Судоку решил найти решение для неразрешимой судоку

Question

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

bool Sudoku::solve(int row, int col){ 
if (board[row][col] != 0){ 
    int next_col = col; 
    int next_row = row; 

    next_col++; 

    if (next_col > 8){ 
     next_row++; 
     next_col = 0; 
    } 

    if (next_row > 8){ 
     return true; 
    } else { 
     if (solve(next_row, next_col)) 
      return true; 
    } 
} 

for (int number = 1; number <= 9; number++){ 
    board[row][col] = number; 

    if (check_row(row, number) 
    && check_col(col, number) 
    && check_box(row, col, number)){ 
     int next_row = row; 
     int next_col = col+1; 

     if (next_col > 8){ 
      next_col = 0; 
      next_row++; 
     } 

     if (next_row > 8){ 
      return true; 
     } 

     if (solve(next_row, next_col)) 
      return true; 
    } 
} 

board[row][col] = 0; 
return false; 

}

плата является 2D целочисленный массив. Я знаю, что я мог бы использовать какую-то структуру вместо целого, которая будет хранить, если номер был изначально там или нет, однако это решение не очень привлекательно для меня. Есть ли другой путь ?

Answer 1

В чеке в самом начале, когда установлена ​​клетка,

if (board[row][col] != 0){ 
    int next_col = col; 
    int next_row = row; 

    next_col++; 

    if (next_col > 8){ 
     next_row++; 
     next_col = 0; 
    } 

    if (next_row > 8){ 
     return true; 
    } else { 
     if (solve(next_row, next_col)) 
      return true; 
    } 
} 

добавить

else { 
    return false; 
} 

или изменить последний

return solve(next_row, next_col); 

, чтобы избежать изменений данными номера. Как и в случае, если головоломка не может быть решена - даже после ошибочного предположения предыдущей ячейки, где оригинал может быть разрешен, он с радостью продолжает менять число в ячейке.

Answer 2

Вы можете создать набор всех посещенных мест.

Пример реализации будет заключаться в создании std::set<pair<int, int> > visited, который содержит каждое посещенное местоположение. Затем, если местоположение было посещено, не изменяйте значение.