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.
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.
- Vertically:
- Horizontally:
- Diagonally:
Qi and Qj are placed in different columns. This is the default condition, and how we model the chessboard.
Qi and Qj are not in the same row, which means their values should be different. This generates one constraint, Qi ≠ Qj.
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:
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.
it’s great explanation .
Thanks for your explanation.
can you solve horse move by using system verilog..
Thanks.
Can you share with me the link to the problem introduction? I will give it a try.