Java で 9x9 グリッドの数独ソルバーをプログラミングしています。
次の方法があります。
グリッドの印刷
指定された値でボードを初期化する
競合のテスト (同じ番号が同じ行または 3x3 サブグリッドにある場合)
数字を 1 つずつ配置する方法で、最も手間がかかります。
その方法について詳しく説明する前に、再帰とバックトラッキングを使用して解決する必要があることを覚えておいてください (例として、こちらのアプレットをご覧ください http://www.heimetli.ch/ffh/simplifiedsudoku.html ) 。
また、私はこの数独を、左上から始めて最初の列、次に 2 番目の列など、垂直に下に移動して解決しています。
これまでのところ、私は次のものを持っています：
public boolean placeNumber(int column){
if (column == SUDOKU_SIZE){ // we have went through all the columns, game is over
return true;
}
else
{
int row=0; //takes you to the top of the row each time
while (row < SUDOKU_SIZE) loops through the column downwards, one by one
{
if (puzzle[row][column]==0){ //skips any entries already in there (the given values)
puzzle[row][column]=1; //starts with one
while(conflictsTest(row,column)){ //conflictsTest is the method I wrote, which checks if the given parameters are in conflict with another number
puzzle[row][column] += 1;
}
//BACK TRACKING
placeNumber(column); //recursive call
}
else{
row++; // row already has a number given, so skip it
}
}
column++; // move on to second column
placeNumber(column);
}
return false; // no solutions to this puzzle
}
BACKTRACKING とラベルを付けた場所は、コードの残りの部分を移動する必要があると思われる場所です。
私は次の行に沿って何かを考え出しました：
- 値が 10 の場合、その値を 0 に戻し、行を戻し、その値を 1 増やします
その後戻りの「戦略」は、いくつかの理由で正確には機能しません。
前の行が指定された値だった場合 (つまり、インクリメントしたり触れたりすることは想定されていませんが、代わりに、そこに配置した最後の値に戻ります)
前の値が 9 だった場合はどうなるでしょうか。それを 1 増やしたら、今度は 10 になり、うまくいきません。
誰かが私を助けてくれますか？