First, if you are not in the know, here's what is Sudoku?

Sudoku board is, typically, a 9X9 matrix of integers. Its property is that every row, every column, and every one among the nine 3X3 blocks consist integers 1 through 9 exactly once, no repeats. Sudoku puzzle is a partially filled-in Sudoku board that can only be completed in one way. The game is to extend the puzzle to its unique board.

Sudoku puzzles are Constraint Satisfaction Problems. As opposed to optimizing for a value, what's needed is to reach a state where all constraints are obeyed.

Now the caveat

There are two classes of sudoku puzzles. First set of puzzles need guesses to be made to proceed, backtracking if a guess results in breaking a sudoku board rule. This is implementation of backtracking algorithm. The other class are puzzles solved by logic alone, no guessing and no backtracking. This is implementation of Arc Consistency algorithm.

Logic alone can solve Puzzle 1. Puzzle 2 needs guesses and backtracking.

Implementing Backtracking algorithm without VBA will be fun, I suspect excruciatingly so. But that's a DIY for another day. Lets solve the first class of puzzle today.

And here's how we'll solve it

• We begin with the first Element, say 1, and note cells in which 1 can be placed. That's only possible if the cell is empty in the original puzzle AND its in a row AND a column AND a block where 1 does not exist.

• After we've noted all cell where its possible, we fill cells with the 1 if it can be placed in only one cell of a row OR a column OR a block.

• Then we add these updates to the original puzzle and iterate same steps for next integer until 9 and loop back to 1 until we end up with the Sudoku board.

Fair warning: What's about to follow isn't for excel novices - but you'll do just fine with familiarity of Name Ranges , Array formulas and 4 Excel Functions: MMULT , INDEX , TRANSPOSE , SUM.

Contrastingly, you'll build familiarity with these functions as you follow along.

So, here's how I went about it. You can either download the file here and follow along or build on your own.

Download file here

#01/13: Set up worksheet

To begin, I created 16 Name Ranges of varying sizes (9X9 means 9 Rows X 9 Columns). It helped avoid cryptic cell referenced formulas.

1. Puzzle (9X9)
2. Element (1X1)
3. ArrayOfOnes (9X1)
4. StartCellIndex (9X1)
5. EndCellIndex (9X1)
6. EmptyCells (9X9)
7. ElementInPuzzle (9X9)
8. EmptyBlocks (9X9)
9. EmptyRows (9X1)
10. EmptyColumns (9X1)
11. ExclusiveCells (9X9)
12. ExclusiveBlocks (9X9)
13. ExclusiveRows (9X1)
14. ExclusiveColumns (9X1)
15. Board (9X9)
16. NextElement (1X1)

#02/13: Populate Puzzle

This was easy. I filled in sudoku puzzle into the range named Puzzle. Done.

• Puzzle = { 0,0,0,0,0,0,0,0,1; 0,0,0,0,0,0,0,2,3; 0,0,4,0,0,5,0,0,0; 4,0,0,1,0,0,0,0,0; 0,0,0,0,3,0,6,0,0; 0,0,7,0,0,0,5,8,0; 0,0,0,0,6,7,0,0,0; 0,1,0,0,0,4,0,0,0; 5,2,0,0,0,0,0,0,0 }

#03/13: Populate constant arrays

Easy as well. Constant arrays are used in calculations. So I filled these ranges:

• ArrayOfOnes = {1;1;1;1;1;1;1;1;1}
• StartCellIndex = {1;1;1;4;4;4;7;7;7}
• EndCellIndexrange = {3;3;3;6;6;6;9;9;9}
• Element= 1

#04/13: Update EmptyCells

I'll use EmptyCells range is a binary array to identify empty cells in the Puzzle: 1s where the puzzle is empty and 0s where its not. Puzzle=0 works just fine as an array of TRUE and FALSE indicators. Using two minus signs as prefix causes the formula to convert a return value of TRUE into 1 and FALSE into 0 which exactly what I need.

• EmptyCells = --(Puzzle=0)

#05/13: Update ElementsInPuzzle

This was an intermediate step needed to create EmptyRows, EmptyColumns and EmptyBlocks. I created an array to identify where the element 1 is placed in original puzzle. You can guess the formula is nearly identical to Step 04.

• ElementInPuzzle = --(Puzzle=Element)

#06/13: Update EmptyRows

Using ElementInPuzzle, I updated EmptyRows to identify rows where 1 is NOT placed. Visually you can see above that 1 is not placed in 2, 3, 5, 6, 7, and 9. So the array result must be {0;1;1;0;1;1;1;0;1}.

The easiest way of course is to sum each row of ElementsInPuzzle array, but that's 9 separate formulae and 9 separate scalar results. MMULT is more elegant.

• EmptyRows = 1-MMULT(ElementInPuzzle,ArrayOfOnes)

