Мой алгоритм поиска судоку с возвратом работает только часть времени, может ли кто-нибудь помочь мне улучшить его?

Question

У меня есть рекурсивный алгоритм, который должен принимать частично или полностью пустую доску для судоку (представленная int [] [], где 0 представляет собой пустое пространство) и заполнять ее. Он работает для пустых досок и для большинства других плат, которые я ввожу, но иногда я получаю ошибку переполнения стека, указывающую на строки 54 и 40 (в операторах grid = copyGrid (emptyFill (grid, current + 1, cant));) Кто-нибудь может помочь мне улучшить это?

  //Creating and filling a board Recursive Methods
//Current represents the index for every cell on the board from 0 to 80 inclusive
//cant holds an array of values that the function may not place for each index 
public static int[][] emptyFill(int[][] grid, int current, int[][] cant){
    if(isFull(grid)){
        return grid; 
    } 
    else if(getCellAt(grid, current) == 0){
        for(int i = 1; i <= 9; i ++){
            if(works(i, current / 9, current % 9, grid) && notInCant(cant, current, i)){
                grid[current / 9][current % 9] = i;
                //Line 40 below this comment
                grid = copyGrid(emptyFill(grid, current + 1, cant));
                return grid; 
            }
        }
        /*Backtracks backwards if no number was found by keeping track of what numbers we have tried. Should clear 
        up the cant list if we backtrack further than it */
        for(int i = current; i < cant.length; i ++){
            clearRow(cant, i);
        }
        addToRow(cant, current - 1,  getCellAt(grid, current - 1)); 
        setCellTo(grid, current, 0); 
        setCellTo(grid, current - 1, 0); 
        //Line 54 below this comment
        grid = copyGrid(emptyFill(grid, current -1, cant));
        return grid; 
    }
    else{
        grid  = copyGrid(emptyFill(grid, current + 1, cant));
        return grid; 
    }

}

Answer 1

Удалось исправить, проблема заключалась в том, что, когда программе не удавалось заполнить ячейку, она выполняла «возврат», очищая текущую и предыдущую ячейки, обновляя список чисел, которые не могли быть помещены, а затем снова вызывая программу. Это приводит к тому, что функция вызывается слишком много раз. Вместо этого новая функция просто очищает ячейку и выходит из функции, когда не может найти подходящего числа. Это позволяет функции возвращаться без повторного вызова самой себя и фактически go возвращаться к предыдущему вызову. Это обновленная функция.

public boolean emptyFill(int[][] grid, int current){
    if(isFull(grid)){
        return true; 
    } 
    else if(getCellAt(grid, current) == 0){
        for(int i = 1; i <= 9; i ++){
            if(works(i, current / 9, current % 9, grid) && notInCant( current, i)){
                grid[current / 9][current % 9] = i;
                if( emptyFill(grid, current + 1)) return true; 
                grid[current / 9][current % 9] = 0;
            }
        }
        return false; 
    }
    else{
       return emptyFill(grid, current + 1);
    }

}