secretGeek.netSudoku
Last year I spent a few weeks completely away from all computers. In this primitive state of savagery (that some refer to as a 'holiday') I took to playing a little Sudoku each day, using old-fashioned materials known as pen and paper. Let me tell you, pen and paper are severely over-rated. Devoid of any computing facilities, I found that — much like Porky Pig whom, whenever he's forced to diet, begins to fantasize about food — I began to fantasize about programming. And Sudoku in particular got me really excited.
I decided there were three interesting challenges here:
- How to start with nothing and create a fully solved board.
- How to remove numbers from a fully solved board until an interesting game is created.
- How to solve a partially completed board: i.e. how to play sudoku.
Start with nothing and create a fully solved board.
In my techno-isolation I came up with an algorithm that I thought would have no trouble generating solved boards.
Here it is in pseudo code.
Do this for each number from 1 to 9, using variable "i".
For each row:
Keep doing this until you've placed the number i somewhere on that row:
Pick a random cell.
Check that the cell is empty.
And that "i" does not appear in the current column.
And that "i" does not appear in the current 3*3 subgrid.
if all three criteria are met, then place "i" in the current cell.
I thought to myself... will this process get stuck? Of course it won't, I thought. How could it!
This is because, as it turns out, when I am away from a computer, my brain turns into useless jelly.
When I was finally sat in front of a computer and wrote a version of the code (using LinqPad) I found that very often it did break down.
Here's an example:
_ 4 _ | _ _ 3 | 2 1 _
_ 3 _ | 2 _ 1 | 4 _ _
1 _ 2 | _ 4 _ | _ _ 3
-------------------------------------
_ 2 _ | 4 _ _ | 1 3 _
3 _ 1 | _ 2 _ | _ 4 _
4 _ _ | 1 3 _ | _ _ 2
-------------------------------------
_ _ _ | _ 1 4 | 3 2 _
2 1 4 | 3 _ _ | _ _ _
_ _ 3 | _ _ 2 | _ _ 1 ← Try and place a "4" on this row!
Sometimes, the numbers that have already been placed will put so many constraints on the next number, that there is no solution.
I ran the program a few times and found that sometimes it stopped at 3 numbers, sometimes it made it as far as 6 numbers.
I thought I would need to write some clever algorithm that tries to shuffle the problem numbers around, to break the deadlock.
In the example above, we could shuffle some other '4's around, to come up with a workable solution... for example....
_ 4 _ | _ _ 3 | 2 1 _ _ 3 _ | 2 _ 1 | _ _ 4 → move this 4 from first to third position 1 _ 2 | _ 4 _ | _ _ 3 ------------------------------------- _ 2 _ | 4 _ _ | 1 3 _ 3 _ 1 | _ 2 _ | _ 4 _ 4 _ _ | 1 3 _ | _ _ 2 ------------------------------------- _ _ _ | _ 1 4 | 3 2 _ 2 1 4 | 3 _ _ | _ _ _ _ _ 3 | _ _ 2 | 4 _ 1 ← Can now place this 4.
And if shuffling 4's above isn't enough, we could expand the range of our shuffling.
But then I had one of those Engineering Breakthroughs you read about in clever articles on Hacker News. (Mathematicians are never as clever as this.) "Sometimes it hits a deadlock by the number '3'... sometimes it gets as far as '6'... what if I just re-run it a bunch of times, and see if it ever completes?" aka, The Retry Pattern.
So I put a loop around it and said, "keep going until you're stuck, then restart from scratch, over and over."
And thus, within a second, it would always succeed at creating a sudoku board. Sometimes it would have to start over only 3 times, sometimes it would be over a thousand times. But I always had a complete new sudoku board in much less than a second.
That was good enough, and no need to perform any tricksy mathematics to "satisfice" the problem.
I came up with similarly simple approaches for the other two problems. I've put some c# sudoku code online.
I can now type "linq sudoku" (from powershell) and see a fresh sudoku to solve, any time I feel like it. Which it turns out is not very often.
