Knight Tour Backstracking with Warndorff rule improvement

[Zidane99]

The assignment said that I could improve it with Warnsdorff’s algorithm with int CountVisitedNeighbors().

Use this function to compare all of the knight's possible moves. Choose the next move where the most neighbors have already been visited.





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

//static int[] xMove = { 1, 1, 2, 2, -1, -1, -2, -2 };
//static int[] yMove = { 2, -2, 1, -1, 2, -2, 1, -1 };
// boardGrid is an 8x8 array that contains -1 for an unvisisted square or a move number between 0 and 63.
static int[,] boardGrid = new int[BoardSize, BoardSize];

/// <summary>
/// Driver Code
/// </summary>
static void Main(string[] args)
{
solveKT();
Console.ReadLine();
}

/// <summary>
/// This function solves the Knight Tour problem using backtracking. This function use solveKTUtil() to
/// solve the problem.It returns false if no complete tour is possible, otherwise return true and print the tour.Please note
/// that there may be more than one solution.
/// </summary>
static void solveKT()
{
/* Initialization of solution matrix. value of -1 means "not visisted yet" */
for (int x = 0; x < BoardSize; x++)
{
for (int y = 0; y < BoardSize; y++)
{
boardGrid[x, y] = -1;
}
}

int startX = 0;
int startY = 0;
// set starting position for knight
boardGrid[startX, startY] = 0;

// count the total number of guesses
attemptedMoves = 0;

/* explore all tours using solveKTUtil()*/
if (!solveKTUtil(startX, startY, 1))
{
Console.WriteLine("Solution does not exist for {0} {1}", startX, startY);
}
else
{
printSolution(boardGrid);
Console.Out.WriteLine("Total attempted moves {0}", attemptedMoves);
}
}

/// <summary>
/// A recursive utility function to solve Knight Tour problem
/// </summary>
static bool solveKTUtil(int x, int y, int moveCount)
{
attemptedMoves++;
if (attemptedMoves % 10000000 == 0) Console.Out.WriteLine("Attempts: {0}", attemptedMoves);

int k, next_x, next_y;

// check to see if we have reached a solution. 64 = moveCount
if (moveCount == BoardSize * BoardSize) return true;

/*Try all next moves from the current coordinate x, y*/
for (k = 0; k < 8; k++)
{
next_x = x + xMove[k];
next_y = y + yMove[k];
if (isSquareSafe(next_x, next_y))
{
boardGrid[next_x, next_y] = moveCount;
if (solveKTUtil(next_x, next_y, moveCount + 1))
{
return true;
}
else
//backtracking
boardGrid[next_x, next_y] = -1;
}
}
return false;
}

/// <summary>
/// a utility function to check if i,j are valid indexes for N*N chessboard
/// </summary>
static bool isSquareSafe(int x, int y)
{
return (x >= 0 && x < BoardSize &&
y >= 0 && y < BoardSize &&
boardGrid[x, y] == -1);
//if (x < 0 || x >= BoardSize || y < 0 || y >= BoardSize)
//{
// return false;
//}
//else
// return true;
}

/// <summary>
/// A utility funciton to print solution matrix sol[N][N]
/// </summary>
static void printSolution(int[,] solution)
{
for (int x = 0; x < BoardSize; x++)
{
for (int y = 0; y < BoardSize; y++)
{
Console.Write(solution[x, y] + " ");
}
Console.WriteLine();
}
}


static int CountVisitedNeighbors(int x, int y)
{
for (int i = 0; i < BoardSize; i++)
{
if (isSquareSafe((x + xMove), (y + yMove)))
attemptedMoves++;
}
return attemptedMoves;
}

Continue reading...