Hidden Gems of SystemVerilog – 3. Solving Sudoku

A few people (Chris Drake, Tudor Timi, and anilraj) have already solved Sudoku using SystemVerilog. So, I am not the first one, but I can’t resist doing it because it sounds a lot of fun! I tried not to look at other people’s solutions and to code it easy-to-understand in mind. For those of you who don’t know about Sudoku, please see this.

Constraints

Solving Sudoku in SystemVerilog is nothing but specifying the rules with constraints. There are five constraints.

Sudoku Parameters
Sudoku Constraints

Box constraints

The value of each box must be between 1 and N, where N is M*M. See the figure above for the definition of M. For the typical 9×9 Sudoku, N is 9.

Row constraints

The boxes on the same row must have unique values.

Column constraints

The boxes on the same column must have unique values.

Block constraints

The boxes in the same MxM block must have unique values.

Puzzle constraints

A Sudoku puzzle to solve is given by an NxN array. The box must have the same value as the puzzle’s if the value is specified (zero represents a blank box). If the puzzle array has all-zero values, there are no puzzle constraints. In this case, a new Sudoku puzzle will be created.

Sudoku class

Here is the full list of the Sudoku class. See how the five constraints are defined in the class. The solve_this (line 64; note solve is a SystemVerilog keyword) is the main solver function. Simply randomizing this class will give us a solution (if it exists). The print function pretty-prints the solution.

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
class sudoku#( int M = 3 ); // M >= 1
  localparam N = M * M;
  local int unsigned puzzle[N][N];
  rand  int unsigned box   [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, colA] ) {
      foreach ( box[   , colB] ) {
        if ( colA != colB ) { 
          box[row][colA] != box[row][colB];
        }
      }
    }
  }
 
  // The boxes on the same column must have unique values.
 
  constraint column_con {
    foreach   ( box[rowA, col] ) {
      foreach ( box[rowB,    ] ) {
        if ( rowA != rowB ) {
          box[rowA][col] != box[rowB][col];
        }
      }
    }
  }
 
  // The boxes in the same MxM block must have unique values.
 
  constraint block_con {
    foreach   ( box[rowA, colA] ) {
      foreach ( box[rowB, colB] ) {
        if ( rowA / M == rowB / M && 
             colA / M == colB / M && 
             ! ( rowA == rowB && colA == colB ) ) {
          box[rowA][colA] != box[rowB][colB];
        }
      }
    }
  }
 
  // 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

Solving a puzzle

I created a sample puzzle shown below.

Sample Sudoku
Sample Sudoku Puzzle

An array literal specifies the puzzle (line 8). Then, the top module calls the solve_this function (line 20).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
module top;
  parameter  M = 3;
  localparam N = M * M;
  int unsigned puzzle[N][N];
  sudoku#( M ) s;
 
  initial begin
    puzzle = '{ '{ 0,2,3, 4,0,6, 7,8,0 }, // 0: blank box
                '{ 4,0,6, 7,0,9, 1,0,3 },
                '{ 7,8,0, 0,2,0, 0,5,6 },
 
                '{ 2,3,0, 0,6,0, 0,9,1 },
	        '{ 0,0,7, 8,0,1, 2,0,0 },
		'{ 8,9,0, 0,3,0, 0,6,7 },
 
                '{ 3,4,0, 0,7,0, 0,1,2 },
                '{ 6,0,8, 9,0,2, 3,0,5 },
                '{ 0,1,2, 3,0,5, 6,7,0 } };
    s = new;
    if ( s.solve_this( puzzle ) ) s.print();
    else $display( "cannot solve the puzzle" );
  end
endmodule: top

You should see the solution like this when you run.

   1  2  3   4  5  6   7  8  9
   4  5  6   7  8  9   1  2  3
   7  8  9   1  2  3   4  5  6
 
   2  3  4   5  6  7   8  9  1
   5  6  7   8  9  1   2  3  4
   8  9  1   2  3  4   5  6  7
 
   3  4  5   6  7  8   9  1  2
   6  7  8   9  1  2   3  4  5
   9  1  2   3  4  5   6  7  8

I hope this post won’t spoil fun of solving Sudoku 😉

EDA Playground

You can view and run the code on EDA Playground (If M=3 takes too long to run, try M=2).

7 thoughts on “Hidden Gems of SystemVerilog – 3. Solving Sudoku”

  1. Hi KK,
    Never thought of sudoku using SV. This sounds fun. I am going to try this out myself and then go through your post.
    Thanks, Venky

  2. I don’t understand the need of the constraint written in lines 40 to 50 in your code.If we remove that constraint then also the outcome is same.

    1. Without block_con constraint, you might get an invalid solution like this:

         2  8  6   1  9  4   7  5  3
         6  2  7   9  5  3   4  1  8
         3  1  9   4  7  5   6  8  2
      
         9  6  8   3  2  7   5  4  1
         5  7  2   6  4  1   8  3  9
         1  9  4   8  3  6   2  7  5
      
         7  3  5   2  1  8   9  6  4
         8  4  1   5  6  9   3  2  7
         4  5  3   7  8  2   1  9  6
      
  3. Hi Keisuke, Really it sounds good!! I have never related SV constraints with solving sudoku. Finally SV helps me for non-technical thing. Thanks a lot for this article.

Leave a Reply