数独パズルの再帰ソルバーを書いています。プログラムがより簡単に読み取れるように、空白の場所を 0 で保存します。グリッドをよりよく視覚化するために、元のパズルを下付き文字から保存しています。再帰を完全に把握しているかどうかはわかりませんが、そこに問題があります。パズルを解くのに順調に進んでいるように見える出力を取得していますが、そこにあるべきではないゼロが残っています。unsetSquare の配置、または return ステートメントと関係があると思います。
これが出力のサンプルです...
**************************************************
7 4 3 | 8 2 1 | 5 6 8
2 6 8 | 0 9 0 | 0 1 0
0 0 0 | 0 0 6 | 0 0 4
---------|---------|---------
0 0 0 | 0 0 0 | 2 3 9
0 0 0 | 0 0 0 | 0 0 0
4 1 5 | 0 0 0 | 0 0 0
---------|---------|---------
9 0 0 | 5 0 0 | 0 0 0
0 2 0 | 0 1 0 | 7 4 0
0 0 0 | 2 0 0 | 9 0 5
**************************************************
**************************************************
7 4 3 | 8 2 1 | 5 6 9
2 6 8 | 0 9 0 | 0 1 0
0 0 0 | 0 0 6 | 0 0 4
---------|---------|---------
0 0 0 | 0 0 0 | 2 3 9
0 0 0 | 0 0 0 | 0 0 0
4 1 5 | 0 0 0 | 0 0 0
---------|---------|---------
9 0 0 | 5 0 0 | 0 0 0
0 2 0 | 0 1 0 | 7 4 0
0 0 0 | 2 0 0 | 9 0 5
**************************************************
**************************************************
7 4 3 | 8 2 1 | 5 6 0
2 6 8 | 1 9 0 | 0 1 0
0 0 0 | 0 0 6 | 0 0 4
---------|---------|---------
0 0 0 | 0 0 0 | 2 3 9
0 0 0 | 0 0 0 | 0 0 0
4 1 5 | 0 0 0 | 0 0 0
---------|---------|---------
9 0 0 | 5 0 0 | 0 0 0
0 2 0 | 0 1 0 | 7 4 0
0 0 0 | 2 0 0 | 9 0 5
**************************************************
**************************************************
7 4 3 | 8 2 1 | 5 6 0
2 6 8 | 2 9 0 | 0 1 0
0 0 0 | 0 0 6 | 0 0 4
---------|---------|---------
0 0 0 | 0 0 0 | 2 3 9
0 0 0 | 0 0 0 | 0 0 0
4 1 5 | 0 0 0 | 0 0 0
---------|---------|---------
9 0 0 | 5 0 0 | 0 0 0
0 2 0 | 0 1 0 | 7 4 0
0 0 0 | 2 0 0 | 9 0 5
**************************************************
**************************************************
7 4 3 | 8 2 1 | 5 6 0
2 6 8 | 3 9 0 | 0 1 0
0 0 0 | 0 0 6 | 0 0 4
---------|---------|---------
0 0 0 | 0 0 0 | 2 3 9
0 0 0 | 0 0 0 | 0 0 0
4 1 5 | 0 0 0 | 0 0 0
---------|---------|---------
9 0 0 | 5 0 0 | 0 0 0
0 2 0 | 0 1 0 | 7 4 0
0 0 0 | 2 0 0 | 9 0 5
**************************************************
最初の行の最後に注意してください。解決策を探して 8 に進み、次に 9 に進みます。9 は正当ではなく、for ループの最後に達したため、ゼロに置き換えて続行します。より完全な解決策を得るために、最初の行で別の数字を試すように戻すにはどうすればよいですか?
これが私の再帰関数です...
bool DoTheWork::addSquare(int& depth, ostream& outStream){
for(int i = ONE; i <= NINE; ++i){
for(int j = ONE; j <= NINE; ++j){
if(i == NINE && j == NINE && board.getSquare(NINE, NINE) != ZERO){
cout << i << " " << j << endl;
return true;
}
//cout << "original" << board.getSquare(i, j) << "coord: " << i << ", " << j << endl;
if(board.getSquare(i, j) == ZERO){
//cout << "original: " << board.getSquare(i, j) << "coord: " << i << ", " << j << endl;
for(int k = ONE; k <= NINE; ++k){
board.setSquare(i, j, k);
board.display(outStream);
if(board.isLegal()){
return addSquare(depth, outStream);
}
else{
board.unsetSquare(i, j);
}
}
}
}
}
board.display(outStream);
return false;
}