# A Bluespec Hardware Implementation of Sudoku

**Introduction**

You might be asking, "Why would anyone create a hardware implementation of Sudoku?" Or even, "What does this have to do with me and what I do?" The simple answer is that we wanted a fun, thought-provoking demo. While this Sudoku implementation is a novelty of sorts, though a very complex one, it nicely illustrates how Bluespec's ESL Synthesis technology effectively tackles key, contemporary System-on-Chip (SoC) development issues:

- How to test software early with accurate hardware representations
- How to create intellectual property (IP) blocks that enable extreme reuse because they are highly parameterized and flexible to change
- How to quickly implement designs that contain both extremely complex algorithms and complex concurrency, especially those with convoluted control logic and numerous shared resource hazards (it is often assumed that dealing with high complexity is only feasible in software)

This article describes BluDACu, a Bluespec parameterized hardware implementation of Sudoku, including both puzzle generation and puzzle solving. All this is made possible because of BSV's high level of abstraction, powerful types and strong static verifications, clean semantics based on atomic transactions (Rules) and atomic-transactional (Rule-based) Interfaces, and automatic regeneration of correct control logic as we substitute one component with another.

**BluDACu Overview**

You are probably familiar with the game of Sudoku. If not, one resource is the Wikipedia entry: Sudoku. Nowadays Sudoku puzzles seem to be offered in many daily newspapers, magazines and books, and there are also several Sudoku sites on the web. The initial setup and the challenge are simply described. You are given a 9x9 grid of cells, which can be further regarded as a 3x3 grid of boxes, each of which is a 3x3 grid of cells. Some of the cells are already filled in, the rest are blank. The challenge is to fill in all the cells, where each cell contains a symbol (1-9), such that each 9-cell row, each 9-cell column, and each 3x3-cell box contains exactly one occurrence of each symbol 1 through 9. A legal puzzle must have exactly one solution so that, in principle, it can be solved by pure reasoning, i.e., without any "guessing".

The usual 9x9 puzzle can be regarded as a special case of N x N puzzles, where N is a square. We refer to the 9x9 puzzle as "order 3", and you could also have "order 2" (4x4 cells with 2x2 boxes and using symbols 1-4), "order 4" (16x16 cells with 4x4 boxes and using symbols 1-9,A-G), and so on.

BluDACu is a parameterized hardware implementation of the game of Sudoku. The "order" of the puzzle is a parameter to the design, so that the same source code can be used for size 2x2, 4x4, 9x9, 16x16, and so on. The implementation includes a puzzle generator, a puzzle solver, and a software-based GUI front-end to control the hardware and display the game for human play. The following is a block diagram outlining the architecture of these components:

The implementation was done using Bluespec SystemVerilog (BSV) " alternatively, it could have been done using Bluespec's ESE SystemC, which has the same notion of atomic transactions (Rules) and atomic-transactional interfaces. The core of the design, the Sudoku generator and solver, and part of the surrounding testbench are in BSV. The testbench makes calls to C functions using BSV's DirectC interface " the BSV design and embedded C can be run at BSV source level using Bluesim, or at the RTL level, in Verilog, using standard Verilog simulators. The BSV-generated Verilog can be further synthesized into FPGA or ASIC netlists, and run on an FPGA or in ASIC silicon.

**The general approach used in BluDACu**

The Sudoku solver was purposely developed to mimic the way a human solves the puzzle, so that we can provide the human player with meaningful assistance if he requests a hint—e.g., instead of just magically filling in the solution symbol for a blank cell, we can describe the reasoning process that solves that cell. Further, this structure also allows us to tune the level of difficulty of the generated puzzles.

Our solver does not use "backtracking", which is one of the "easy" ways to write a Sudoku solver in software, i.e., at each step, one could "guess" the solution for a blank cell and proceed, possibly realizing after many steps that the guess was wrong because it leads to an inconsistency. Such a solver would require saving the state of the grid at this "guess point", so that if the guess turned out be wrong, it could backtrack, or restore the grid state to this guess point, and make a different guess. Of course, after making one guess it may be necessary to guess again for some other cell, and so on, so that at some point one may be "nested" in several levels of guesses. Such a solver needs no further intelligence—it is a kind of "brute force" search of the solution space. This is easy to do in software, but humans typically do not employ this approach, since backtracking is hard to do with pencil on a folded newspaper while hanging on to a strap on the morning bus or subway! Further, in such a solver, it is not easy to provide a meaningful hint to the player at any intermediate point, i.e., a focused hint about how to solve a particular cell.

Finally, a backtracking solver would be very bad for hardware implementation. It would need much memory to save all the grid states at all the pending guess points, and it might consume a lot of power.

