Me writing my sudoku solver

I have tried writing a Sudoku solver before, one completed using a very simple brute-force depth-first backtrack searcher in C++ for an university assignment, another using a constraint based depth-first searcher in Clojure, in common lisp, etc, in-completed.

The simple brute-force was elegant, efficient and does the job, however, I have thought about how I myself solves the sudoku when I see it right in front of me, I want to make a program that solve the sudoku that way. This is the main motivation with this program, and there are two main goals behind this attempt:

1. to see to myself finishing a project from start to finish
2. to challenge myself, to complete something that I hadn't completed individually yet and with sudoku it isn't something too difficult that I would give up mid-way like many times before.

First of all, a data-structure is needed to hold the representation of a sudoku board in memory. In this case it's trivia to select a 2d array. In other more complicated computer problems, choosing and implementing the right data-structure will often help facilitate progress rather than hinder it, and choosing poorly will cause hindrance.

Anyhow, with a 2d array, the rows of a sudoku can be accessed with O(1) time. Accessing the columns is requires a bit more work. Although these matters less compared to the algorithm as because accessors for rows and columns are effectively function calls and the cost of the function in this case being row is both faster and cheaper can be optimized later on.

Moving onto the algorithm side, the program will start looking at one position at a time. For a position (i,j) it will look into the i-th row and j-th column and starts filtering down the possible candidates from there.

Normally, I would use a set to represent the combination of unique numbers from the row and column, for instance, in table of numbers we see what the set of numbers are existing in row0 then in col0 (column 0), in the third table row it shows what's the combined set of row 0 and column 0. The last table row showing the missing numbers from the combined set.

Table 1: Numbers table

PLACE	SET OF NUMBERS
row0	(1 2 3 4 5 6 7 8 9)
col0	(1 2 3 4 5 6 7 8 9)
row0 + col0	(1 2 3 4 5 6 7 8 9)
what's missing	NIL

Set is a good tool for holding the data I need. However, I wanted to try something different this time, with compactness in mind. The problem space here is, a way to encode the state of a row, column and region (sub-grid), given that each number from 1 to 9 are either present or missing. After some time I realized bit-mask is the right tool for this, what's better is that, there are boolean operation that helps combining two encodings. I settled with 1 as missing and 0 as present because of overlooked the operation "binary nor" and "binary and" only works with the chosen schema.

(

NOTE: binary mask works different in Common Lisp, they are called bit-vectors, essentially a vector or 1d array that holds only bits (either 1 or 0)

They have a literal syntax of for instance #*1111, which you may think of as 0b1111 in equivalence of binary number system, then going forward with the examples to illustrate the different between common-lisp "binary mask" (bit arrays) is that for instance, #*1100 is the same as 0b0011 not 0b1100 as you might have thought. In other words, the bit array are counting from the left most, or that the left most digit is the least significant bit, as contrary to the binary number system where 0b001 has a 1 in its least significant bit since it counts from the right most.

now with a simple table at common lisp bit array table to finish this all off.

)

Bit array	in Binary	in Decimal
#*1100	0b1100	12
#*0011	0b0011	3

Coming back to the sudoku at hand, let's say there is an encoding of #*111000000 this would represent 1,2,3 are missing and the rest are present for any particular region, row, column or all three combined.

PLACE	SET OF NUMBERS	ENCODING (inverted)
row0	(1 2 3 4 5 7 8)	#*111110110
col6	(2 3 4 7)	#*011100100
first region	(1 2 4 7 8)	#*110100110
row0 + col0	(1 2 3 4 5 7 8)	#*111110110

let's say i is 0 and j is 6 and we get the following encoding:

The encoding translate back into the possible candidates for this position which are (counted from the LSB as 1):

6,

9

My solver started to step through the sudoku and filling in the numbers in their respective positions. But then it halted at step 10

Stepping through the sudoku puzzle once more and this time we stopped at step 23.

Looking at the message it tells me the solver is unable to find a position with any candidates. Looking at the board right now, I see this is because there are some contradicting numbers placed onto the board.

For instance, the 6 at (0 . 6) should have been a 9 instead. But why did the program decide to put that 6 there. Back to the encodings:

Name	encoding
row	#*000001001
column	#*100011011
region	#*001011001
combined	#*000001001
numbers	6, 9

This tells me the newly added logic that took advantage of the information/numbers from the other lanes has mis-lead the program. Because for (0 . 6) and (0 . 8) either could have put a 6 or 9 down, but due to design of the searcher that simply goes column first then onto the next row meant that (0 . 6) got filled with a 6.

Time to revise the searcher from positional to regional. The searcher should take into account of the impact of a conflicting choices, which tend to happen to spots within the same row, column or region. Instead of computing for one position at a time, the searcher should compute for 3 rows, 3 columns and 1 region.

I thought to myself the best way to approach this is to start with a regional view, where we will consider the problem for all three rows, three columns and one single region.

From here the new algorithm is as follows:

• Start from one region, typically starts from region X, where X can be anything from 0 to 8
• Within region X, there are Y number of empty positions, and Z number of empty positions that has a mask with only 1 bit asserted
• there are Y number of masks for each of the empty position, where Y satisfy 0 < Y < X.
• From the Y masks there are Z number of masks with only 1 bit asserted
• Finally, those Z masks are translated back into the integer to fill back into the Sudoku board.

With the algorithm detailed above implemented after stepping through the program a couple times the Sudoku board is finally solved