我正在创建一个程序来发明一个新的数独拼图。我最初计划这样做的方法是发明一个新的谜题,然后去掉随机数。然而,我使用的算法(如下图所示)创建一个新的谜题可能需要5分钟的时间。有人有更快的解决方案吗?
创建算法
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()简单地将NULL_VAL填充到板上。
发布于 2010-12-18 08:33:18
这里可能有几种优化方法。首先,您应该在每个单元格中添加一些簿记,为81个单元格中的每个单元格设置一组“仍然可能的数字”。在填充下一个单元格时,不要取任意的随机数,而是从这个集合中取一个随机数。
当你有6,561次失败的尝试时,不要停下来。当81盘中的一盘为空时,停止。在这种情况下,您不应该丢弃板,重新开始,而是后退一步,为前一个单元格尝试另一个值。试着从那做一个完整的回溯。
发布于 2010-12-18 08:53:30
我建议看一看D.Knuth的舞蹈环节 (gzipped )论文。有了他的方法,你可以有一个非常快的sudoku求解,然后你可以解决你的董事会,以检查它是否可以。
作为一种想法,对于工程Euler问题96,我的Java实现给出了解决方案(即解决50个sudokus):
real 0m0.357s
user 0m0.350s
sys 0m0.010s(UbuntuLinux2.6.32-26-服务器x86_64 GNU/ Linux,运行在"Intel(R) Atom(TM) CPU 330 @1.60GHz“上)
发布于 2010-12-18 08:28:31
我不认为删除随机数是个好主意。
在这里发布其他方法:boadIsOK()和resetBoard(),并阅读一些如何创建谜题(1)的文章。
https://stackoverflow.com/questions/4477288
复制相似问题