A simple algorithm for generating Sudoku puzzles
I first came in contact with Sudoku a few years ago, back when I was a student. I traveled a lot, about three hours one-way at least twice a month, and it was a real pleasure "not" to waste my time just staring in the moving environment, although even that can be fun sometimes, but it gets a bit dull after the first couple of trips and then it simply makes you asleep :)
Few months ago I got obsessed with it, again, I've started solving Sudoku puzzles in a specialized Sudoku magazines (daily newspapers puzzles weren't enough anymore), and it's become a real office mind-stimulating treatment... Try making a short Sudoku-solving break every time you're coding something, in a short time you'll find algorithms leaking out of your brains, and coding faster than you've ever had :)... No, seriously, it has some strange positive influence on your (or mine at least) logic, maybe because there is so much logic in it... even though it's so simple game.
I wanted to go deeper this time... you know "Set the Controls for the Heart of the Sun", find out more about it, reach for its "essence", build an algorithm or two and then do a bit of coding.
It sounds like a story so far ain't it :), yet this post is intended to be a showcase of some approaches and algorithms for creating a Sudoku puzzles and games. So let's get technical...
Sudoku is a logic game, there are pretty well definition and details on Wikipedia for the game. The player has to fill a partially filled 9x9 grid which consists of nine 3x3 boxes or blocks so that each number from 1 to 9 appears only once in each column, row and box. I was very surprised how much stuff about Sudoku one can find on the Net. There are a bunch of sites, forums, blogs completely dedicated to Sudoku and things about it.
When building a Sudoku game, perhaps the most fundamental thing is to generate the puzzle, afterward you'll just have to wait for the player to solve it. In order to generate a puzzle you (your application) have to solve it first, so in a sense generating a puzzle is like a solving a certain puzzle.
There are many approaches/algorithms for generating or solving a Sudoku puzzle. The backtracking algorithm can be used to generate a Sudoku puzzle. You can use this by iterating through each cell of the grid and populating it with certain number. You can start with the first cell by populating it with a random number from 1 to 9, then move to the second cell and populate it with another random number excluding the number in the first cell etc. Basically when populating a certain cell you'll have to take in mind the numbers that have already been populated in the column, row and box where the current cell is positioned. Solving Sudoku is also possible with brute-force algorithms, although if not coded well it can bring to a great resources (CPU in particular) consumption. There are far more approaches, but here we'll concentrate on one single one, and pretty simple as well.
Sudoku is a logic game which consists of numbers, and logic plus numbers is a perfect grounding for math to take over. In fact, there is a lot more math involved in Sudoku, but we'll use one concept: a valid Sudoku puzzle (each number appears only once in each row, column and box) can morph to another valid puzzle by applying certain transformations to certain cells, or complete rows, columns and/or boxes. I've heard about this some time ago, so I wanted to make sure if it's really true... and you guess it, it is :), but we'll skip the mathematical proof here.
We'll use the following transformations:
Swap cells (rows) horizontally: rotating the grid around the fourth row, the first row swaps with the last, the second swaps with the eighth and the third swaps with the fifth, no change to the fourth row
Swap cells (columns) vertically: rotating the grid around the fourth column, the first column swaps with the last, the second swaps with the eighth and the third swaps with the fifth, no change to the fourth column
Swap cell around the main diagonal: sort of rotating the grid around the main diagonal
Swap cell around the minor diagonal: sort of rotating the grid around the minor diagonal
Here is a simple flash gadget that might help visiulize the transformations:
if(typeof(flashCnt) == 'undefined') flashCnt=[];
flashCnt.push({id:'sudoku-alg', width:512, height:552,movie:'/swf/sudokuAlg.swf', fvObj: {wmode:'transparent', allowfullscreen:false, allowscriptaccess: 'always', menu: false}});
Sudoku Transformations
You can also swap any two columns in the first, second and the third vertical region, as well as any two rows in the first, second and the third horizontal region, but for the sake of simplicity we'll skip them here.
Theoretically applying these transformations or their combination on a single puzzle solution will effect in tremendous number of puzzles, proportionally to the number of transformation iterations.
In practice applying these transformations or their combination on a reasonable number of puzzle solutions will effect in fairly enough amount of puzzles, when applying reasonable number of transformation iterations.
You'll first need to define a number of completed solutions. Once the player starts a new game randomly select one of the completed solutions. At this point you can go with this puzzle and start the game or apply some transformation combination and then start the game. Use some logic when applying the combination since some of them don't make sense at all and result in the initial solution, like: horizontal and horizontal, or horizontal, vertical, horizontal and vertical. The puzzle solutions can be stored in an one-dimensional (indexes from 0 to 80 for each cell) or two-dimensional array (indexes [row][column]).
We'll go with the one dimensional array in this presentation. Here are the definitions of the two arrays in Action Script 3:
//
// Puzzle Solutions, two-dimensional array - each element contains valid puzzle solution:
//
private var solutions:Array = [
[4,2,9,3,1,6,5,7,8,8,6,7,5,2,4,1,9,3,5,1,3,8,9,7,2,4,6,9,3,1,7,8,5,6,2,4,6,8,2,9,4,1,7,3,5,7,4,5,2,6,3,9,8,1,3,5,4,6,7,2,8,1,9,1,7,8,4,5,9,3,6,2,2,9,6,1,3,8,4,5,7],
[9,6,5,4,1,8,7,3,2,1,4,3,2,6,7,9,5,8,8,2,7,9,5,3,6,1,4,5,7,9,3,8,4,1,2,6,4,1,2,6,9,5,3,8,7,6,3,8,1,7,2,4,9,5,3,5,4,7,2,1,8,6,9,7,8,6,5,3,9,2,4,1,2,9,1,8,4,6,5,7,3],
[1,2,5,8,9,7,6,3,4,6,7,4,5,1,3,9,2,8,3,9,8,4,2,6,1,5,7,4,8,2,6,5,9,7,1,3,7,6,9,2,3,1,4,8,5,5,3,1,7,8,4,2,9,6,2,4,3,9,7,5,8,6,1,9,5,6,1,4,8,3,7,2,8,1,7,3,6,2,5,4,9],
....................................................................................
];
//
// Current Solution - contains the solution for the current puzzle [the first cell has index 0, second has index 1, ... last has index 80], element from solutions array or transformed version
//
private var currentSolution:Array = [];
In the case of one-dimensional array usage for the puzzle solution, here is a short code snippet for swapping appropriate cells for a certain transformation:
private function transformSudoku(type:String = 'horizontal'):void
{
var i:uint = 0, tmp, tmpIx, mod9, div9;
switch(type) {
case 'vertical':
for(i = 0; i < 81; i++) {
//
// If column (i % 9) < 4 swap it:
//
if(i % 9 < 4) {
tmp = currentSolution[i];
div9 = Math.floor(i / 9);
tmpIx = (9 * div9 + 8) - (i - (9 * div9));
currentSolution[i] = currentSolution[tmpIx];
currentSolution[tmpIx] = tmp;
}
}
break;
case 'mainDiagonal':
for(i = 0; i < 81; i++) {
//
// Upper Main diagonal: row + column < 8
//
if((Math.floor(i / 9) + i % 9) < 8) {
mod9 = Math.floor(i % 9);
div9 = Math.floor(i / 9);
tmp = currentSolution[i];
tmpIx = (8 - mod9) * 9 + 8 - div9;
currentSolution[i] = currentSolution[tmpIx];
currentSolution[tmpIx] = tmp;
}
}
break;
case 'minorDiagonal':
for(i = 0; i < 81; i++) {
//
// Upper Minor diagonal: row > column
//
if(Math.floor(i / 9) > i % 9) {
mod9 = Math.floor(i % 9);
div9 = Math.floor(i / 9);
tmp = currentSolution[i];
tmpIx = div9 + mod9 * 9;
currentSolution[i] = currentSolution[tmpIx];
currentSolution[tmpIx] = tmp;
}
}
break;
case 'horizontal':
default:
for(i = 0; i < 81; i++) {
//
// Row < 4
//
if(Math.floor(i / 9) < 4) {
mod9 = Math.floor(i % 9);
div9 = Math.floor(i / 9);
tmp = currentSolution[i];
tmpIx = mod9 + (8 - div9) * 9;
currentSolution[i] = currentSolution[tmpIx];
currentSolution[tmpIx] = tmp;
}
}
break;
}
}
That should be it, simple yet useful approach. Now relax, treat yourself a game of Sudoku (level: very, very easy) and try to beat our best time: 0:01 :)
if(typeof(flashCnt) == 'undefined') flashCnt=[];
flashCnt.push({id:'sudoku-game', width:512, height:552,movie:'/swf/sudoku.swf', fvObj: {wmode:'transparent', allowfullscreen:false, allowscriptaccess: 'always', menu: false}});
Sudoku Game
