java - 递归回溯的问题

Question

我正在尝试用 Java 实现回溯算法，以解决数独问题。

我 95% 确定问题出在 solve 方法中，但我包含了两个辅助方法以防万一。

我正在做的一些奇怪的事情只是出于要求/方便，比如拼图的硬编码初始值。我确定问题出在我解决方法的底部附近，但我无法弄清楚...

我当前的问题是:处理第一行并找到可能有效的值排列后，我的程序就放弃了。如果我取消注释打印“ROW IS DONE”的行，它将在一行之后打印，并且不再给出输出。为什么它在第一行之后就放弃了？关于我的实现还有什么我应该担心的吗

编辑:我做了很多改变。它越来越近了。如果我在 EXHAUST 为真时打印，我得到一个谜题，除了最后一行之外，每一行都已解决。看起来它在解决/几乎解决之后正在撤消所有内容。我觉得它可能已经达到了完全解决难题的地步，但我没有在正确的时间传回 TRUE ......我现在做错了什么？

import java.util.ArrayList;

class Model
{
    ArrayList<View> views = new ArrayList<View>();
    int[][] grid = 
            {
              {5,3,0,0,7,0,0,0,0},
              {6,0,0,1,9,5,0,0,0},
              {0,9,8,0,0,0,0,6,0},
              {8,0,0,0,6,0,0,0,3},
              {4,0,0,8,0,3,0,0,1},
              {7,0,0,0,2,0,0,0,6},
              {0,6,0,0,0,0,2,8,0},
              {0,0,0,4,1,9,0,0,5},
              {0,0,0,0,8,0,0,7,9}
            };

    /**
     * Method solve
     * 
     * Uses a backtracking algorithm to solve the puzzle.
     */
    public boolean solve(int row, int col) //mutator
    {   
        if(exhaust(row,col)) {printGrid(); return true;}
        int rownext = row;
        int colnext = col+1;
        if(colnext>8)
        {
            colnext = 0;
            rownext++;
        }           
        if(grid[row][col] != 0) solve(rownext,colnext);
        else //is == 0
        {
            for(int num = 1; num <= 9; num++)
            {   
                if(!conflict(row,col,num)) //try a non-conflicting number   
                {
                    grid[row][col] = num;
                    if(solve(rownext,colnext)) return true;                     
                    grid[row][col] = 0;
                }
            }
        }
        return false;       

    }
    /**
     * Method exhaust
     * 
     * Iteratively searches the rest of the puzzle for empty space
     * using the parameters as the starting point.
     *
     * @return true if no 0's are found
     * @return false if a 0 is found
     */
    public boolean exhaust(int row, int col)
    {
        for(int i = row; i <= 8; i++)
        {
            for(int j = col; j <= 8; j++)
            {
                if(grid[i][j] == 0) return false;
            }
        }
        System.out.printf("Exhausted.\n");
        return true;
    }

    /**
     * Method conflict
     * 
     * Checks if the choice in question is valid by looking to see
     * if the choice has already been made in the same row or col,
     * or block. 
     *
     * @return true if there IS a conflict
     * @return false if there is NOT a conflict
     */
    public boolean conflict(int row, int col, int num)
    {
        for(int j = 0; j <= 8; j++)
        {
            if(grid[row][j] == num) {
                return true;
            }
        }   
        for(int i = 0; i <= 8; i++)
        {
            if(grid[i][col] == num) {
                return true;
            }
        }           

        int rowstart = 0;
        if(row>=3) rowstart = 3;
        if(row>=6) rowstart = 6;

        int colstart = 0;
        if(col>=3) colstart = 3;
        if(col>=6) colstart = 6;                    

        for(int r = rowstart; r <= (rowstart + 2); r++)
        {
            for(int c = colstart; c <= (colstart + 2); c++)
            {
                if(grid[r][c] == num) {
                    return true;
                }   
            }   
        }       
        return false;
    }
}

Answer 1

想象一下，您正在平稳地、一行一行地前进，并且没有后退。您的下一个位置是 solve(1,1);。在跟踪代码时注意 rownext。您应该很快就能看到问题所在。如果您不进行回溯，则 rownext 的值应至少保持为 1。