I'm creating a program that invents a new Sudoku puzzle. The way I initially planned on doing this is by inventing a new puzzle and then removing random numbers. However, the algorithm I use (seen below) to create a new puzzle can take up to 5 minutes to make one. Does anyone have any faster solutions?
for (int x = 0; x < boardWidth; x++) //boardWidth is the number of fillable squares wide and high the board is. (9 for a standard Sudoku board)
{
for (int y = 0; y < boardWidth; y++)
{
int errorCount = 0;
do
{
boardVals[y][x] = (byte)(rand.nextInt(boardWidth) + 1);
errorCount++;
if (errorCount > Math.pow(boardWidth, 4)) //If the square has been tried to be filled up to boardWidth^4 times (6,561 for a standard Sudoku board), it clears the board and starts again.
{
resetBoard();
x = 0; y = 0; break;
}
}while (!boardIsOK()); //boardIsOK() is a method that checks to see if the board is solvable, ignoring unfilled squares.
}
}
private boolean boardIsOK()
{
for (int i=0; i < boardWidth; i++)
{
if (!setIsOK(getRow(i)))
{
return false;
}
if (!setIsOK(getCol(i)))
{
return false;
}
}
for (int x=0; x < boardSegs; x++)
{
for (int y=0; y < boardSegs; y++)
{
if (!areaIsOK(getSquare(x,y)))
{
return false;
}
}
}
return true;
}
private byte[] getRow(int index)
{
return boardVals[index];
}
private byte[] getCol(int index)
{
byte[] b = new byte[boardWidth];
for (int i=0; i < boardWidth; i++)
b[i] = boardVals[i][index];
return b;
}
private byte[][] getSquare(int xIndex, int yIndex)
{
byte w = (byte)(boardWidth / boardSegs), b[][] = new byte[w][w];
for (int x=0; x < b.length; x++)
{
for (int y=0; y < b[x].length; y++)
{
b[y][x] = boardVals[y + (yIndex * w)][x + (xIndex * w)];
}
}
return b;
}
private boolean setIsOK(byte[] set)
{
for (int i=0; i < set.length - 1; i++)
{
for (int j=i + 1; j < set.length; j++)
{
if (set[i] == set[j] && set[i] != NULL_VAL && set[j] != NULL_VAL)
{
return false;
}
}
}
return true;
}
private boolean areaIsOK(byte[][] area)
{
int size = 0;
for (int i=0; i < area.length; i++)
{
size += area[i].length;
}
byte[] b = new byte[size];
for (int x=0, i=0; x < area.length; x++)
{
for (int y=0; y < area[x].length; y++, i++)
{
b[i] = area[x][y];
}
}
return setIsOK(b);
}
resetBoard() simply fills the board with NULL_VAL.
There are several optimization approaches possible here. First, you should add some bookkeeping to each cell, having a set of the "still possible numbers" for each of the 81 cells. Instead of taking an arbitrary random number, take a random number from this set when you fill the next cell.
And don't stop when you had 6,561 unsuccessful tries. Stop when one of the 81 sets goes empty. When this is the case, you should not throw the board away and start over again, but go one step backwards and try another value for the previous cell. Try to make a complete backtracking algo from that.