John's Blog
Everyone and his dog has a 'blog these days, right? So why not me? If you are interested in anything I'm saying, great! Let's talk about it! (Leave comments.) If not, try one of my other links. Better yet, why are you wasting your time staring at your computer screen, go do something real!
Let me know if you'd like to be to be updated whenever I post a new article. It won't happen every day!
Automatic Sudoku Puzzle Generation
Wednesday, August 01, 2007
In a meeting today, while the focus was on what others were doing, I entertained myself by thinking about how you would go about creating Sudoku puzzles. I started by creating a 2x2 (easy), then a standard 3x3, using a simple pattern of sequences. That led to thoughts of the general steps required to create any N x N Sudoku, herewith.(Click title to read more...)My initial 3x3 pattern was:
123 456 789
234 567 891
345 678 912
456 789 123
567 891 234
678 912 345
789 123 456
891 234 567
912 345 678
You see the pattern? First row is in order, each next row starts with the next higher digit than the last.
Then I realized that an easy way to create variations on this is to swap any single row or column within the same large square, which as far as I could tell will not cause a violation of the rules. Finally, you don't really have to start the first row in order, as long as you always shift each subsequent row by one place.
In general, then, here are the steps I've come up with for generating any valid combination for an N x N puzzle, which could be implemented by computer algorithm:
- Generate row 1 in random order
- For rows 2 through N^2, take previous row and shift left or right one place (consistently)
- When finished generating rows, shuffle single rows or columns within the same large square as desired
Some notes: For larger puzzles than 3x3, you must go to letters of the alphabet. This can take you up to 5x5, maybe even 6x6 if you also include numeric digits. Above 6x6, you'd have to include puncuation, which seems kind of silly.
Implementation of this algorithm is left as an exercise to the reader. But if you do, let me know and I'll link to it. ;-)
0 comments
