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

Generating Sudoko using System verilog constraints

Constraints:

• c_values : Constraint on minimum and maximum values any element in the matrix can hold
• c_row_unique :
• We need to have unique value (from 1 to 9) in each row, for this we run 2 loops
• Loop - 1 [i,j] iterates through all elements in 2d-matrix
• Loop - 2 [ ,l] iterates only through each column element
• If condition is used for not picking up the same element for comparison

• Constraint c_row_unique and c_col_unique employs similar strategy to generate unique elements in each row and column
• c_subs_unique :
  
• since each sub matrix 3x3 too should have unique values, we can simply divide the i,j and k,l with 3 to pick each 3x3 matrix and apply unique condition for them as well.
•   !(i==l && j==k) is used to skip same element for comparision.
• matrix[i][j] != matrix[k][l] , compares one element against all the other elements to avoid replication. 
  

//------------------------------------------------------------------------------------------------------------------------//

class sudoku;
  rand bit [3:0] matrix[9][9];

  constraint c_values     { foreach (matrix[i,j]) { matrix[i][j] inside {[1:9]}; } }

  constraint c_row_unique { foreach (matrix[i,j]) { foreach (matrix[,l]) { if(j!=l) matrix[i][j] != matrix[i][l]; } } }                    
  constraint c_col_unique { foreach (matrix[i,j]) { foreach (matrix[k,]) { if(i!=k) matrix[i][j] != matrix[k][j]; } } }  

constraint c_sub_unique { foreach (matrix[i,j]) { foreach (matrix[k,l]){ if(i/3 == k/3 && j/3 == l/3 && !(i==k && j==l)) matrix[i][j] != matrix[k][l]; } } } 

  function void display();
    foreach(matrix[i,j]) begin //{
      $write("%0d ",matrix[i][j]);
      if(j == 8) $write("\n");
    end //}
  endfunction: display

endclass: sudoku

module top;
  sudoku s;

  initial begin
    s = new;
    void'(s.randomize());
    s.display();
  end
endmodule:top