[kaze's test] プログラミングメモ
Knight's Tour 騎士の巡歴

→目次

騎士の巡歴の再帰プログラムです。

#include "stdafx.h"
#include  <windows.h>
#include  <iostream>

#define N 5
using namespace std;

struct POS {
    int x;
    int y;
};
int tour[N][N];   //tour[x][y]

void printTour() 
{
   Sleep(10);
   for (int y = 0; y < N; y++) {
      for (int x = 0; x < N; x++) {
          cout << tour[x][y] << "\t";
      }
      cout << endl;
   }
}

POS POSSIBLE[8] = {
    { 2, 1 }, { 1, 2 },
    {-1, 2 }, {-2, 1 },  
    {-2,-1 }, {-1,-2 },
    { 1,-2 }, { 2,-1 } 
};

bool isMovable(POS pos)
{
   int x = pos.x;
   int y = pos.y;
   return ((x >= 0 && x < N) && (y >= 0 && y < N) && (tour[x][y] == 0));
}

bool knightTour(POS currPos, int tourCount) 
{
    tour[currPos.x][currPos.y] = tourCount;
    if (tourCount == N*N)
        return true;
    for (int i = 0; i < 8; i++) {
        POS nextPos;
        nextPos.x = currPos.x + POSSIBLE[i].x;
        nextPos.y = currPos.y + POSSIBLE[i].y;
        if (isMovable(nextPos)) {
            if (knightTour(nextPos, tourCount + 1)) {

                return true;
            }
        }
    }
    tour[currPos.x][currPos.y] = 0;
    return false;
}
error
int main() 
{
   POS from = {2, 2};
   for (int x = 0; x < N; x ++) {
      for (int y = 0; y < N; y ++) {
          if (from.x == x && from.y == y)
              tour[x][y] = 1;
          else
              tour[x][y] = 0;
      }
   }
   
    POS nextPos;
    bool ret = false;
    for (int i = 0; i < 8; i++) {
        nextPos.x = from.x + POSSIBLE[i].x;
        nextPos.y = from.y + POSSIBLE[i].y;
        if (isMovable(nextPos)) {
            ret = knightTour(nextPos, 2);
            if (ret)
                break;      
        }
    }
       
    if (ret) 
        cout << "Tour is " << endl;
    else 
        cout << "No solusion" << endl;

    printTour();
    getchar();
    return 0;
}