Как найти первое решение только с этим возвратом

Question

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

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

любой способ, которым я пытался, всегда выдает ошибки компиляции (method must return boolean).

public boolean recursiveSolve(int line, int column) {
    if(line == N) // N is the board size (9)
        return true;
    // if Cell is not empty - continue
    if(board1.getCell(line, column) != 0) { 
        return nextCell(line, column);
    }
    // if Cell empty - solve
    else { 
        for(int i = 1; i <= N; i++) {
            board1.setCell(line, column, i); // set value to cell
            if(board1.boardIsOk())           // check if the board is legal
                return nextCell(line, column); // continue
        }
        board1.setCell(line, column, 0);     // backtrack
    }
}

private boolean nextCell(int line, int column) {
    if(column < 8)
        return recursiveSolve(line, column+1); // progress up the row
    else
        return recursiveSolve(line+1, 0);      // progress down the lines
}

Любая помощь будет наиболее ценной.

Answer 1

Вот некоторый псевдокод для большинства рекурсивных проблем с возвратом.

Если вы уже в решении, сообщите об успехе.

для (каждый возможный выбор в текущей позиции) {

Сделайте этот выбор и сделайте один шаг по пути.

Используйте рекурсию для решения задачи с новой позиции.

Если рекурсивный вызов успешен, сообщите об успехе следующему более высокому уровень.

Возврат из текущего выбора для восстановления состояния в начале петли.

}

Сообщить об ошибке.

Вот некоторый фактический код, основанный на лекции из Стэнфорда. Я переписал его в Java и добавил комментарии.

Boolean SolveSudoku(int[][] grid)
{
    int row, col;

    if(!FindUnassignedLocation(grid, row, col))
        //all locations successfully assigned
        return true;

    for(int num = 1; num <= 9; num++)
    {
        //if number is allowed to be placed in the square
        if(NoConflicts(grid, row, col, num))
        {
            //place the number in the square
            grid[row][col] = num;

            //recur, if successful then stop
            if(SolveSudoku(grid))
                return true;

            //undo and try again
            grid[row][col] = UNASSIGNED;
        }
     }
     //this triggers backtracking from early decisions
     return false;
}

Вам просто нужно реализовать несколько методов, которые довольно тривиальны.

Answer 2

Изменить

        if(board1.boardIsOk())           // check if the board is legal
            return nextCell(line, column); // continue

на

        if(board1.boardIsOk()) {          // check if the board is legal
            boolean solved = nextCell(line, column); // continue
            if (solved) {
                return true;
            ]
        }
    ...
    return false;