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

Keisuke Shimizu

Last Updated on July 2, 2017

This is a sequel to my old article about solving Sudoku. Last time, someone asked a question about using the “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 sounded promising, so I gave it a try. This method requires more steps than the original “sudoku” class. In this article, I’m going to replace the three constraints (row_con, column_con, and block_con) in the previous article with the constraints below.

Row constraint

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

Indexes of a box[N][N] Array

Line 5 makes the column values in 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 boxes in the same column requires a little more work. This is because we cannot do the following 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 a column like this diagram.

Indexes of a column[N][N] Array

After transposing the array, we use “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 a block like this diagram.

Indexes of a 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 the 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

Compared to the original “sudoku” class in the previous article, the new constraints are not as simple as expected. As stated in the introduction, I still prefer the original constraints because it does not need the helper arrays, but either method should work.

EDA Playground

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

2 thoughts on “Hidden Gems of SystemVerilog – 4. Solving Sudoku with Uniqueness Constraints”

Leave a Reply

Your email address will not be published. Required fields are marked *