Archive - Originally posted on "The Horse's Mouth" - 2005-06-23 06:32:48 - Graham Ellis
Have you seen the sudoku puzzles that are being published in the Daily Telegraph and (I think) the Los Angeles times? There's a whole group of addicts out there and helper and forum web sites too. Lisa pointed the puzzle out to me recently (no, she's not an addict!) with the thought of providing a helper spreadsheet and wondered what I could do on algorithms.
The puzzle is easily explained. You're given a 9 x 9 grid of cells with some of them already filled in with a single digit in the range 1 to 9 and you have to complete the puzzle by adding further 1 to 9 digits such that each row, each column and each cluster of 9 cells contains each digit just once. Here's a blank board:
on which I've numbered the cells just for reference.
Here's that same game board completed. I filled in the numbers that you now see in red on the form above (try it out if you like) and when I submitted it to my program, it completed the other cells ... in this example right through to a complete solution.
I've not personally spent a huge amount of time on this - just played with the algorithms and I think that my program will solve most (but not all) puzzles. Furthermore, it's what I describe as a "spike solution" - the code is poorly written as it grew during my research. Bits of code are duplicated (I should have used a loop or functions), documentation and comments are lacking, and it's pretty poorly inset. You can see the code in this shocking state if you like and rightly criticise me. My defence is that it's a spike solution - a proof of context that needs re-engineering.
Two questions
Have I provided a "helper" or a "cheat"? Is a program such as this one a helper in the spirit of the game, or does it go to far and provide an unfair advantage? If that's the case, where's the limit?
Should I publish code like this? I'm quite happy with my spike solution and I don't think it opens any security holes on our site. So should I say "hey - look at this and use it if you like", should I publish it with a copyright statement, or should I be ashamed of myself for even typing code this p*sspoor in the first place?
Two more sample solutions - tests of my algorithm (I'll come back and replace one with a demo of what happens when someone submits a puzzle that can't be fully resolved).
Here's that same game board completed. I filled in the numbers that you now see in red on the form above (try it out if you like) and when I submitted it to my program, it completed the other cells ... in this example right through to a complete solution.
Two more sample solutions - tests of my algorithm (I'll come back and replace one with a demo of what happens when someone submits a puzzle that can't be fully resolved).