Рекурсивный возврат в стеке

Question

Рекурсивный возврат в стеке

Я пытаюсь написать программу, которая будет использовать обратный трекинг для создания решателя судоку. Мне удалось создать черную сетку Судоку, и я могу проверить, является ли ход правильным ходом. Моя программа работает нормально, пока для квадрата не выбрано больше одного числа.

Проблема: вы посмотрите на мой метод Solve и увидите, как я мог бы изменить его, чтобы он вернулся, изменил ответ и снова двинулся вперед. Я назвал имена всех других моих методов выше и каждого из этих работ.

Пример ввода:

int board[ROWS][COLS] = {
{ 6, 0, 3, 0, 2, 0, 0, 9, 0 },
{ 0, 0, 0, 0, 5, 0, 0, 8, 0 },
{ 0, 2, 0, 4, 0, 7, 0, 0, 1 },
{ 0, 0, 6, 0, 1, 4, 3, 0, 0 },
{ 0, 0, 0, 0, 8, 0, 0, 5, 6 },
{ 0, 4, 0, 6, 0, 3, 2, 0, 0 },
{ 8, 0, 0, 2, 0, 0, 0, 0, 7 },
{ 0, 1, 0, 0, 7, 5, 8, 0, 0 },
{ 0, 3, 0, 0, 0, 6, 1, 0, 5 }
};

bool sudokuBoard::emptyCell(int i, int j);

bool sudokuBoard::isValidCol(int i, int j, int number);

bool sudokuBoard::isValidRow(int i, int j, int number);

bool sudokuBoard::isValidSquare(int i, int j, int number);

bool sudokuBoard::validMove(int i, int j, int number);

void sudokuBoard::solvePuzzle(int row, int col) {

for (int i = 1; i < 10; i++) {
if (validMove(row, col, i)) {
board[row][col] = i;
showBoard();
}
}
if (row < 8 && col < 8) {
if (col < 8) {
solvePuzzle(row, col + 1);
}
else {
col = 0;
solvePuzzle(row + 1, col);
}
}
}

Пример токового выхода:

  6  5  3|  1  2  8|  4  9  0|
0  0  0|  0  5  0|  0  8  0|
0  2  0|  4  0  7|  0  0  1|
--------------------------------
0  0  6|  0  1  4|  3  0  0|
0  0  0|  0  8  0|  0  5  6|
0  4  0|  6  0  3|  2  0  0|
--------------------------------
8  0  0|  2  0  0|  0  0  7|
0  1  0|  0  7  5|  8  0  0|
0  3  0|  0  0  6|  1  0  5|

моя программа останавливается на последнем 0 в первой строке, поскольку решения не существует, если только предыдущие 4 не поменяются на 7, программа завершается.

2

c++recursive-backtracking

Решение

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

Это то, что решило это для меня. Спасибо за твою помощь.

bool sudokuBoard::solvePuzzle() {
int row, col;

if (emptyCell(row, col) == false) {
return true;
}

for (int i = 1; i < 10; i++) {
cout << "Trying " << i << " in spot [" << row << "][" << col << "]" << endl;
if (validMove(row, col, i)) {
board[row][col] = i;
showBoard();
if (solvePuzzle()) {
return true;
}
board[row][col] = 0;
}
}
return false;
}

0

Источник

Accepted Answer

Возвращение в исходное положение может быть трудно обернуть ваше внимание в первый раз, поэтому мы предпримем этот шаг за шагом, начиная с некоторого псевдокода о том, что у вас есть сейчас:

    while(puzzlenotsolved)
{
foreach row
{
findEmptySquare
{
findValidMove(1-9)
}
}
}

Это, конечно, застревает, если для квадрата не может быть найдено правильного хода из-за ранее выбранного значения.

Чтобы противостоять этому, мы должны вернуться false когда у нас заканчиваются действительные ходы в квадрате, нам также нужно отменить наше предположение, чтобы снова сделать квадрат пустым. Затем нам нужно возобновить цикл в предыдущем квадрате, где мы остановились.

Так что наша функция find valid move (решить головоломку в вашем случае) может выглядеть примерно так:

bool findValidMove
{
if(noEmptySquare) {return true;}  //important bit

findEmptySquare()
for (1-9)
{ if (isvalidMove )
{
assignMoveToSquare
}
if (findValidMove) {return true}  //important bit

unassignMoveFromSquare
}
return false; //no values valid in this square, a previous square has a wrong value
}

Теперь это считается методом грубой силы, и его можно оптимизировать, но для вашего вопроса давайте вернемся к работе, и вы можете позаботиться об оптимизации скорости позже, если хотите.

Обратите внимание на два места, которые я прокомментировал как важные биты, во-первых, это показатель того, что не осталось пустых квадратов. Поскольку ваша программа назначает только правильные ходы, головоломка должна быть завершена и исправлена, поэтому программа возвращает true. Это базовый случай, в общем случае рекурсивным функциям нужен базовый случай.

Второй важный бит — это когда функция рекурсивно вызывает себя. Обратите внимание, что он все еще находится в цикле, поэтому, когда вызов возвращает false, он возобновит цикл в предыдущем вызове. Каждый звонок накладывается на другой, как в этот пример кроме нашего примера возвращается обратно в цикл.

Обратите внимание, что ячейка не будет назначена до тех пор, пока не вернется рекурсивная функция, это позволит вам не беспокоиться о добавлении 1 к вашим строкам и столбцам, как вы упоминали в своем комментарии. Все, что вам нужно сделать, это иметь надежный метод findEmptySquare, а остальное позаботится о рекурсии.

Ваш showBoard(); метод будет иметь неоценимое значение для отладки, я бы сказал, сразу после assignMoveToSquare

Надеюсь, это поможет, вы действительно близки, так что я думаю, что так и будет. Если у вас есть дополнительные вопросы, не стесняйтесь комментировать это, и я постараюсь связаться с вами, когда у меня будет время.

4