Last step in generating Sudoku Puzzles

DT31

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
al.add(j); // add it to arraylist
}
}
// 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);
}
}

Puzzler · Posted: Thu May 07, 2009 3:13 pm Post subject:

The clincher in generating grids is that you have to use a brute force method that just keeps trying different combination until they work.

Here's the way I did it. I got a bit lazy and allowed for 100's of backtracking loops, but I don't think they ever get executed more than a few times. I've never reached "stop"

Other programmers have implemented much more sophisticated techniques that include symmetry.

Actually, after writing this code I realized that much brighter people than me had spent more time than me generating grids and then published their results and/or their generators. Search for "top50000.zip" and you'll find 50,000 pretty challenging ones.

Funnily enough in 20 years of programming I never had to use Gotos until I started coding Sudoku where I found that the levels of nesting required become so complex it's just easier to bug out of the middle of a deep nest. I wish VB had an "Continue" or "Break" command instead!

Cheers

Lunatic · Posted: Sun May 10, 2009 11:38 am Post subject:

Puzzler · Posted: Mon May 11, 2009 2:33 pm Post subject: Iterate

Hey Marc

One of the challenges I had with the deep levels of nesting was that without the goto, I'd have needed even MORE nesting. At some point the code is clarified by simply bugging out, rather than trying to wrap more endifs and nexts.

I look at Gotos as a chainsaw. Ok to use if you know what you're doing, but dangerous in the hands of a novice.

"Exit For" is the equivalent of "Break", but there's no "Iterate" command that equates to the "Continue" statement. That said, in 20 years, I can't say I've missed it before. It's just this funky (and fun) sudoku analysis stuff!

cheers

Lunatic · Posted: Mon May 11, 2009 4:16 pm Post subject: Re: Iterate

Puzzler · Posted: Mon May 11, 2009 5:08 pm Post subject: Simple Coloring

Hey Marc

Could you help me out with the simple coloring algorithm? I've studied (and studied, and studied) your code but I'm just not understanding the sequence that the cells get colored

I've tried :
Following the chain of conjugations, flipping the color at each joint.
Following the chain by row/column sequence, setting the color based on surrounding cells.

In both cases I come to the end of a chain and have to make a decision what color to paint the starting cell of the next chain. In every case I would logically chose green, not blue for cell R1,C9.

Simple Sudoku correctly chooses Blue, so it must be using a different sequence but there's no pattern that I can discern.

Can you point me in the right direction?

Here's the puzzle I'm flummoxed with:

Puzzler · Posted: Mon May 11, 2009 5:48 pm Post subject: EUREKA!

Hey Marc

I found the problem.

I was using {r1,c4} as my starting cell.

I finally realized that this couldn't be a starting cell, because it's part of three occurrences in Box 2. Once I added some code to ignore three-occurrence cells, it all came together.

Man, I've struggled with this one. I swear, I'm not a dummy, but I've just had a mental block.

Thanks for your help

Lunatic · Posted: Mon May 11, 2009 7:20 pm Post subject: Re: EUREKA!

m_b_metcalf · Posted: Wed May 13, 2009 5:48 pm Post subject:

Puzzler · Posted: Wed May 13, 2009 7:45 pm Post subject: Recursion

Like bumblebee flight, how helicopters stay in the air and Bit-masking, recursion is something I think of as being the devils work Very Happy

It creates very compact code like yours (nice code by the way) but debugging can be a bear. I haven't used it much in the past, but since starting this pesky project have encountered all manner of freaky things - including (shudder) goto's Rolling Eyes

I use a recursive call to check incoming puzzles for solvability and uniqueness, and I used recursion to color the chains in my Simple Coloring algorithm (which I finally got working!).

I was pleased with the results and happy to know I was smart enough to use recursion after all!

Cheers

Kevin

PIsaacson · Posted: Wed May 13, 2009 10:49 pm Post subject: Re: Iterate

Lunatic · Posted: Thu May 14, 2009 8:15 am Post subject: Re: Iterate

m_b_metcalf · Posted: Thu May 14, 2009 10:51 am Post subject: Re: Recursion

gsf · Posted: Thu May 14, 2009 12:55 pm Post subject: Re: Recursion

PIsaacson · Posted: Thu May 14, 2009 10:51 pm Post subject:

Marc,

Thanks for the links to your MPQ solver. Very nicely done!!! An impressive set of features and techniques! The ALS-XZ help states that it is not yet implemented. Any projected dates for completion??? I only ask because ALS chains and Death Blossom are my (current) special area of interest.

BTW: I had a hard time seeing the help examples in FireFox due to the back-slashed file names for the gifs. They display just fine in IE, but I had to download a special add-on to "fix" urls containing back-slashes before they would appear in FireFox. Apparently this is a "known feature" of FF, but it's still my browser of choice...

Thanks again,
Paul