Kev's Development Toolbox

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.