# Last step in generating Sudoku Puzzles

• May 7th, 2009, 06:50 AM
DT31
Last step in generating Sudoku Puzzles
I have some code here that I need some help finishing. This code generates a random Sudoku Puzzle, problem is though that the one thing it is currently not checking for is having only one of each number in a set of three. I'm not quite sure on how to code that. Any help would be appreciated.

import java.util.*;

// produce a Sudoku grid
public class SudokuGenerator {

// the grid with the numbers
private int[][] grid;
// a single row
private int[] row;
// random and aray list
private Random ran;
private ArrayList<Integer> al;
// number of row and column
private int size;

// size of the Sudoku grid is received as parameter
SudokuGenerator(int size) {
this.size = size;
// this this the grid that we will fill
grid = new int[size][size];
// this is to store a row that we are trying to build
row = new int[size];
// random number generator
ran = new Random();
// arraylist that will contain the possible values for every case in the grid
al = new ArrayList<Integer>();

// now let's fill the grid row by row
for(int i = 0; i < size; i++)
fillRow(i);
}

// will call genRow() to fill row
// then will copy that row into the grid... the main reason for this method is to display debug info
private void fillRow(int n) {
genRow(n); // get a new row
// ok i can copy the row into the grid
System.out.print("Row " + n + ":");
for(int i = 0; i < size; i++) {
grid[n][i] = row[i];
System.out.print(" " + row[i]); // optional debug statement
}
System.out.println();

}
// fill the instance variable row with a new row
private void genRow(int n) {
// will be used to flag which values are available or not
boolean[] used = new boolean[size];
// it might take more than one trial to fill a row
// imagine the following case
// 1 2 3 4
// 2 3 4 1
// now if I add for the third row
// 3 then
// 3 4 then
// 3 4 2 then
// the only possible case for the last column is 1 but 1 is invalid in the last column
// so we'll have to try again
boolean conflict = true; // assume we have conflict to enter the while loop
while(conflict) {
conflict = false; // assume it worked
// loop for each column of the row
for(int i = 0; i < size; i++) {
// initialized that all number form 0 to size are not used and are available
for(int j = 0; j < size; j++)
used[j] = false;
// i cannot use any previous number used on that row so I set to true
// all the already allocated numbers in that row
for(int j = 0; j < i; j++)
used[row[j]] = true;
// i cannot use neither the numbers used in the same column in the previous rows already filled
for(int j = 0; j < n; j++)
used[grid[j][i]] = true;
// fill the array list with the possible values
al.clear(); // empty the arraylist
for(int j = 0; j < size; j++) { // fill it with the permitted values
if(!used[j]) { // if number not used
}
}
// now case explained in comment for variable conflict
// in that case no number would have been entered in the arraylist so its size would be 0
if(al.size() == 0) {
// if it is the case flag that there is a conflict
conflict = true;
break; // no need to continue the loop
}
// pickup a number randomly from the arraylist
row[i] = al.remove(ran.nextInt(al.size()));
}
}
}

// to retreive the grid
public int[][] getGrid() {
return grid;
}
// to print the grid (numbers are from 0 to size-1)
// but for regular user we will display from 1 to size
public String toString() {
String str = "";
for(int i = 0; i < size; i++) { // for every row
for(int j = 0; j < size; j++) { // and column
str += " " + (grid[i][j] + 1); // add value to String
}
str += "\n"; // end of line
}
return str;
}

public static void main(String[] arg) {
SudokuGenerator s = new SudokuGenerator(9);
System.out.print(s);
}
}
• May 7th, 2009, 10:32 AM
Xeel
Re: Last step in generating Sudoku Puzzles
Sorry for a stupid question, I haven't ever played Sudoku, so I don't know the rules: what do you mean by "having only one of each number in a set of three"

- you showed an example in the code but the sets were vertical only. Does the same rule apply to the horizontal sets as well?
- can the game be 8x8 or it's always a multiplier of 3?
- if yes, the uniqueness of sets you wanted is applied for 3x3 window only, or in case of 9x9 it should be 9x9 set uniqueness?

I believe I could solve your problem, I'm just asking to be able to help... :p

