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

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, программа завершается.

Answer 1

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

    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

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

Answer 2

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

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;
}