Instead, BluDACu works like a human solver, repeatedly employing a tactic chosen from a repertoire of tactics (a "bag of tricks"). Each successful application of a tactic makes concrete progress by solving one cell. An example of a simple tactic applied to a particular cell is:

Tactic *elim_other_singletons*: Eliminate as possibilities all symbols from this cell that already appear as the solution to any other cell in the same "constraint group" (same row, same column, or same box).

Said in a reverse way, if you've already solved a cell, eliminate it as a possibility from all other cells in the same row, column or box. A more complex tactic:

Tactic *repeated_2_set*: If, in a constraint group (row, column, box) of this cell A, two other cells B and C contain the same "2-set" { *j, k* }, i.e., symbols *j* and *k* are the only remaining possibilities in cells B and C, then *j* and *k* can be eliminated from this cell A (because *j* and *k* must be in the cells B and C, even though we may not yet know which one goes where).

By repeatedly applying each tactic to each cell in the grid, and to each of the cell's containing constraint groups (row, cell, box), steady progress is made until the puzzle is solved. Note that there is no guarantee that the repertoire of tactics is "complete", i.e., that they are capable of solving *any* Sudoku puzzle. The stronger the tactics, the more difficult the puzzle that can be solved. BluDACu's tactics succeed on many puzzles found in newspapers, books and web sites, including those that are labeled by their authors as "hard", "difficult", "evil", etc. (You will also see in the discussion below how easy it is to add a new tactic to the solver, when you discover one.)

**Expressive and parameterized data types**

The file Sudoku.bsv contains declarations for a number of the parameterized data types used in the solver. For example:

typedef Bit#(TSquare#(order)) Cell#(numeric type order);

defines the type *Cell#(O)*, the representation of a cell in an order *O* puzzle, to be a bit-vector of *O ^{2}* bits. For example, in an order 3 puzzle, each cell has 9 bits. This encodes which values are possible candidates for that cell. When a value is ruled out at a particular cell location, its corresponding bit is cleared. When only one bit remains set in the mask for a cell, the value of that cell has been determined (solved). The declaration:

defines the type *Grid(nr,nc,t)* as a vector or *nr* rows containing a vector of *nc* columns containing items of some type *t*. By parameterizing in this way, the type can be reused in various ways. For example, the declaration:

defines the type of the "state" for the Sudoku solver of order *O—* it is a *Grid* with *O ^{2}* rows and

*O*columns of registers (type

^{2}*Reg#()*), where each register contains a

*Cell*value (bit vector of

*O*bits). But the

^{2}*Grid*type can also be used to represent the abstract

*values*in the Suduko grid:

**Grid#(TSquare#(order), TSquare#(order), Cell#(order))**

i.e., here the values in the grid are just *Cell* values, not registers. Or,

**Grid#(order, order, Cell#(order))**

can be used to represent the values in a box (e.g., a 3x3 box in a 9x9 puzzle). Similarly:

**typedef Vector#(TSquare#(order), Cell#(order)) Group#(numeric type order);**

defines *Group(O)* as a parameterized type that is a vector of *O ^{2}* cells. It can be used to refer to the values in a row, column, or box of cells, each of the three kinds of "constraint groups". By parameterizing our tactics in terms of

*Groups*, the same tactic can be used on rows, columns or boxes.

This level of parameterization is made possible by Bluespec SystemVerilog and is not practical in legacy RTL languages. The "order" parameter controls the size of the puzzle. In general, an order *O* puzzle contains *O ^{4}* cells arranged in an

*O*grid and each of the

^{2}xO^{2}*O*rows, columns and boxes contains the symbols 1 through

^{2}*O*. Thus, an order

^{2}*O*puzzle requires

*O*bits of state! You see some hint of these "constraint" relationships (which you can think of as formal assertions) in the use of phrases like

^{6}*TSquare()*in the above examples.

The files SolveTest2.bsv and SolveTest3.bsv contain small unit-level testbenches for solvers of order 2 (4x4) and 3 (9x9), respectively. In those files, you'll see lines like

**SudokuSolver#(2) solver <->**

and

**SudokuSolver#(3) solver <->**

respectively. This simple, single-parameter change, from 2 to 3, automatically adjusts a lot of generated hardware circuitry, including:

The bit-width of each cell value and cell register

The number of cell registers in each row and column

The width of arguments and results in the various interfaces

The scope of all of the functions for accessing and modifying Sudoku grids

The logic for each tactic

The number of tactic applications

The sequence of states in the solver FSM

The sequence of states in the generator FSM

The logic to place a given solved value somewhere in the grid

and so on.

In other words, formal constraints like *TSquare()* are exploited by the BSV synthesizer to produce all the logic correctly sized for each order *O* of puzzle. This correct-by-construction generation of datapath and control logic eliminates a large source of bugs encountered in legacy RTL.

post a commentregarding this story.