时间戳

首页 > 解决方案 > 我的数独回溯算法仅在部分时间有效，有人可以帮我改进吗？

java - 我的数独回溯算法仅在部分时间有效，有人可以帮我改进吗？

问题描述

我有一个递归算法，它应该采用部分或完全空的数独板（表示一个 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; 
    }

}

标签： javaalgorithmrecursionstack-overflowbacktracking

解决方案

设法修复它，问题是当程序无法填写单元格时，它会通过清除当前和上一个单元格来“回溯”，更新无法放置的数字列表，然后调用程序再次。这会导致函数被调用太多次。新函数只是简单地清除单元格并在找不到合适的数字时退出该函数。这允许函数在不再次调用自身的情况下回溯，并且实际上返回到上一个调用。这是更新的功能。

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

}

推荐阅读