Судоку рекурсия, принимая нули как законные

Я строю рекурсивный решатель судоку, но столкнулся с проблемой. Кажется, моя функция легальности принимает 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;
}

Спасибо.

1

Решение

Я думаю, что ваша проблема здесь:

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 без уважительной причины.

0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector