8-2 ナイト巡回問題

問題

バックトラック法

ナイト巡回問題は、与えられたマスを、ナイトが連続して飛び続けることで、
全てのマスを１回ずつ訪れる経路を求める問題である。 

行儀の良くないナイト巡回問題を解きます。

ソース

#include <Windows.h>
#include <string>
#include <stack>

struct JyoutaiDef
{
    int Level;
    int X;
    int Y;
    std::string Path;
};

bool IsValid(int X,int Y,std::string Path);

void main()
{
    std::stack<JyoutaiDef> stk;

    JyoutaiDef WillPush;
    WillPush.Level = 1;
    WillPush.X = WillPush.Y = 1;
    WillPush.Path = "(1,1)";
    stk.push(WillPush);

    int AnswerCnt = 0;

    while (stk.empty() == false) {
        JyoutaiDef Popped = stk.top(); stk.pop();

        if (Popped.Level == 5 * 5) {
            printf("Answer%03d=%s\n",++AnswerCnt,Popped.Path.c_str());
            continue;
        }

        WillPush.Level = Popped.Level + 1;

        int moveX[] = { +1, +2, +2, +1, -1, -2, -2, -1 };
        int moveY[] = { -2, -1, +1, +2, +2, +1, -1, -2 };

        for (int I = 0; I <= sizeof(moveX)/sizeof(int)-1; I++) {
            WillPush.X = Popped.X + moveX[I];
            WillPush.Y = Popped.Y + moveY[I];

            if (IsValid(WillPush.X, WillPush.Y, Popped.Path)) {
                char wk[99];
                wsprintf(wk,"(%d,%d)",WillPush.X, WillPush.Y);
                WillPush.Path = Popped.Path + wk;
                stk.push(WillPush);
            }
        }
    }
}

bool IsValid(int X,int Y,std::string Path)
{
    if (X < 1) return false;
    if (X > 5) return false;
    if (Y < 1) return false;
    if (Y > 5) return false;

    char wk[99];
    wsprintf(wk,"(%d,%d)",X, Y);

    return Path.find(wk) == std::string::npos;
}

実行結果

Answer001=(1,1)(2,3)(1,5)(3,4)(2,2)(1,4)(3,5)(5,4)(4,2)(2,1)(1,3)(2,5)(4,4)(5,2)(3,1)(1,2)(2,4)(4,5)(3,3)(4,1)(5,3)(3,2)(5,1)(4,3)(5,5)
Answer002=(1,1)(2,3)(1,5)(3,4)(2,2)(1,4)(3,5)(5,4)(4,2)(2,1)(1,3)(2,5)(4,4)(5,2)(3,1)(1,2)(3,3)(4,1)(5,3)(4,5)(2,4)(3,2)(5,1)(4,3)(5,5)
Answer003=(1,1)(2,3)(1,5)(3,4)(2,2)(1,4)(3,5)(5,4)(4,2)(2,1)(1,3)(2,5)(3,3)(4,1)(5,3)(4,5)(2,4)(1,2)(3,1)(5,2)(4,4)(3,2)(5,1)(4,3)(5,5)
省略
Answer302=(1,1)(3,2)(5,1)(4,3)(5,5)(3,4)(4,2)(5,4)(3,3)(2,1)(1,3)(2,5)(4,4)(5,2)(3,1)(1,2)(2,4)(4,5)(5,3)(4,1)(2,2)(1,4)(3,5)(2,3)(1,5)
Answer303=(1,1)(3,2)(5,1)(4,3)(5,5)(3,4)(4,2)(5,4)(3,5)(1,4)(2,2)(4,1)(5,3)(4,5)(2,4)(1,2)(3,3)(2,1)(1,3)(2,5)(4,4)(5,2)(3,1)(2,3)(1,5)
Answer304=(1,1)(3,2)(5,1)(4,3)(5,5)(3,4)(4,2)(5,4)(3,5)(1,4)(2,2)(4,1)(5,3)(4,5)(2,4)(1,2)(3,1)(5,2)(3,3)(2,1)(1,3)(2,5)(4,4)(2,3)(1,5)

解説

下記のように配列の初期化子で符号を明示して、オートフォーマットしても上下がずれないようにしてます。
int moveX[] = { +1, +2, +2, +1, -1, -2, -2, -1 };
int moveY[] = { -2, -1, +1, +2, +2, +1, -1, -2 };