Holiday Sudoku project…progress
I posted recently about my holiday and that during the holiday I started to play with my own Sudoku game. The start for me was to generate random Sudoku puzzles for the player to solve.
I went headlong into creating my own algorithm which would create a Sudoku puzzle by filling a 9×9 grid with number between 1 and 9 and applying checks after each number to make sure the number was unique in its row and column as well as its local 3×3 grid, the basic rules of the game. This threw up a bunch of problems which I tried to find solutions for i.e. the generator would get to a point where 3/4 of the grid was populated but it would then loop endlessly trying to find combinations which met the ruels of the game. Because it would get stuck I put in some backtracking code which would realise that it was stuck and go back a few cells and change the numbers used to force the algorithm down a different path. This didn’t really solve the problem for me either. These kinds of problems have never been my strong point and I was starting to think I would not be able to come up with a quick and simple solution.
Then I had an idea :D which is that all Sudoku puzzles are basically the same i.e. 1-9 in cells, in a grid following some rules…so…how about I start off with a template i.e. an already complete puzzle and from this I generate a new puzzle. This to me would work and so that is what I tried next.
So I created a very simple command line Java app which would generate a puzzle and print out its solution and the puzzle itself to the console.
The first thing I needed was an array of numbers from 1 to 9. I would then shuffle this array before I generated a puzzle. Using this array I would then read a number from the puzzle template I had and use the number returned as an index into the numbers array. I would then place the number from the numbers array returned by this index into a new puzzle array. The code below is the setting up of these items.
public class Sudoku {
/**
* @param args
*/
public static void main(String[] args) {
int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int[] puzzle = new int[81];
/* Create a template Sudoku puzzle to use when creating new puzzles. */
int[] template = {
1, 2, 3, 4, 5, 6, 7, 8, 9,
4, 5, 6, 7, 8, 9, 1, 2, 3,
7, 8, 9, 1, 2, 3, 4, 5, 6,
2, 3, 4, 5, 6, 7, 8, 9, 1,
5, 6, 7, 8, 9, 1, 2, 3, 4,
8, 9, 1, 2, 3, 4, 5, 6, 7,
3, 4, 5, 6, 7, 8, 9, 1, 2,
6, 7, 8, 9, 1, 2, 3, 4, 5,
9, 1, 2, 3, 4, 5, 6, 7, 8};
You will see from the code above, I have created a template of a completed Sudoku puzzle. It was the most simple one I could find. This forms the basis for all the puzzles I will generate. This sounds limiting, but with this one template I can generate well over 300,000 puzzles with little chance of duplication, so it should keep most people happy :)
The next job was to shuffle the array of numbers from 1 to 9 so that we get a nice random puzzle generated. For this I created a couple of small methods. I’ve found that getting truly random numbers can be a pain and as I’m using native arrays and the Collection.shuffle methods deal with Objects, I decided to just create my own. They are shown in the next code snippet
/**
* Method which takes an array of ints and shuffles the ints within the array
*
* @param a Array of ints to shuffle
*/
private static void shuffle(int[] a) {
int N = a.length;
for (int i=0; i < N; i++) {
int r = i + (int) (Math.random() * (N - i));
exchg(a, i, r);
}
}
/**
* Method to exchange two ints within an array
*
* @param i Index of the array element to be swapped
* @param r Index of the array element with which i should be swapped
*/
private static void exchg(int[] a, int i, int r) {
int t = a[i];
a[i] = a[r];
a[r] = t;
}
I shuffle my array by calling the shuffle method as follows
/* Shuffle the numbers array so that we get a different puzzle each time */ shuffle(numbers);
Once that is done, its just down to looping through the template puzzle, getting the number from each cell and using that as an index into the numbers array. What ever is returned is then placed into a new puzzle array. This is a simple loop
/* Create a new puzzle. This is done by reading each number from the puzzle
* template and then retrieving that index from the numbers array. The numbers
* array contains 1-9 in a random order. */
for (int i = 0; i < 81; i++) {
int number = template[i];
puzzle[i] = numbers[number-1];
}
We now have an array called puzzle which holds the new puzzle we have generated. For this prototype I now just print out the completed puzzle. For this I create a small method to format and make it a little easier to read
/**
* Method which takes an array (expected to be a 9x9 grid) and outputs the
* contents to the console
*
* @param a Array which contains the data to be displayed
*/
private static void printPuzzle(int[] a) {
/* Output the new puzzle */
String row = "";
for (int y = 0; y < 81; y++) {
if (y % 9 == 0 && y > 0) {
System.out.println(row + "|") ;
row = "";
}
if (y % 3 == 0) {
row += "|";
}
if (y % 27 == 0) {
System.out.println(" - - - - - - - - - - -");
}
if (a[y] != 0) {
row += a[y] + " ";
} else {
row += " ";
}
}
System.out.println(row+"|");
System.out.println(" - - - - - - - - - - -");
}
This is called as follows
/* Print the solution to the puzzle */ printPuzzle(puzzle);
Now we have a complete puzzle we need to remove some numbers so that the player has something to solve. I've done this again using a simple loop in which we randomly remove numbers from the puzzle array by setting their value to 0. The minimum number of numbers you need in a puzzle so that it can be solved is 17, so as long as we don't remove more than 64 numbers, the puzzle should be able to be solved. The loop to remove the numbers is shown below
/* Remove numbers from the completed puzzle to create a puzzle which can then
* be played
*/
for (int i = 0; i < 45; i++) {
int index = (int)(Math.random() * 81);
if (puzzle[index] != 0) {
puzzle[index] = 0;
} else {
i--;
}
}
I then print the puzzle again as this is the puzzle which a player would solve and that's it. I've done some testing on this and the puzzles all look to be solvable and are generated VERY quickly :D
Now I've got a method, even if it is simple, for generating puzzles, I'm going to work on the main game framework so that the user has a nice graphical GUI in which to see the puzzle and play the game as well as a timer etc. This will be done using the Slick 2D framework so that I can do some funky stuff with OpenGL.
If anyone has any questions, suggestions etc please let me know. I'm learning as I go on this one but it is a lot of fun.
The full code for this test app is shown below
public class Sudoku {
/**
* @param args
*/
public static void main(String[] args) {
int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int[] puzzle = new int[81];
/* Create a template Sudoku puzzle to use when creating new puzzles. */
int[] template = {
1, 2, 3, 4, 5, 6, 7, 8, 9,
4, 5, 6, 7, 8, 9, 1, 2, 3,
7, 8, 9, 1, 2, 3, 4, 5, 6,
2, 3, 4, 5, 6, 7, 8, 9, 1,
5, 6, 7, 8, 9, 1, 2, 3, 4,
8, 9, 1, 2, 3, 4, 5, 6, 7,
3, 4, 5, 6, 7, 8, 9, 1, 2,
6, 7, 8, 9, 1, 2, 3, 4, 5,
9, 1, 2, 3, 4, 5, 6, 7, 8 };
/* Shuffle the numbers array so that we get a different puzzle
* each time */
shuffle(numbers);
/*
* Create a new puzzle. This is done by reading each number from the
* puzzle template and then retrieving that index from the numbers
* array. The numbers array contains 1-9 in a random order.
*/
for (int i = 0; i < 81; i++) {
int number = template[i];
puzzle[i] = numbers[number - 1];
}
/* Print the solution to the puzzle */
printPuzzle(puzzle);
/*
* Remove numbers from the completed puzzle to create a puzzle
* which can then be played
*/
for (int i = 0; i < 45; i++) {
int index = (int) (Math.random() * 81);
if (puzzle[index] != 0) {
puzzle[index] = 0;
} else {
i--;
}
}
/* Output the puzzle with missing numbers */
printPuzzle(puzzle);
}
/**
* Method which takes an array (expected to be a 9x9 grid) and outputs the
* contents to the console
*
* @param a
* Array which contains the data to be displayed
*/
private static void printPuzzle(int[] a) {
/* Output the new puzzle */
String row = "";
for (int y = 0; y < 81; y++) {
if (y % 9 == 0 && y > 0) {
System.out.println(row + "|");
row = "";
}
if (y % 3 == 0) {
row += "|";
}
if (y % 27 == 0) {
System.out.println(" - - - - - - - - - - -");
}
if (a[y] != 0) {
row += a[y] + " ";
} else {
row += " ";
}
}
System.out.println(row + "|");
System.out.println(" - - - - - - - - - - -");
}
/**
* Method which takes an array of ints and shuffles the ints within the
* array
*
* @param a
* Array of ints to shuffle
*/
private static void shuffle(int[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int r = i + (int) (Math.random() * (N - i));
exchg(a, i, r);
}
}
/**
* Method to exchange two ints within an array
*
* @param i
* Index of the array element to be swapped
* @param r
* Index of the array element with which i should be swapped
*/
private static void exchg(int[] a, int i, int r) {
int t = a[i];
a[i] = a[r];
a[r] = t;
}
}
