Asked by:
Knight Tour Backstracking with Warndorff rule improvement
Question

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[i]), (y + yMove[i])))
attemptedMoves++;
}
return attemptedMoves;
}
All replies

Hi Zidane99,
Thank you for posting here.
There is no exception in this code. Does its output not meet your expectations?
Could you please describe your problem in detail?
This will let us know where to start.
Best Regards,
Timon
MSDN Community Support
Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com. 
This is the Knight Tour backtracking bruteforce method. However, it was insufficient and it did not work for all coordinate. For example, if I change int startX = 0; int startY = 4; It will loop FOREVER. Therefore, Warndorff rule is a better solution. How can I apply that Algorithm into this code.

Hi Zidane99,
I’m not familiar with this algorithm, but please see if the code example in this link meets your requirements,
Warnsdorff’s algorithm for Knight’s tour problem
Note: This response contains a reference to a third party World Wide Web site. Microsoft is providing this information as a convenience to you. Microsoft does not control these sites and has not tested any software or information found on these sites; Therefore, Microsoft cannot make any representations regarding the quality, safety, or suitability of any software or information found there. There are inherent dangers in the use of any software found on the Internet, and Microsoft cautions you to make sure that you completely understand the risk before retrieving any software from the Internet.
Best Regards,
Timon
MSDN Community Support
Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com. 