Я строю рекурсивный решатель судоку, но столкнулся с проблемой. Кажется, моя функция легальности принимает 0 в окончательном ответе. Это не назначение нулей, однако, нули используются в качестве заполнителя, чтобы отметить незаполненное значение. Когда я запускаю программу, я получаю вывод, как это …
**************************************************
7 4 3 | 8 2 1 | 0 0 0
0 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 0 0
0 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
0 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 | 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
**************************************************
Как видно из этих распечаток головоломки по мере ее решения, она принимает ноль в качестве последнего числа в первом столбце. Я не могу найти где-нибудь в своем коде, где это позволило бы это случиться. Кроме того, я заметил, что когда я компилировал, иногда я думал, что столкнусь с памятью, в которой должен был находиться, но это позволяет мне уйти. Я чувствую, что мои функции иногда вынимают вещи из воздуха.
Вот мои легальные функции:
bool Board::isRowLegal(int row){
bool present[9] = {};
for(int i = 1; i < theBoard.size(); ++i){
if(theBoard[row][i] != 0){
if(present[(theBoard[row][i]) - 1]){
return false;
}
present[(theBoard[row][i]) - 1] = true;
}
}
return true;
}
bool Board::isColumnLegal(int column){
bool present[9] = {};
for(int i = 1; i < theBoard.size(); ++i){
if(theBoard[i][column] != 0){
if(present[(theBoard[i][column]) - 1]){
return false;
}
present[(theBoard[i][column]) - 1] = true;
}
}
return true;
}
bool Board::isPanelLegal(int rowStart, int colStart){
// Store the numbers in the panel in one vector.
vector<int> currentPanel;
for(int i = rowStart; i < rowStart + THREE; ++i){
cout << endl;
for(int j = colStart; j < colStart + THREE; ++j){
cout << theBoard[i][j];
currentPanel.push_back(theBoard[i][j]);
}
}
bool present[9] = {};
cout << endl << currentPanel.size() << endl;
for(int k = 0; k < currentPanel.size(); ++k){
if(currentPanel[k] != 0){
if(present[currentPanel[k] - 1]){
return false;
}
present[currentPanel[k] - 1] = true;
}
}
return true;
}
Я знаю, что это сбивает с толку подписчиков, но, как правило, я начинаю с нижнего индекса, чтобы найти числа. Таким образом, 7 в первом ряду, первом столбце — это координаты 1, 1. Не 0, 0.
Я считаю, что это связанная проблема, возможно, я не проверяю все цифры в одном случае, однако мои молодые программистские глаза не видят этого.
Также кто-то может объяснить, почему в isPanelLegal я должен поставить present [currentPanel [k] — 1]. Я могу понять, почему в других, потому что вектор начинается с 1, но в isPanelLegal, вектор начинается с нуля, так как я только что создал его в первой части функции. Он работает с -1 и не работает без него.
Рекурсивная часть …
if(board.isBoardFull()){
cout << "here" << endl;
board.display(outStream);
return true;
}
for(int i = ONE; i <= NINE; ++i){
for(int j = ONE; j <= NINE; ++j){
//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);
if(board.isLegal(1, 10, 1, 10)){
board.display(outStream);
addSquare(depth, outStream);
return true;
}
board.unsetSquare(i, j);
}
}
}
}
board.display(outStream);
return false;
}
Спасибо.
Я думаю, что ваша проблема здесь:
bool Board::isRowLegal(int row){
bool present[9] = {};
for(int i = 1; i < theBoard.size(); ++i){
if(theBoard[row][i] != 0){ // This line
if(present[(theBoard[row][i]) - 1]){
return false;
}
present[(theBoard[row][i]) - 1] = true;
}
}
return true;
}
В вашем цикле for, если каждое число равно 0, функция вернет true. Что вам нужно сделать, так это вернуть false, если вы найдете 0 (при условии, что 0 никогда не является допустимым, что, как я думаю, имеет место в случае с судоку).
bool Board::isRowLegal(int row){
bool present[9] = {};
for(int i = 1; i < theBoard.size(); ++i){
if(theBoard[row][i] == 0)
return false;
if(present[(theBoard[row][i]) - 1])
return false;
present[(theBoard[row][i]) - 1] = true;
}
}
return true;
}
То же самое для столбца.
Редактировать: О, я только что понял, что вам также может понадобиться <= theBoard.size () в ваших циклах for. Если вы пытаетесь перейти с 1-9, а размер доски 9, < займет у вас 1-8. Это еще одна причина, почему вы должны начинать с 0, как говорили другие люди. Все становится запутанным, если вы начинаете массив с 1 без уважительной причины.
Других решений пока нет …