N Queen Board Problem in SV Constraint

SystemVerilog
, , ,
1

Hi, I have been struggling in solving N queen problem in SV constraint. I know how to constraint the elements for each column and row(credit to the forum). However, diagonals are really a nightmare to me. Can anyone help me out, a detailed explain will be appreciated!!!


class queen_board;
 rand bit queen_b[8][8];
 
 constraint row_c {
    foreach(queen_b[row]) queen_b[row].sum() with (int'(item)) <= 1;
} 
 constraint col_c {
    foreach(queen_b[,col]) queen_b.sum() with (int'(queen_b[item.index(1)][col])) <= 1;
}
 constraint diag_c{
  //??????????????????????????
}
endclass
2

In reply to qkuang:
A key part of this problem is the diagonals have different lengths. You need to guard

module top;
  parameter N = 8;
  class queen_board;
    rand bit queen_b[N][N];
    constraint c {
      foreach(queen_b[i]) {
        queen_b[i].sum() with (int'(item)) == 1; // row
        queen_b.sum(b) with (int'(queen_b[b.index][i])) == 1; // col
        // descending diagonals
        queen_b.sum(b) with (i+b.index<N? int'(queen_b[b.index][i+b.index]) : 0) <= 1;
        queen_b.sum(b) with (i+b.index<N? int'(queen_b[i+b.index][b.index]) : 0) <= 1;
        // ascending diagonals
        queen_b.sum(b) with (i+b.index<N? int'(queen_b[N-1-i-b.index][N-1-b.index]) : 0) <= 1;
        queen_b.sum(b) with (i+b.index<N? int'(queen_b[N-1-b.index][N-1-i-b.index]) : 0) <= 1;
      }
    }
  endclass
     
  queen_board qb = new;
      initial repeat(5) begin
    assert(qb.randomize());
    foreach(qb.queen_b[i]) $display("%p",qb.queen_b[i]);
    $display;
  end
endmodule
3

In reply to dave_59:

Thanks Dave! What a elegant solution!
But I think your ascending diagonals constraints are equivalent to descending ones. So there may still has elements on same ascending diagonal.
I updated the constraint and added some comments. If people are interested in this puzzle, hopefully it can help.

if we have a 3X3 board, the coordinates for each location are:
(0,0)(0,1)(0,2)
(1,0)(1,1)(1,2)
(2,0)(2,1)(2,2)


//descending diagonals
 queen_b.sum(b) with (i+b.index<N? int'(queen_b[b.index][i+b.index]) : 0) <= 1;
 // constraint (0,0)+(1,1)+(2,2) <= 1, (0,1)+(1,2) <= 1, (0,2) <= 1;

 queen_b.sum(b) with (i+b.index<N? int'(queen_b[i+b.index][b.index]) : 0) <= 1;
 // constraint (0,0)+(1,1)+(2,2) <= 1, (1,0)+(2,1) <= 1, (2,0) <= 1;

// ascending diagonals
 queen_b.sum(b) with (i+b.index<N? int'(queen_b[b.index][N-1-b.index-i]) : 0) <= 1;
 // constraint (0,2)+(1,1)+(2,0) <= 1, (0,1)+(1,0) <= 1, (0,0) <= 1;

 queen_b.sum(b) with (i+b.index<N? int'(queen_b[i+b.index][N-1-b.index]) : 0) <= 1; 
 // constraint (2,0)+(1,1)+(0,2) <= 1, (2,1)+(1,2) <= 1, (2,2) <= 1;
4

In reply to dave_59:

Hi Dave ,
Have a question related to unrolling of queen_b.sum(b) :

foreach(queen_b[i]) queen_b[i].sum() with (int'(item)) == 1;

Here item refers to each element of queen_b[i] i.e queen_b[i][0] to queen_b[i][7]
As i iterates from 0 to 7 , the resultant expression will be sum i.e addition (+) of 8 resultant with_expression i.e :
For queen_b[0].sum() i.e Row 0 :: int’( queen_b[0][0] ) + int’( queen_b[0][1] ) + … + int’( queen_b[0][7] ) == 1 ;
Similarly for queen_b[7].sum() i.e Row 7 :: int’( queen_b[7][0] ) + int’( queen_b[7][1] ) + … + int’( queen_b[7][7] ) == 1 ;

For queen_b.sum(b) , will the resultant expression comprise of sum of 8x8 i.e 64 with expressions ? ( with some elements being 0 due to false condition )

5

In reply to ABD_91:

Array reduction methods iterates single dimension of an array. For this question, if you didn’t specify with clause in queen_b.sum(b), it will cause a compiling error.

6

Hello @dave_59 , can you please let me know why the below code is not working for checking diagonal contradiction?

constraint c1 {
      foreach(queen_b[i,j]) {
        foreach(queen_b[m,n])
                {
                  if( i != m && j != n)
                  {
                    i - m != j - n;
                    i - m != n - j;
                  }
                  	
                }
           }
    }
7

Okay, I had forgotten to add a few additional conditions:

if( i != m && j != n && queen_b[i][j] == 1 && queen[m][n] == 1)

8

Hi @dave_59 Could you please explain the interpretation of this expression in constraint ? I understood the part where we are trying to identify diagonal elements such that they are below descending diagonal but couldn’t understand queen_b[b.index][i+b.index] . Please provide interpretation.

9

I solved the above way, using the following as the reference
:Solving the N Queens Problem in SystemVerilog – Yue Guo

10

Below one solution also works well .


`define N 8

class my_item;

  //Final chess-board for N-Queens placement
  bit board[`N][`N];
  
  // Permute encodes the placement on the board
  // For N queens, 2 Queens cannot be on same row or column
  // Hence the board can be encoded using permute array
  // Permute[i]=j means there is Queen on row=i, column=j
  rand int permute[`N];
    
  constraint tc{
    //Columns have to be unique
    unique {permute};
    foreach(permute[i]){
      //Queens have to be within the board range
      permute[i] inside {[0:`N-1]};
      foreach(permute[j]){
        //Diagonal Queen constraint
        //abs(i-j)!=abs(perm(i)-perm(j))
        i!=j -> (i-j)!=(permute[i]-permute[j]);
        i!=j -> (i-j)!=(permute[j]-permute[i]);
      }
    }
  }
        
  function void post_randomize();
      for(int i=0; i<`N; i++)begin
        board[i][permute[i]] = 1;
      end
  endfunction
 

  // Print out the items.
  function void print();
    string s;
    $display("Printing Sudoku");
    foreach (board[i])begin
      s="";
      foreach (board[i][j])begin
        s = {s, " ", $sformatf("%0d", board[i][j])};
      end
    $display(" %s", s);
    end
  endfunction
      
    
  
endclass

module automatic test;
  function void run;
    my_item item = new();
    for (int i = 0; i < 1; i++) begin
      $display("RANDOMIZE %0d", i);
      item.randomize();
      item.print();
    end
  endfunction
  initial run();
endmodule
``verilog
11

Yes. Below one solution is very much easy to understand . pls refer EDA playground link - EDA Playground

// Code your testbench here
// or browse Examples

`define N 8
 
class Nqueen ;
  
  bit board[`N][`N];
  
  rand int q[`N] ; // Array to store the col position of the queen of each row 
  
 constraint unique_col {
    unique {q} ; // each col has to be unique.
    foreach (q[i]) {   // Queens has to be within the range of board.
      q[i] inside {[0:`N-1]};
    }
  }
  
      // No 2 queens on same daigonal (both the directions ) -//|i-j| ≠ |Qi-Qj|
      
 constraint no_daigo_queen_attack {
    foreach(q[i]) {
      foreach(q[j]) {
        i!=j -> (i-j)!=(q[i]-q[j]);
        i!=j -> (i-j)!=(q[j]-q[i]);
      }
    }         
 }
        

function void print();
    string s;
  $display("Printing N queen output: ");
    foreach (board[i])begin
      s="";
      foreach (board[i][j])begin
        s = {s, " ", $sformatf("%0d", board[i][j])};
      end
    $display(" %s", s);
    end
endfunction
        

function void post_randomize();
      for(int i=0; i<`N; i++)begin
        board[i][q[i]] = 1;
      end
  endfunction
  
endclass


module Nqueen_test;
  Nqueen queen_h ;
  
  initial begin
    queen_h = new();
    if(!queen_h.randomize())
      $display("Randamisation is failed !!");
    else begin
      $display("Randamisation is Successful!! ");
      queen_h.print();
    end 
    
  end 
  
endmodule
``verilog
12

Hi Dave, Could you please help with array iterator method (index)? How it is working with multidimensional array? I know it can work with sub array or single dimension arrays.
Since foreach is on each row iterator, so what would b.index yield?
Please elaborate below constraint for better understanding!
queen_b.sum(b) with (i+b.index<N? int’(queen_b[b.index][i+b.index]) : 0) <= 1;

Thanks!
Regards
Ankur