Solving the N Queens Problem in SystemVerilog

Hi, today I’m going to post my thoughts on how to solve the N Queens problem using constraints in SystemVerilog. I am using one particular algorithm to solve it. I believe there must also be other ways to model the chessboard to approach this problem using other constraints. If I have time later, I will try to add other methods to solve it.

The N Queens problem means that we want to place N queens on an NxN chessboard, so that no two queens threaten each other, meaning no two queens share the same row, column and diagonal.

In this post, I’m going to use the Eight Queens problem to illustrate how I model the chessboard, construct the constraints, and solve the problem. The Wikipedia page link for the Eight Queens Problem can be found here.

 

Image credit: Queen pieces from Cburnett under CC 3.0

I am going to use an array to model the location of each queen. It is an array of eight elements: Q0, Q1, Q2, Q3, Q4, Q5, Q6, Q7, which represent the queens on each column and has its row number as its value. For this chessboard, we have Q0 = 1, Q1 = 7, Q2 = 4, Q3 = 6, Q4 = 8, Q5 = 2, Q6 = 5, and Q7 = 3. So, the value of Q should be between 1 and 8.

We are going to set up the constraints to solve the eight queens problem. The key is that no queen can attack another queen.

  1.  Vertically:
  2. Qi and Qj are placed in different columns. This is the default condition, and how we model the chessboard.

  3. Horizontally:
  4. Qi and Qj are not in the same row, which means their values should be different. This generates one constraint, Qi ≠ Qj.

  5. Diagonally:
  6. The queens cannot be the same number of rows apart as they are columns apart. This gives us another constraint, |i-j| ≠ |Qi-Qj|.

So, the code can be written according to the constraints we have:

class Q_class #(int N =8); //parameterized class
  rand int Q[N];

  //The value of Qi is between 1 and N
  constraint Qi_value{
    foreach(Q[i])
      Q[i] inside {[1:N]};
  }

  //The value of Qi does not equal to any other Qj
  constraint Qi_doesnt_equal_Qj{
    foreach(Q[i])
      foreach(Q[j])
        if(i!=j)
          Q[i] != Q[j]; //Qi ≠ Qj
  }

  //Diagonal condition
  constraint Qi_Qj_absolute_valeu{
    foreach(Q[i])
      foreach(Q[j])
        if(i!=j)
          !((Q[i]-Q[j]) inside {(i-j), (j-i)}; //|i-j| ≠ |Qi-Qj|
  }

endclass

program N_Queens;

  initial begin

    Q_class qc1; //N = 8 default value
    Q_class #(4) qc2; //N = 4
    qc1 = new();
    qc2 = new();
   
    qc1.randomize();
    $display("qc1.Q is %p", qc1.Q);
    qc1.randomize();
    $display("qc1.Q is %p", qc1.Q);

    qc2.randomize();
    $display("qc2.Q is %p", qc2.Q);
    qc2.randomize();
    $display("qc2.Q is %p", qc2.Q);

  end

endprogram

That’s all for this post. Leave me a comment below if you have any questions. I will try to come up with other methods to solve this problem later.

2 thoughts on “Solving the N Queens Problem in SystemVerilog

  1. it’s great explanation .
    Thanks for your explanation.
    can you solve horse move by using system verilog..

Leave a Reply

Your email address will not be published. Required fields are marked *