bubblenut
05-30-2005, 09:17 AM
These little puzzles recently appeared in the Bristish papers and have taken the public by storm. I really enjoyed doing them but then thought up something even more fun to do, write a program to solve them for me :D
For an explination of the puzzle itself check here (http://en.wikipedia.org/wiki/Sudoku) (NB: I did my solution without getting any hints from the internet so the sollution concepts aren't quite as well formed as in this article).
Terms I have used in the comments are as follows
Row : Pretty obvious, it's a row.
Column: Again, pretty obvious.
Block: This is less so, it's one of the 3x3 (in the case of a 9^2 Sudoku) sub squares.
Any comments on optimization would be greatly appreciated. Also, I've briefly tried to create a generator but if I just go straight through the board checking what possible options there could be in each cell and picking one at random it fails a few rows in. It just gets to a cell where there are no possible options. The only way I can think around this is dumb backtracking, so every time it hits a cell which it can't find an option for it steps back, picks another option and tries again but this would be horrendously expensive. Can anyone think of a better way? I think my next stage in this is going to be making it object oriented, in terms of design I've only really thought about the classes there would be so far, I'm thinking Board, Row, Column, Block and possibly Cell, what are everyone elses thoughts?
Cheers for your time
Bubblenut
For an explination of the puzzle itself check here (http://en.wikipedia.org/wiki/Sudoku) (NB: I did my solution without getting any hints from the internet so the sollution concepts aren't quite as well formed as in this article).
Terms I have used in the comments are as follows
Row : Pretty obvious, it's a row.
Column: Again, pretty obvious.
Block: This is less so, it's one of the 3x3 (in the case of a 9^2 Sudoku) sub squares.
Any comments on optimization would be greatly appreciated. Also, I've briefly tried to create a generator but if I just go straight through the board checking what possible options there could be in each cell and picking one at random it fails a few rows in. It just gets to a cell where there are no possible options. The only way I can think around this is dumb backtracking, so every time it hits a cell which it can't find an option for it steps back, picks another option and tries again but this would be horrendously expensive. Can anyone think of a better way? I think my next stage in this is going to be making it object oriented, in terms of design I've only really thought about the classes there would be so far, I'm thinking Board, Row, Column, Block and possibly Cell, what are everyone elses thoughts?
Cheers for your time
Bubblenut