As an aside, MMULT (Matrix Multiplication) deserves its own post because practical all neural networks and deep learning techniques are one giant variation of Matrix Multiplications with activation functions adding non-linearities. I'll get to it soon.

In essence this formula multiplies the matrix ElementInPuzzle with vector ArrayOfOnes. I then flipped the signs by subtraction the product from 1 because I needed an array indicating rows where 1 did NOT appear.

#07/13: Update EmptyColumns

As you can imagine, this step is identical to Step 06. Except that to check on column, I had to transpose (tilt to right) 'ElementsInPuzzle'. Visually, we see Columns 1,3,5,6,7 and 8 don’t consist 1. So, our result must be {1;0;1;0;1;1;1;1;0} which exactly what I end up with this formula

• EmptyColumns = 1-MMULT(TRANSPOSE(ElementInPuzzle),ArrayOfOnes)

#08/13: Update EmptyBlocks

This was a fun step. Let revisit the ElementInPuzzle picture. Visually its easy to see that I needed 0s in top right, middle center and bottom left blocks because they all consist the Element. Its also easy to create this array if I use a separate formula for each block, therefore 9 formulas. But I wanted a unified formula for the entire matrix. So, here’s my implementation.

• EmptyBlocks = --(0=SUM (INDEX(ElementInPuzzle,StartCellIndex,TRANSPOSE(StartCellIndex)) :INDEX(ElementInPuzzle,EndCellIndex,TRANSPOSE(EndCellIndex))))

Good news is that the formula works. Unfortunately, you don't end up with an array with this implementation. So forget about nesting this formula into other formulas. Also, because this formula refers to a range in worksheet, there’s no way to use it on a “virtual” array. I feel like I’ve pushed excel to its absolute limit on this task.

So briefly elated and also mildly disappointed, I moved on.

#09/13: Update ExclusiveCells

So, again this is an array of cells where 1 could be filled. Its not cells where 1 must be filled.

I had now created EmptyCells, EmptyRows, EmptyColumns and EmptyBlocks. If a cell was zero in any of those arrays, then 1 cannot be filled in that cell. Conversely, the a particular cell was TRUE (or 1) in all 4 arrays, then it could be filled without breaking any sudoku rule. I implemented it the only way it should be done.

• ExclusiveCells = EmptyCells * EmptyBlocks * EmptyRows * TRANSPOSE(EmptyColumns)

#10/13: Update ExclusiveBlocks

This implementation is a identical of Step 08 except that this time we check if the sum of cells in block equals 1 instead of equaling 0.

• ExclusiveBlocks = --(1=SUM (INDEX(ExclusiveCells,StartCellIndex,TRANSPOSE(StartCellIndex)) :INDEX(ExclusiveCells,EndCellIndex,TRANSPOSE(EndCellIndex))))

#11/13: Update Board

I now had all ingredients to update our puzzle. If a cell is TRUE (1) in ExclusiveBlocks OR ExclusiveRows OR ExclusiveColumns AND if it is TRUE (1) in ExclusiveCells then that cell must be filled with the Element in Original Puzzle. Here’s the implementation.

• Board = --((ExclusiveRows + TRANSPOSE(ExclusiveColumns) + ExclusiveBlocks)>0) * ExclusiveCells * Element + Puzzle

#12/13: Update NextElement

I was nearly there. I had to fill the range NextElement with a formula to determine next element for which we’ll follow Step 01 to Step 11. Of course, the easy formula is IF(Element=9,1,Element+1). But I wanted to stick to Math operators rather than Logic Operators. So here’s the other formula:

• NextElement = (1-(--(Element=9)))*Element+1

#13/13: Time for Iterative Calculations

So Now I enabled iterative calculations and created the circular references to see the MAGIC Happen!

• I Enable Iterative calculations
• Navigate File > Options > Formulas
• Check “Enable iterative calculations“
• Set Maximum Iterations to 200
• Then Created a circular reference in Element range
• Element = NextElement
• Puzzle = Board

and BOOM! DISASTER!

This is not what I expected! I absolutely lost my mind over this for the next hour. Surely this must be an excel bug. Everything worked just as expected when I disabled iterative calculations. But, as soon as I turned it on, the spreadsheet went crazy.

I went about frantically searching web for somebody to assure me this was an excel bug. No answers. No mention of this problem.

And finally, it dawned on me. Location, Location, Location.

I had arranged name ranges like adjacent to the other in the same row. which meant all calculations happened in parallel. But I need calculations to happen in a sequence. So, I rearranged the name ranges in the sequence necessary.

And then, it worked like a charm!

There are ways to reduce the number of formulas further and reduce real estate too… but I think this form best explains what’s happening under the hood. So, I leave it at this.

TIP: You can change the Maximum Iterations value to 1 and press F9 key repeatedly to check how the puzzles evolves toward sudoku board solution after each iteration.

* The post Constraint Satisfaction Problem first appeared on continuoous.com