Hidden Gems of SystemVerilog – 4. Solving Sudoku with Uniqueness Constraints

This is a sequel of my old article about solving Sudoku. One of my audiences suggested me for using “unique” constraint to solve Sudoku. The “unique” constraint, which was added to IEEE Std 1800™-2012, constrains a group of variables such that no two members of the group have the same value after randomization. This sounds promising to solve Sudoku, so let’s give it a try. I’m going to replace the three constraints (row_con, column_con, and block_con) in the previous article.

Row constraint

Constraining the boxes on the same row is pretty straightforward using the “unique” constraint. This diagram shows the indexes of two-dimensional array (box[N][N]), where N=9.

Indexes of box[N][N] Array

The line 5 makes the column values on each row unique.

1
2
3
4
5
6
7
  rand int unsigned box[N][N];
 
  constraint row_con {
    foreach ( box[row,] ) { // for each row,
      unique { box[row] };  // column values must be unique    }
  }

Column constraints

Constraining the boxes on the same column requires a little more work. This is because we cannot do something like this with unique:

foreach ( box[,col] ) { unique { box[][col] }; } // this doesn't work

Instead, we will use a “helper” array (we call it column) that transposes the row into column like this diagram.

Indexes of column[N][N] Array

After transposing the array, we use the “unique” like we did before (line 11).

1
2
3
4
5
6
7
8
9
10
11
12
13
  local rand int unsigned column[N][N]; // helper array
 
  constraint row_to_column { // set the values of helper array
    foreach ( column[col,row] ) {
      column[col][row] == box[row][col]; // transpose
    }
  }
 
  constraint column_con {
    foreach ( column[col,] ) { // for each column,
      unique { column[col] };  // row values must be unique    }
  }

Block constraints

Similar to the column constraints, we will use another helper array (called block) to map the row into block like this diagram.

Indexes of block[N][N] Array

The mapping constraint is a little complicated (line 5). After mapping the array, we use “unique” to make the values in the block unique. Note that the loc loop variable indicates the location of box within the block.

1
2
3
4
5
6
7
8
9
10
11
12
13
  local rand int unsigned block[N][N]; // helper array
 
  constraint row_to_block { // set the values of helper array
    foreach ( block[blk,loc] ) {
      block[blk][loc] == box[(blk/M)*M+loc/M][(blk%M)*M+loc%M]; // mapping    }
  }
 
  constraint block_con {
    foreach ( block[blk,] ) { // for each block,
      unique { block[blk] };  // values in the block must be unique    }
  }

Sudoku class

Here is the full list of the new Sudoku class.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class sudoku#( int M = 3 ); // M >= 1
  localparam N = M * M;
  local int unsigned puzzle[N][N];
  rand  int unsigned box   [N][N];
 
  // helper arrays
 
  local rand int unsigned column[N][N];
  local rand int unsigned block [N][N];
 
  // The value of each box must be between 1 and N.
 
  constraint box_con {
    foreach ( box[row, col] ) {
      box[row][col] inside { [ 1 : N ] };
    }
  }
 
  // The boxes on the same row must have unique values.
 
  constraint row_con {
    foreach ( box[row,] ) { // for each row,
      unique { box[row] };  // column values must be unique    }
  }
 
  // The boxes on the same column must have unique values.
 
  constraint row_to_column { // set the values of helper array
    foreach ( column[col,row] ) {
      column[col][row] == box[row][col]; // transpose
    }
  }
 
  constraint column_con {
    foreach ( column[col,] ) { // for each column,
      unique { column[col] };  // row values must be unique    }
  }
 
  // The boxes in the same MxM block must have unique values.
 
 
  constraint row_to_block { // set the values of helper array
    foreach ( block[blk,loc] ) {
      block[blk][loc] == box[(blk/M)*M+loc/M][(blk%M)*M+loc%M]; // mapping
    }
  }
 
  constraint block_con {
    foreach ( block[blk,] ) { // for each block,
      unique { block[blk] };  // values in the block must be unique    }
  }
 
  // The box must have the same value as the puzzle's if specified (!=0).
 
  constraint puzzle_con {
    foreach ( puzzle[row, col] ) {
      if ( puzzle[row][col] != 0 ) {
        box[row][col] == puzzle[row][col];
      }
    }
  }
 
  // Sudoku solver
 
  function int solve_this( int unsigned puzzle[N][N] );
    this.puzzle = puzzle;
    return this.randomize();
  endfunction: solve_this
 
  // Print the solution.
 
  function void print();
    for ( int i = 0; i < N; i++ ) begin
      if ( i % M == 0 ) $write( "\n" );
      for ( int j = 0; j < N; j++ ) begin
        if ( j % M == 0 ) $write( " " );
        $write( "%3d", box[i][j] );
      end
      $write( "\n" );
    end
  endfunction: print
 
endclass: sudoku

If you look at the original sudoku class in the previous article, the new constraints are not as simple as expected. I prefer the original constraints because it does not need the helper arrays, but either style should work.

EDA Playground

You can view and run the code on EDA Playground as usual.

Leave a Reply