Solving queen puzzle using system verilog constraints

 Problem statement :

• 8 queens should be placed on a chess board such that no queen can kill each other.

Notes :

• To solve this we need to know how queen moves on the chess board.
• Queen can move through entire ROW, COLUMN and across the DIAGONAL.
• Therefore, we should have only 1 queen across each row, column and diagonal.
• Queen in the 2-d matrix used is represented by 1 and the rest are 0's in the matrix(2-D).
• We have 2 set of constraints for the problem.
• diag_c : for controlling the diagonals ( same direction and anti diagonals )
• Transpose_c : for using a transpose matrix for application of sum on the columns.
  

Constraints :

• diag_c :
  
• For this, use 2 matrices, one for normal directional diagonals and one for the other direction.
• Map the elements of the diagonal to the main matrix board.
• Number of row equal number of diagonals present. ( 2*N -1 ).
  
• The number of colums for each row depends on the length of the diagonal.
• For example, if we take a 3x3 matrix, we have 3 diagonals on each side.
• [00].[0,1] [1,0] , [0,2] [1,1] [2,0]. [1,2] [2,1], [3,3]
• Mapping of these will be
• diag - board
• [0,0] - [0,0]
• [1,0] - [0,1] , [1,1] - [1,0]
• [2,0] - [0,2] , [2,1] - [1,1], [2,2] - [2,0]
• [3,0] - [1,2] , [3,1] - [2,1]
• [4,0] - [3,3]
• transpose_c :
• 3 constraints
• board_t transpose map to board
• sum on each row for board
• sum on each row for board_t, in effect it would be a sum on each row of board.
• And we are done. :)
  

//======================================================================//

class queen#(parameter N=3);
  rand bit board[N][N];
  rand bit board_t[N][N];
  rand bit diag[2*N-1][];
  rand bit anti_diag[2*N-1][];

  constraint diag_c {
    foreach(diag[i,j]) {
      if(i < N) diag[i][j] == board[j][i-j];
      else      diag[i][j] == board[(N-1)-j][i+j-N+1];
    }
    foreach(anti_diag[i,j]) {
      if(i < N) anti_diag[i][j] == board[j][N-1-i+j];
      else      anti_diag[i][j] == board[i-(N-1)+j][j];
    }
    foreach (diag[i]     ) {
      diag[i].sum() with (int'(item)) inside {0,1};
    }
    foreach (anti_diag[i]) {
      anti_diag[i].sum() with (int'(item)) inside {0,1};
    }
  }
 
 
  constraint transpose_c {
    foreach(board[i,j])  { board[i][j] == board_t[j][i];  }
    foreach (board[i])   { board[i].sum(item)   with (int'(item))== 1;  }
    foreach (board_t[i]) { board_t[i].sum(item) with (int'(item))== 1;  }
  }
 

  function void pre_randomize();
    int unsigned n;
    foreach(diag[i]) begin //{
      n = (i < N) ? i+1 : 2*N -(i+1);
      diag[i]      = new[n];
      anti_diag[i] = new[n];
    end //}
  endfunction: pre_randomize


  function void display();
    foreach(board[i,j]) begin //{
      $write("%0b ",board[i][j]);
      if(j== N-1) $write("\n");
    end //}
/*
    foreach(diag[i,j]) begin
      if(i < N)  $display(" DIAG %0d %0d BOARD %0d %0d",i,j,j,i-j);
      else       $display(" DIAG %0d %0d BOARD %0d %0d",i,j,((N-1)-j),(i+j-N+1));
    end
    foreach(anti_diag[i,j]) begin
      if(i < N) $display(" DIAG %0d %0d BOARD %0d %0d",i,j,j,(N-1-i+j));
      else      $display(" DIAG %0d %0d BOARD %0d %0d",i,j,(i-(N-1)+j),j);
    end
    */
  endfunction: display
   
endclass: queen

module top;
  queen#(8) q;

  initial begin //{
    q = new;
    void'(q.randomize());
    q.display();
  end //}
endmodule: top