Knight tour все ответы на c ++

Для задачи о рыцарском туре я пришел к следующему ответу; однако он просто печатает один ответ. Я не знаю, как распечатать все ответы. Я знаю, что мне нужно изменить вывод поиска на пустоту, чтобы не закончить, но я не знаю, как это сделать. Может кто доработать?

#include <iostream>
using namespace std;

const int ROW_COUNT = 6;
const int COL_COUNT = 6;
const int POSSIBLE_MOVES = 8;

int row_delta[POSSIBLE_MOVES] = {2, 1, -1, -2, -2, -1, 1, 2};
int col_delta[POSSIBLE_MOVES] = {-1, -2, -2, -1, 1, 2, 2, 1};

int board[ROW_COUNT][COL_COUNT];

void print_board() {
    for (int i = 0; i < ROW_COUNT; i++) {
        for (int j = 0; j < COL_COUNT; j++) {
            if (board[i][j] < 10)
                cout << ' ';
            cout << board[i][j] << ' ';
        }
        cout << endl;
    }
    cin.get();
}

bool find_tour(int move_no, int current_row, int current_col) {
    // uncomment the following two lines for debugging:
     //cout << move_no << endl;
     //print_board();

    if (move_no == ROW_COUNT * COL_COUNT)
        return true;

    for (int move = 0; move < POSSIBLE_MOVES; move++) {
        int new_row = current_row + row_delta[move];
        int new_col = current_col + col_delta[move];

        if (new_row < 0 || new_row >= ROW_COUNT || new_col < 0 || new_col >= COL_COUNT)
            continue;

        if (board[new_row][new_col] != 0)
            continue;

        board[new_row][new_col] = move_no + 1;
        if (find_tour(move_no + 1, new_row, new_col))
            return true;
        board[new_row][new_col] = 0;
    }
    return false;
}

void solve(int init_row, int init_col) {
    for (int row = 0; row < ROW_COUNT; row++)
        for (int col = 0; col < COL_COUNT; col++)
            board[row][col] = 0;

    board[init_row][init_col] = 1;
    if (find_tour(1, init_row, init_col))
        print_board();
    else
        cout << "Failed to find a tour!\n";
}

int main() {
    solve(2, 3);
}

c++ recursion backtracking
person mohammad amin    schedule 09.10.2015    source источник
comment
Похоже, вы могли бы использовать цикл. Для каждого места на доске решайте в указанном месте.   -  person Thomas Matthews    schedule 09.10.2015
comment
Поищите в StackOverflow экскурсию по c ++ Knights, чтобы получить больше примеров.   -  person Thomas Matthews    schedule 09.10.2015
comment
@ThomasMatthews Да, я уже искал. Видите ли, моя проблема не в том, как придумать один ответ, как мой код, а в том, чтобы найти все маршруты. И я не понял, куда я должен положить петлю.   -  person mohammad amin    schedule 09.10.2015
comment
Ваш код близок; ему нужно использовать отслеживание с возвратом. Каждый раз, когда find_tour вызывает find_tour, вы не должны возвращаться в случае успеха. Вместо этого измените ход и попробуйте другие возможные ходы. Вы должны print_board, когда move_no == ROW_COUNT * COL_COUNT), потому что это решение.   -  person cliffordheath    schedule 09.10.2015
comment
@cliffordheath Спасибо, чувак! Это сработало.   -  person mohammad amin    schedule 09.10.2015
comment
Узнайте, как использовать отладчик. Затем с помощью отладчика вы можете пройти по коду и определить место, в котором он делает что-то не так. Этот метод важен для программирования, в частности, он полезен для знакомства с новым кодом.   -  person Ulrich Eckhardt    schedule 09.10.2015
comment
Также не ждите, пока это найдет все решения. Однажды я оставил высокооптимизированную версию этой системы работать на три недели (она нашла много тысяч решений), и она отступила лишь на крошечной части пути. Я подозреваю, что общее время выполнения больше, чем оставшаяся продолжительность жизни Вселенной.   -  person cliffordheath    schedule 09.10.2015

Ответы (1)


arrow_upward
2
arrow_downward

Следуя моему комментарию, этот код должен работать:

#include <iostream>
using namespace std;

const int ROW_COUNT = 6;
const int COL_COUNT = 6;
const int POSSIBLE_MOVES = 8;

int row_delta[POSSIBLE_MOVES] = {2, 1, -1, -2, -2, -1, 1, 2};
int col_delta[POSSIBLE_MOVES] = {-1, -2, -2, -1, 1, 2, 2, 1};

int board[ROW_COUNT][COL_COUNT];

void print_board() {
    for (int i = 0; i < ROW_COUNT; i++) {
        for (int j = 0; j < COL_COUNT; j++) {
            if (board[i][j] < 10)
                cout << ' ';
            cout << board[i][j] << ' ';
        }
        cout << endl;
    }
    cin.get();
}

find_tour(int move_no, int current_row, int current_col) {
    // uncomment the following two lines for debugging:
     //cout << move_no << endl;
     //print_board();

    if (move_no == ROW_COUNT * COL_COUNT)
    {
        print_board();
        return;
    }

    for (int move = 0; move < POSSIBLE_MOVES; move++) {
        int new_row = current_row + row_delta[move];
        int new_col = current_col + col_delta[move];

        if (new_row < 0 || new_row >= ROW_COUNT || new_col < 0 || new_col >= COL_COUNT)
            continue;

        if (board[new_row][new_col] != 0)
            continue;

        board[new_row][new_col] = move_no + 1;
        find_tour(move_no + 1, new_row, new_col);
        board[new_row][new_col] = 0;
    }
}

void solve(int init_row, int init_col) {
    for (int row = 0; row < ROW_COUNT; row++)
        for (int col = 0; col < COL_COUNT; col++)
            board[row][col] = 0;

    board[init_row][init_col] = 1;
    find_tour(1, init_row, init_col);
}

int main() {
    solve(2, 3);
}
person cliffordheath    schedule 09.10.2015