SystemVerilog Sudoku Solver
Sudoku is a logic-based counting game, where the objective is to fill a grid with numbers such that each column, row, and block contain each number exactly once. Normally, Sudoku uses a 9-by-9 grid, but variants exist of smaller and larger grid sizes.
Since Sudoku is a static puzzle, it is simple to implement using the constraint solver in SystemVerilog.
To define some terms, where M-by-M are the dimensions of each the block and N-by-N are the dimensions of the overall grid.
- Element – a single box in the overall puzzle
- There are a total of N*N elements
- Row – a horizontal group of N elements
- There are N rows per puzzle
- Column – a vertical group of N elements
- There are N columns per puzzle
- Block – an M-by-M square of elements
- There are M*M blocks per puzzle
Below shows an example Sudoku with M = 3 (and N = 9).
row
↓
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3 ← column
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| ← element
+-----+
3 4 5 6 7 8 |9 1 2|
6 7 8 9 1 2 |3 4 5| ← block
9 1 2 3 4 5 |6 7 8|
+-----+
Sudoku Constraints
The constraints are as follows:
- Each element can only contain numbers between 1 and N
- Each element in a row must be unique
- Each element in a column must be unique
- Each element in an M-by-M block must be unique
Sudoku Class
Let’s start with some boiler-plate code to create the class. The sudoku class contains a parameter M – which is the width and height of each block, as well as the number of blocks per row and column in the puzzle. The N parameter is the number of possible digits, the number of elements in each row, the number of elements in each column, and the number of elements in each block.
The puzzle 2-D array is the input puzzle passed in by the constructor. Elements that are non-zero are copied to the solved puzzle row as known values by the c_puzzle constraint. Elements that are zero will be solved during randomization.
The print function will print the solved puzzle, row.
class sudoku #(int M = 3);
// Number of elements per row/col/block
localparam N = M*M;
// Input puzzle
local int puzzle [N][N];
// Randomized variable for the solved puzzle
local rand int row [N][N];
// Constraint to fill in the solved puzzle with non-zero elements of the input
constraint c_puzzle {
foreach (puzzle[r,c]) {
if (puzzle[r][c] != 0) {
row[r][c] == puzzle[r][c];
}
}
}
// Constructor with puzzle passed in
function new (int puzzle [N][N]);
this.puzzle = puzzle;
endfunction : new
// Print the solved puzzle
function void print ();
foreach (row[r,]) begin
if (r % M == 0) $write("\n");
foreach (row[,c]) begin
if (c % M == 0) $write(" ");
$write("%3d", row[r][c]);
end
$write("\n");
end
endfunction : print
endclass : sudoku
And here is the corresponding program to run it. Notice the parameterized sudoku class to set the dimensions. Here, the input puzzle is uninitialized, which will implicitly set each value to 0.
In the initial block, the sudoku object s is created, randomized, and if randomization succeeds it will print the solved puzzle.
program p;
localparam M = 3, N = M*M;
int puzzle[N][N];
sudoku #(M) s;
initial begin
s = new(puzzle);
if (s.randomize()) s.print();
else $display("cannot solve puzzle");
end
endprogram : p
Constraint 1: Per-element uniqueness
Now let’s start working through the constraints. The first one is easy – we just need to ensure that each digit is between 1 and N*N. This is done through the inside operator.
constraint c_value {
foreach (row[r,c]) {
row[r][c] inside { [1:N] };
}
}
With just the c_value constraint, the output could be something as follows. YMMV, based on the constraint solver and starting seed.
2 9 2 7 1 1 9 2 5
5 1 2 1 2 5 1 1 1
4 9 6 3 8 1 9 6 2
5 5 4 5 6 9 8 5 2
8 7 7 1 4 7 7 5 2
2 6 5 8 5 2 6 8 2
3 1 5 3 3 8 1 7 3
2 8 6 4 4 9 3 8 9
9 4 7 2 3 5 4 2 6
Constraint 2: Per-row uniqueness
The second constraint ensures that each element of a row is unique, which is done through the unique operator. Notice that the foreach loop is only looping over the rows in row.
constraint c_row {
foreach (row[r,]) {
unique { row[r] };
}
}
By adding this constraint, the resulting output could be as follows. Notice that each row has the numbers 1 through 9 in them without repeating. The columns and blocks are not necessarily unique yet, since those constraints have not yet been added.
9 2 4 8 1 7 5 6 3
7 8 6 2 9 4 3 5 1
9 8 6 3 2 5 4 7 1
4 9 7 5 1 6 8 3 2
5 3 4 8 2 7 6 9 1
4 2 5 7 1 9 6 8 3
9 2 8 3 5 6 1 4 7
7 5 9 8 2 4 1 6 3
2 7 5 8 9 4 1 6 3
Constraint 3: Per-column uniqueness
The third constraint requires that each element of a column is unique. Because SystemVerilog does not allow passing in something like row[,c] to unique in a constraint, we’ll create a helper random array column that will contain the transpose of the row view via the c_row_to_column constraint, then each “row” of column is constrained to be unique through c_column.
local rand int column [N][N];
constraint c_row_to_column {
foreach (row[r,c]) {
column[c][r] == row[r][c];
}
}
constraint c_column {
foreach (column[r,]) {
unique { column[r] };
}
}
The output from the constraints so far could result in an output of the following, which guarantees each element in a row is unique through c_row, and each element in a column is unique through c_column.
6 3 1 4 5 2 9 7 8
2 7 4 5 8 1 6 9 3
5 4 6 8 3 7 2 1 9
7 8 2 6 1 9 5 3 4
4 6 8 9 7 3 1 2 5
1 2 5 3 9 6 4 8 7
9 5 7 2 6 8 3 4 1
3 1 9 7 2 4 8 5 6
8 9 3 1 4 5 7 6 2
Constraint 4: Per-block uniqueness
The fourth constraint mandates that each N-by-N block have unique elements. As with before, a helper array (block) will be created that puts each block into a separate row of a 2-D array. Then, unique will be called on each row of this view.
local rand int block [N][N];
constraint c_row_to_block {
foreach (row[r,c]) {
block[r][c] == row[(r/M)*M+c/M][(r%M)*M+c%M];
}
}
constraint c_block {
foreach (block[r,]) {
unique { block[r] };
}
}
The magic math to convert the row view into the block view is simply choosing which element to put into the new view. For example:
block[0][0] = row[(0/3)*3+0/3][(0%3)*3+0%3] = row[0+0][0+0] = row[0][0]
block[0][1] = row[(0/3)*3+1/3][(0%3)*3+1%3] = row[0+0][0+1] = row[0][1]
block[0][2] = row[(0/3)*3+2/3][(0%3)*3+2%3] = row[0+0][0+2] = row[0][2]
block[0][3] = row[(0/3)*3+3/3][(0%3)*3+3%3] = row[0+1][0+0] = row[1][0]
block[0][4] = row[(0/3)*3+4/3][(0%3)*3+4%3] = row[0+1][0+1] = row[1][1]
block[0][5] = row[(0/3)*3+5/3][(0%3)*3+5%3] = row[0+1][0+2] = row[1][2]
block[0][6] = row[(0/3)*3+6/3][(0%3)*3+6%3] = row[0+2][0+0] = row[2][0]
block[0][7] = row[(0/3)*3+7/3][(0%3)*3+7%3] = row[0+2][0+1] = row[2][1]
block[0][8] = row[(0/3)*3+8/3][(0%3)*3+8%3] = row[0+2][0+2] = row[2][2]
block[1][0] = row[(1/3)*3+0/3][(1%3)*3+0%3] = row[0+0][1+0] = row[0][3]
block[1][1] = row[(1/3)*3+1/3][(1%3)*3+1%3] = row[0+0][1+1] = row[0][4]
block[1][2] = row[(1/3)*3+2/3][(1%3)*3+2%3] = row[0+0][1+2] = row[0][5]
block[1][3] = row[(1/3)*3+3/3][(1%3)*3+3%3] = row[0+1][1+0] = row[1][3]
block[1][4] = row[(1/3)*3+4/3][(1%3)*3+4%3] = row[0+1][1+1] = row[1][4]
block[1][5] = row[(1/3)*3+5/3][(1%3)*3+5%3] = row[0+1][1+2] = row[1][5]
block[1][6] = row[(1/3)*3+6/3][(1%3)*3+6%3] = row[0+2][1+0] = row[2][3]
block[1][7] = row[(1/3)*3+7/3][(1%3)*3+7%3] = row[0+2][1+1] = row[2][4]
block[1][8] = row[(1/3)*3+8/3][(1%3)*3+8%3] = row[0+2][1+2] = row[2][5]
...
This results in a Sudoku puzzle creator that will generate valid puzzles with an empty puzzle input.
1 7 3 5 4 8 6 9 2
8 5 9 2 3 6 1 7 4
6 4 2 1 7 9 3 8 5
7 3 6 8 1 4 2 5 9
5 1 8 3 9 2 7 4 6
9 2 4 7 6 5 8 3 1
2 8 1 9 5 3 4 6 7
4 9 7 6 8 1 5 2 3
3 6 5 4 2 7 9 1 8
Results
And of course, the input puzzle in the program can be initialized to solve a puzzle.
initial begin
puzzle = '{
'{ 5,3,0, 0,7,0, 0,0,0 },
'{ 6,0,0, 1,9,5, 0,0,0 },
'{ 0,9,8, 0,0,0, 0,6,0 },
'{ 8,0,0, 0,6,0, 0,0,3 },
'{ 4,0,0, 8,0,3, 0,0,1 },
'{ 7,0,0, 0,2,0, 0,0,6 },
'{ 0,6,0, 0,0,0, 2,8,0 },
'{ 0,0,0, 4,1,9, 0,0,5 },
'{ 0,0,0, 0,8,0, 0,7,9 }
};
s = new(puzzle);
if (s.randomize()) s.print();
else $display("cannot solve puzzle");
end
Running this solves the puzzle shown on Wikipedia.
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
Of course, the M parameter can be changed to form smaller or larger puzzles. An M of 4 with a blank puzzle could generate a puzzle like so:
12 5 14 9 16 11 6 8 13 10 7 4 3 15 2 1
7 8 13 2 10 15 12 3 9 11 1 14 4 16 5 6
3 15 11 16 13 14 1 4 5 12 6 2 9 7 8 10
10 1 4 6 7 2 5 9 15 16 3 8 13 11 14 12
5 10 2 13 14 7 15 6 12 8 11 16 1 9 4 3
8 7 9 15 5 4 16 2 1 13 10 3 6 12 11 14
4 16 12 1 8 3 9 11 7 2 14 6 15 13 10 5
14 6 3 11 1 13 10 12 4 5 15 9 7 8 16 2
6 11 8 5 4 10 3 1 16 15 13 7 2 14 12 9
9 14 7 12 2 8 13 5 3 6 4 11 10 1 15 16
15 13 16 4 9 12 14 7 2 1 5 10 11 6 3 8
2 3 1 10 6 16 11 15 14 9 8 12 5 4 7 13
1 4 6 14 12 5 2 10 11 7 16 13 8 3 9 15
16 9 5 7 15 6 4 14 8 3 2 1 12 10 13 11
13 2 10 3 11 9 8 16 6 4 12 15 14 5 1 7
11 12 15 8 3 1 7 13 10 14 9 5 16 2 6 4
While an M of 2 would result in something simpler such as:
2 1 4 3
3 4 1 2
4 2 3 1
1 3 2 4
Puzzles too large will result in very long simulation run times, since the number of elements that need to be constrained by the solver grow with M.
The code for the Sudoku solver is published to EDA Playground: Sudoku Solver
This post was inspired by the following tutorial from Clue Logic.