none
Knight Tour Backstracking with Warndorff rule improvement RRS feed

  • 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;
            }

    Saturday, October 17, 2020 6:11 PM

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.

    Monday, October 19, 2020 7:08 AM
  • This is the Knight Tour backtracking bruteforce method. However, it was in-sufficient 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.
    Monday, October 19, 2020 7:48 PM
  • 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.

    Tuesday, October 20, 2020 9:25 AM
  • Btw, also not talking about the Warnsdorff's algorithm, but if you'll log the "number of visits" on each cells, you should be able to eliminate the problem of "short loop" by "always go to the cell with lowest visit count" 
    Tuesday, October 20, 2020 9:50 AM
    Answerer