Java で数独ボードを生成/解決するための再帰的な DFS アルゴリズムを作成しましたが、終了するのに永遠に時間がかかります。説明/最適化を歓迎します。数独ボードを生成するのにそれほど時間がかかるとは想像もできません。特に、周りにあるすべてのアプリの場合はそうです (ただし、データベースはあるかもしれませんが)。
基本的に、[1-9] のいずれかが数独の制約を満たすかどうかを確認しながら、すべてのセルをトラバースし、行き止まりの分岐をバックトラックします。メモリを節約し、再帰メソッドの呼び出しごとにボードとして機能する 2D 配列をコピーしないようにするために (そして、私が間違っていなければ、そのツリーには潜在的に 81*9! の葉が存在します...)、2D を作成しました。ブランチが探索されるたびに要素がプッシュされ、行き止まりの場合はポップされる整数スタックのマトリックス。
以下、実装です。高速化に関するアドバイスは大歓迎です。私はこれを個人的な演習として行っていますが、漸近的により良いものが存在するかどうか疑問に思っています。
以下のひどい読み物ではないことを願っています..ありがとう！
1) アルゴリズムの実装: (一意のボードを作成するために、値が [1-9] の「ごちゃまぜ」な配列になっていることに注意してください。)
/**
* Provides one solution to a board with an initial configuration, or <code>null</code> if there is none.
* The search is randomized, s.t. the algorithm can serve to populate an empty board.
*
* @param initial The initial board given to solve.
* @return The fully solved board, or null if no solution found.
*/
public static int[][] solveBoard (int[][] initial){
return solveBoard(new StackedBoard(initial), 0, 0);
}
private static int[][] solveBoard (StackedBoard board, int xPos, int yPos){
// base case - success
int remaining = 81;
for (int x = 0; x < 9; x++){
for (int y = 0; y < 9; y++){
if (board.peekAt(x, y) != Board.EMPTY){
remaining--;
}
}
}
if (remaining == 0){
return board.flatView();// the only creation of an array.
}
// recursive case
for (int x = 0; x < 9; x++){
for (int y = 0; y < 9; y++){
if (board.peekAt(x, y) == Board.EMPTY){
for (int val : getJumbledRandomVals()){
if (isMoveLegal(board, x, y, val)){
board.pushAt(x, y, val);
int[][] leafBoard = solveBoard(board, x, y);
if (leafBoard != null) {
return leafBoard;
}
}
}
}
}
}
// base case - dead branch
board.popAt(xPos, yPos);
return null;
}
2) StackedBoard の実装:
/**
* Represents square boards with stacked int elements.
*/
class StackedBoard {
ArrayList<ArrayList<Stack<Integer>>> xaxis = new ArrayList<ArrayList<Stack<Integer>>>();
/**
*
* @param init A square array - both dimensions of equal length, or <code>null</code> if no initialization.
*/
public StackedBoard (int[][] init) {
for (int i = 0; i < 9; i++){
ArrayList<Stack<Integer>> yaxis = new ArrayList<Stack<Integer>>();
xaxis.add(yaxis);
for (int j = 0; j < 9; j++){
Stack<Integer> stack = new Stack<Integer>();
yaxis.add(stack);
}
}
if (init != null){
for (int x = 0; x < init.length; x++){
for (int y = 0; y < init.length; y++){
getStackAt(x, y).push(init[x][y]);
}
}
}
}
public Stack<Integer> getStackAt (int x, int y){
return xaxis.get(x).get(y);
}
public int peekAt (int x, int y){
return getStackAt(x, y).peek();
}
public void pushAt (int x, int y, int value){
getStackAt(x, y).push(value);
}
public Integer popAt (int x, int y){
try {
return getStackAt(x, y).pop();
} catch (EmptyStackException e){
// shhhhh!
return Board.EMPTY;
}
}
/**
* Flat view of the stacked-board; peek of the top elements.
*/
public int[][] flatView (){
int[][] view = new int[xaxis.size()][xaxis.size()];
for (int x = 0; x < xaxis.size(); x++){
for (int y = 0; y < xaxis.size(); y++){
view[x][y] = getStackAt(x, y).peek();
}
}
return view;
}
}
3) 制約関数の実装:
/**
* Is the move legal on the suggested board?
*
* @param board The board.
* @param x The X coordinate, starts with 0.
* @param y The Y coordinate, starts with 0.
* @param value The value.
* @return <code>true</code> iff the move is legal.
*/
private static boolean isMoveLegal (StackedBoard board, int x, int y, int value){
// by value
if (1 > value || value > 9){
return false;
}
// by column
for (int i = 0; i < 9; i++){
if (board.peekAt(i, y) == value){
return false;
}
}
// by row
for (int i = 0; i < 9; i++){
if (board.peekAt(x, i) == value){
return false;
}
}
// by lil square
int lowerX = x < 3 ? 0 : (x < 6 ? 3 : 6);
int upperX = lowerX + 2;
int lowerY = y < 3 ? 0 : (y < 6 ? 3 : 6);
int upperY = lowerY + 2;
for (int i = lowerX; i <= upperX; i++){
for (int j = lowerY; j <= upperY; j++){
if (board.peekAt(i, j) == value){
return false;
}
}
}
return true;
}