Sudoku and Exact Cover problems

Sudoku is an example of an Exact Cover problem and can be solved by picking a subset of candidate rows from the exact cover matrix that satisfy all of the constraints for the complete grid.

I explored building an implementation of Donald Knuth’s Algorithm X using Dancing Links as a Sudoku solver, which you can read more about here.

For a 9×9 Sudoku puzzle, a candidate grid has x possible candidates, by y constraints.

For a 9×9 grid using numbers 1 through 9, there are:

9 rows x 9 columns x 9 (values 1 through 9) = 729

… possible candidate values for the cells.

For 4 constraints applied to every cell in the 9×9 grid, there are

9 rows x 9 columns x 4 constraints = 324

… constraints to be met.

If you fill a grid where a 1 represents a met constraint by that candidate and 0 is unmet, if you zoom out far enough the table looks like this:

To see how a matrix like this is used together with Donald Knuth’s Algorithm X and Dancing Links, see my previous post here.

Can you develop code to effectively solve a problem without understanding the problem first? (writing code to solve Sudoku puzzles)

You shouldn’t have to think too hard to answer this question. In order of most likely answer first, least likely last (I hope), your answer could be one of:

a) No. How can you solve a problem if you don’t understand what it is that you’re trying to solve?

b) Possibly, if your approach to solving a vague or poorly defined problem is to ask clarifying/fact finding questions to investigate and gain an understanding of the problem so you can get to a position where you’re able to solve the problem.

c) Yes. (Really?)

There’s no correct answer to this question although I hope you initially answered (a), but (b) is a valid possibility if you consider the effort to understand a problem is an essential part of solving a problem (which of course it is).

I decided I would have a go at writing a Java app to solve Sudoku puzzles. I’m familiar with the rules of Sudoku and have solved a few puzzles by hand. I’m not an expert by any means, but I know enough about this type of puzzle to realize there’s probably at least a few well understood algorithms for effectively solving them, but as I started out I wasn’t familiar with any particular approach.

So here’s my experiment: I decided I would deliberately avoid doing any background reading on known algorithms or reading any articles or discussions on approaches for how to solve, and would attempt to blindly develop my own approach to solve a puzzle to see how successful (or otherwise) I would be. I know the rules to the puzzle, I understand what the end result must be, so how hard can it be, right?

For those unfamiliar with Sudoku, here’s the 3 rules:

  • each 3×3 square must contain each digit 1 through 9 with no repeated values
  • each column must also contain each digit 1 through 9 with no repeated values
  • and the same rule for each row, 1 through 9, with no repeated values

Here’s my starting puzzle that I used to write my code against:

      | 8 1   | 6 7   
    7 | 4 9   | 2   8 
  6   |   5   | 1   4 
- - - + - - - + - - -
1     |     3 | 9     
4     |   8   |     7 
    6 | 9     |     3 
- - - + - - - + - - -
9   2 |   3   |   6   
6   1 |   7 4 | 3     
  3 4 |   6 9 |       

(Puzzle generated by WebSoduku)

My initial approach for my algorithm was to follow the steps I would go through by hand if I were solve a puzzle on paper. This already set me off at a disadvantage because I don’t think I’m particularly skilled or experienced at solving Sudoku, so I wasted some hours trying to capture these steps in code. Going down this path I realized if you take this approach, you mentally ask several questions as you look for possible values for empty squares, but it’s not not the answer to any one of questions that gets you a correct answer, it’s the combination of answers to multiple questions (because there’s 3 constraints, above, that you need to follow). So following this approach, I wrote code to iterate through the complete grid applying my limited set of questions to find potential values for each empty cell. The result was after a couple of iterations I had inserted values into all empty cells as sets of potential values, but my approach was not complete enough to be able to solve the example puzzle I was using for testing.

This is where I reached my point of realization. Clearly I did not understand enough about the problem to be able to write a program to solve it.

After some debugging and tweaking to my approach, I did reach a point where I could solve my test puzzle in 7 passes through the grid, but when testing the same approach with another easy puzzle, my approach failed to reach a solution. So my approach only partially works when I have a starting point with enough values, or a certain distribution through the grid, but fails to solve all puzzles.

At this point I could have continued blindly in the same direction, but I decided I had already proved to myself my point that you can’t solve a problem if you don’t understand what it is that you’re trying to solve. It was time to read up on the the established algorithms to solving, so I could understand what it was that I was missing.

There are a number of established algorithms for solving Sudoku, and I won’t describe or cover them all there, but there’s a good summary on this wikipedia page. The approaches range from brute force (sequentially testing each value 1 through 9 in each cell, with backtracking to prior cells if chosen values fail to find a solution, to variations such as Donald Knuth’s Dancing Links algorithm.

My conclusion to my original question though is clear: had I recognized the problem as an example of an exact cover problem, I would have known that there are established algorithms for solving this type of problem.

You can’t solve a problem if you don’t understand what it is that you’re trying to solve.

If you’re interested in taking a look at my partial solution you can find it here on my Github.

Implementing simple sort algorithms in ARM Assembly (part 2)

I haven’t completed the code yet, but I wanted to share my progress learning ARM assembly by implementing a simple sort algorithm (part 1 is here). I’m committing my changes as you go so if you’re interested you can also pull the code form github here.

The simple sort that I’m implementing is a ‘comparison sort‘. You start at lowest end of the array of values, iterate through to find the smallest value and then switch the smallest found value to the front. You then repeat the loop starting at the next index in the array, search again for the smallest, switch, and then continue repeating this until you’ve looped through and compared all values.

I’ll make clear that as I’m learning ARM ASM I’ve no idea at this point if my approach to implementing this algorithm is optimal, but I’m finding it a useful learning exercise. At this point I’m also finding debugging the code in Eclipse C++ indispensable – I don’t think a this point I could debug the code without an IDE (or to try would be difficult and error prone). Once you’ve walked through the steps to crosscompile in Eclipse C++ you can use the same setup to remove debug in Eclipse C++ too, with the executable running remote on the Raspberry Pi.

So far I have the outer and inner loops working, so can iterate through the values, and compare to find the smallest value on each iteration. I’ll post another update once I’ve got the swapping done. In the meantime if you’re interested you can take a look at my latest commit in my github repo above.