Edit: Ok I briefly revised the rules and I saw that I understood nothing about the thing you wrote about filling an instance with rows.
• May 7th, 2009, 12:25 PM
DT31
Re: Last step in generating Sudoku Puzzles
Basically the objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes (also called blocks or regions) contains the digits from 1 to 9 only one time each. The puzzle setter provides a partially completed grid. The code now checks for conflicts in the rows and columns, I'm just not sure how to check for a conflict in a 3x3 set. The game technically can be 8x8 or 4x4, I just have it set to the standard 9x9 at the moment, which is what I will be using. The uniqueness is for the rows, columns, and 3x3 sets.
• May 7th, 2009, 01:00 PM
ProgramThis
Re: Last step in generating Sudoku Puzzles
The checking of the 3x3 grid is the hardest part without a doubt. What you have to do is get the upper left hand location and make your ending conditions for your loop +3 from there.

So basically you get the array[0][0] for the first grid. You check it while i < 3 and j < 3 making sure that the numbers 1-9 only appear once during your checks. Then you move on to the next one, making your starting points your previous ending points: while i = 3 and i < 3+3 = 6 (or j, depending on how you set up your loops), then repeat for the other loop variable.

Something like this:
Code:

```for(int k = 0; k < 9; k++) { // you have 9 3x3 squares     //get i and j points     //set i and j ending points     for(;i < iEnd; i++) {         for(;j < jEnd; j++) {             //do your checking here         }     } }```

There is a neat way to get your i, j, iEnd and jEnd. I don't want to just give it to you, I want you to try and think of it first. Come up with what you think it should be and I'll help you with it. HINT* You should use k and &#37; somewhere in there. Good luck :D
• May 7th, 2009, 03:31 PM
DT31
Re: Last step in generating Sudoku Puzzles
I guess I'm just burnt out on Sudoku, this was the best I could do.

for(int k = 0; k < 9; k++) {

for( j = 0; j < j+3; j++ )
{
for(i=0; i< i+3; j++)
used[grid[i][j]]=true
}
}

Update:

k&#37;3 ?
• May 7th, 2009, 09:28 PM
DT31
Re: Last step in generating Sudoku Puzzles
I'm a bit confused as to how your code or hint fits into my code..I can't even think anymore, this program has me starting to hate Sudoku.

Update: I still haven't gone to sleep and this STILL doesn't make any sense to me. I can't even set the loop up. I would really really like to both be able to go to sleep and be done with this program, so if anyone can help me out with what I need to add to my code it would be much, much, much, much,much appreciated. Thanks!
• May 8th, 2009, 04:07 AM
dlorde
Re: Last step in generating Sudoku Puzzles
Once you get into that mental state, the best thing you can do is to go to sleep and dream about the problem. I usually find everything is clearer after a restless night's sleep ;)

It is probably best to work out how to do the checks step by step on paper before trying to write any code.

Every now and then go away, have a little relaxation, for when you come back to your work your judgment will be surer. Go some distance away because then the work appears smaller and more of it can be taken in at a glance and a lack of harmony and proportion is more readily seen...
Leonardo Da Vinci
• May 8th, 2009, 10:34 AM
DT31
Re: Last step in generating Sudoku Puzzles
I drew this picture...I understand what I need to do...just writing it is the problem haha. Thanks for the tip thought it was nice to get some rest.
• May 8th, 2009, 01:31 PM
dlorde
Re: Last step in generating Sudoku Puzzles
Quote:

Originally Posted by DT31
I drew this picture...I understand what I need to do...just writing it is the problem haha.

A diagram is a great way of understanding the problem, but not so great for figuring out what the code will be. You need an intermediate step between diagram and code. Try writing down how you would explain to someone how to do it - in simple steps in English. Don't worry about loops and ordering at first. Look at each step you've written and see if it can be broken down into simpler steps. When you have detailed all the different steps you think are needed, work out the order they must fit together and how you need to loop back to repeat steps, e.g. to do the rows and/or columns, etc. When you can describe what to do step by step, in English, you can then start thinking about how that would look as code.

The problem is mainly a logic puzzle - work it out as fully as you can before translating it into Java. Writing code is hard enough without having to figure out the program design at the same time.

If I had eight hours to chop down a tree, I would spend 6 hours sharpening an axe...
Anon.