Solving Knight’s Tour Problem Using SystemVerilog Constraints

Hi, I was asked by one of my readers to solve this problem using SystemVerilog. It definitely took me some time to figure out how I would like to model the chessboard. So today I would like to share my solution here.

First, let’s take a look at the definition of this problem. According to Wikipedia, a knight’s tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight’s move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed; otherwise, it is open.

The common methods to solve this problem are to use the Backtracking algorithm or Warnsdorff’s algorithm. I am looking at this from the hardware programming language’s angle. So I am going to use SystemVerilog constraints to solve this question.

 
We know that the knight should visit each square exactly once and cover all the squares on the chessboard. For explanatory purposes, I am going to implement this example in a 5×5 chessboard. We can model our chessboard using the following data structures:

  1. Row and column values of each time’s visit
  2. For example, the knight’s location here is row 1, column 2, because we start from row 0 and column 0.

    For each visit, we are going to record the row and column information. We need two arrays, each of size N^2, which is 25 in our case to store the information. For example, if the knight starts at the location marked in the figure below, row[0] is 1, and column[0] is 2. We are going to write the next stop’s location information into row[1] and column[1], and so on.

    The following equation is used to calculate the location value using row and column information.

    location value = row value * N + column value

    We can mark each square with its corresponding location value, from 0 to 5*5-1, which is 24 as below:

  3. Helper array
  4. The helper array is needed to record the sequence of the visiting order. The size of the helper array is N*N. In our case, N is 5, so the size of the helper array is 25.

    helper_array[0] is the location value of where the knight starts, helper_array[1] is the location value of where the knight is after its first move, and so on. helper_array[24] is the location value of where the knight stands after the tour ends.

  5. Another array to rebuild the chessboard
  6. For the helper array, we only record the location information of each move, and it’s not easy to understand that intuitively. We need to bring in another array to help us rebuild the chessboard for this purpose. This is not required. We are only going to use this in the post_randomize function.

    We use the array find_index method here to find the visiting sequence of a certain square. For example, if we have help_array [3] = 4, this means we visited square 4 at the 3rd move. A loop is needed to iterate through the help_array. Since we need to use the find_index method, we also need to instantiate a queue to store the result. Then we are going to pop up the value from the queue to store it in this new array.

 

Now we have all the data structures ready, we can define all the constraints and the post_randomize function in the following:

  1. Column and row values inside 0 to N-1
  2. The column and row values are bounded by the chessboard’s size. Since we have a 5×5 chessboard here. The values for columns and rows are between 0 and 4.

  3. Map column and row values to the helper array
  4. We need to map the location value into the helper array. We can get the equation from above:

    location value = row value * N + column value

  5. The values in the helper array should be unique
  6. Since we are visiting each square exactly once, the location values should be different from each other.

  7. Knight move
  8. From the above figure, we can see all eight possible squares the knight can move to. We can see the pattern here: |row(i)-row(i-1)| + |column(i)-column(i-1)|= 3, which means the absolute distance difference is 3, either 1 row and 2 columns apart, or 2 rows and 1 columns apart. At the same time, the next move is not on the same column nor row with the current location, which gives us row(i) ≠ row(i-1) and column(i) ≠ column(i-1)

  9. Closed game
  10. A closed game means the last square where the knight is is a knight move away from the first square where it starts. This can be solved by using a similar knight move constraint to constrain the row and column values of move 0 and N^2-1. In our case, move 0 and move 24.

  11. Post_randomize function to rebuild the chessboard
  12. We are going to iterate from square 0 to square 24 and get the visiting sequence for all the squares. The index value of the helper array is when the square is visited. We are going to store the value inside the new array from square 0 to square 24.

 
The SystemVerilog code can be constructed correspondingly:

program p1;


    class c1 #(int N = 5);

        //each move's row and column values
        rand int row[N**2];
        rand int col[N**2];

        //visiting order
        rand int helper_array[N**2];


        //helper array
        int A[N**2];
        int q[$];


        /*
        1. column value inside [0:N-1]
        2. row value inside [0:N-1]
        3. Map the helper array to row and col, unique values
        4. Knight move |i'-i|+|j'-j| = 3  i'≠ i j'≠ j
        5. closed game
        */



        //column and row value range
        constraint c1 {
            foreach(row[i])
                row[i] inside {[0:N-1]};
            foreach(col[i])
                col[i] inside {[0:N-1]};
        }


        //map helper array to row and col
        constraint c2 {
            foreach(helper_array[i])
                helper_array[i] == N*row[i]+col[i];
            unique {helper_array}; //unique value

        }



        //knight move
        constraint c3 {
            foreach(row[i])
                //constraint guard
                (i>0) -> ((((row[i]>row[i-1])?(row[i]-row[i-1]):(row[i-1]-row[i]))+((col[i]>col[i-1])?(col[i]-col[i-1]):(col[i-1]-col[i])))== 3)
                        &&(row[i]!=row[i-1])&&(col[i]!=col[i-1]);
        }


        //closed game
        // constraint c4 {

        //  ((((row[N**2-1]>row[0])?(row[N**2-1]-row[0]):(row[0]-row[N**2-1]))+((col[N**2-1]>col[0])?(col[N**2-1]-col[0]):(col[0]-col[N**2-1])))== 3)
        //  &&(row[N**2-1]!=row[0])&&(col[N**2-1]!=col[0])

        //  ;

        // }



        function void post_randomize ();
            for (int i = 0; i < N**2; i++) begin
                q = helper_array.find_index with ( item == i ); //find the index value of the square i
                A[i] = q.pop_front(); //pop the value out and store it in A
             end    
        endfunction

    endclass


    c1 #(5) c1_h2;


    initial begin

        c1_h2 = new();



        repeat(3) begin
            if(c1_h2.randomize()) begin

                $display("==========================================================================================");

                for (int i = 0; i < 5; i++) begin
                    for (int j = 0; j < 5; j++) begin
                        $write("%d", c1_h2.A[i*5+j]);
                    end
                    $display("");
                end
                $display("==========================================================================================\n");

            end
        end

    end

endprogram

 
The last constraint is about the closed game. However, the constraints couldn’t be solved using all major vendors’ simulation tools. I am guessing the computation is too complex for now. I am going to leave the constraint commented at this moment. Maybe I will try that again later when they have more optimized constraint solvers.

Also, there are some limitations to different vendors. Not all of the simulators can solve all the constraints. The constraints are complex enough, and it is not possible at this point to increase the chessboard dimension to a bigger number. Theoretically, I believe the constraints are constructed correctly.

 
Thank you for reading. That’s all for this post. Leave me a comment below if you have any questions.

Leave a Reply

Your email address will not be published.