Thursday, October 16, 2008

Regarding Sudoku.sv

Probably everybody's favorite constraint satisfaction problem is Sudoku, a fun yet irritating game that has about 10,000 books dedicated to it at Borders. I find the SystemVerilog solution to be particularly elegant.

For the rare uninitiated, the game is played on a 9x9 square. Entries are integers between 1 and 9. All column and row entries must be unique. Furthermore, the 9x9 square is further subdivided into 9 3x3 squares, and the entries of each 3x3 square must be unique.

Truthfully, the game can be further generalized into an NxN version (N >= 3), but the most convenient way to do that with SystemVerilog seems to be by using a template, and my current VCS version doesn't support templates.

This program has two modes. You can either use the solver to solve a specific puzzle, or you can just have the solver generate a random Sudoku table. Let's say you want to solve the following board, where zeros indicate empty spaces:

000 080 014
061 000 500
700 090 300

004 902 008
000 000 000
900 805 400

007 010 006
008 000 140
130 060 000

Save this table into a file called "table", and run simv.

To compile with vcs:
vcs -sverilog Sudoku.sv
To run:
./simv
Example output (using above):
+---+---+---+
|293|586|714|
|461|327|589|
|785|194|362|
+---+---+---+
|314|972|658|
|852|641|937|
|976|835|421|
+---+---+---+
|547|213|896|
|628|759|143|
|139|468|275|
+---+---+---+

No comments: