2

Knight's Tour のコードを書こうとしています:

ナイト ツアーとは、チェス盤上のナイトの一連の動きであり、ナイトがすべてのマスを 1 回だけ訪れるようになっています。

他の人のコードを変更しようとしましたが、バックトラッキングが正しく機能していないようです - 解決策が見つかりません。騎士が 0, 0 から開始する場合は完全に正常に動作しますが、2D グリッドの他の場所から開始する場合、プログラムは永遠に続きます。

このコードのどこにバグがありますか?

#include <iostream>
#include <ctime>
using namespace std;

const int N = 8;
int map[N][N];

/* A utility function to check if i,j are valid indexes for N*N chessboard */
bool isSafe(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N && map[x][y] == -1;
}

/* A utility function to print solution matrix sol[N][N] */
void printSolution() {
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++)
            cout << map[x][y];
        cout << endl;
    }
}

/* A recursive utility function to solve Knight Tour problem */
bool knightsTourRecursive(int x, int y, int movei, int xMove[N], int yMove[N]) {
    int nextX, nextY;

    if (movei == N*N)
        return true;

    /* Try all next moves from the current coordinate x, y */
    for (int k = 0; k < 8; k++) {
        nextX = x + xMove[k];
        nextY = y + yMove[k];

        if (isSafe(nextX, nextY)) {
            map[nextX][nextY] = movei;

            if (knightsTourRecursive(nextX, nextY, movei+1, xMove, yMove))  // recursion
                return true;
            else
                map[nextX][nextY] = -1;             // backtracking
        }
    }
    return false;
}

bool knightsTour() {
    /* Initialization of solution matrix */
    for (int x = 0; x < N; x++)
        for (int y = 0; y < N; y++)
            map[x][y] = -1;

    /* xMove[] and yMove[] define next move of Knight.
       xMove[] is for next value of x coordinate
       yMove[] is for next value of y coordinate */
    int xMove[8] = {  2, 1, -1, -2, -2, -1,  1,  2 };
    int yMove[8] = {  1, 2,  2,  1, -1, -2, -2, -1 };

    int initX = rand() % N;
    int initY = rand() % N;

    cout << "Starting at " << initX << " " << initY << endl;

    // Since the Knight is initially at the first block
    map[initX][initY]  = 0;

    /* explore all tours using solveKTUtil() */
    if(!knightsTourRecursive(initX, initY, 1, xMove, yMove) ) {
        cout << "Solution does not exist" << endl;
        return false;
    }
    else
        printSolution();

    return true;
}

int main() {
    srand( (unsigned) time(0));
    knightsTour();

    cin.get();
    return 0;
}
4

2 に答える 2

2

このプログラムは完全に正しいようです。このコードにバグは見当たりません。

ただし、騎士のツアーは非常に複雑なアルゴリズムです。実際には、プログラムは 64!=1*2*3*...*64 までの異なる方法でボードをチェックする必要があります。これは89個のゼロからなる数字です!

多くの場合、バックトラックは初期の分岐で停止しますが、一部の分岐は永久に上昇します。

0,0 から始まるツアーがすぐに見つかった場合、それは純粋な偶然であるか、(0,0) の解がすぐに見つかるように配列 xMove と yMove が巧妙に初期化された可能性があります。

したがって、問題はプログラムではなく、アルゴリズムです。このトピックについて調査を行うことをお勧めします。ナイツツアーには、より妥当な時間で解決策を提供する多くのアルゴリズムがあります。

于 2013-08-06T07:24:19.823 に答える
0

コメントするほどの評判はありませんが、これはコメントのようなものです。Warnsdorff の Rule のPython 実装については、こちらを確認してください。Warnsdorff の規則に対するさらなる最適化については、ここで説明します

于 2013-11-29T05:36:19.867 に答える