java - 数独算法无法正确回溯

Question

我正在制作一个数独解算器，它会尝试正方形中的所有可能值，如果没有找到解决方案，则回溯。我相信我有一个几乎可以工作的算法，但到目前为止它只在 16 单元拼图的第 0、2 和 3 行上有效。

public boolean fillBoard(int[][] board, int row, int col){
    int index = 1;              //Next value to try when an empty is found
    boolean solved = false;

    for(int i = row; i < width; i++){       //For each row
        for(int j = col; j < height; j++){  //For each column
            if(board[i][j]==0){             //0 represents empty
                while(!solved){
                    board[i][j] = index;
                    if(checker.checkRow(board[i]) 
                            && checker.checkColumn(columnToArray(board, j))
                            //&& checker.checkBox(<input>)
                            ){
                            solved = fillBoard(board, i, 0);
                    }else{
                        if(index < width){
                            index++;
                        }else{
                            return false;
                        }
                    }
                }
            }
        }
    }
    puzzle = copyPuzzle(board);
    return true;
}

现在它不检查第三个数独规则，它只检查列和行。但是，它仍然应该返回一个遵循行和列规则的谜题，对吧？一旦checkBox方法被写出来，它应该能够解决这个难题。我哪里搞砸了？

编辑一些例子:

对于输入

        {1, 2, 0, 0},
        {0, 4, 0, 0},
        {0, 0, 1, 0},
        {0, 0, 3, 2}

程序返回

1 2 4 3
4 4 4 4
2 3 1 4
4 1 3 2

对于输入

        {1, 0},
        {2, 0}

它正确地解决了这个问题。

对于输入

        { 1, 0, 3, 4, 0, 0 },
        { 4, 0, 6, 0, 0, 3 },
        { 2, 0, 1, 0, 6, 0 },
        { 5, 0, 4, 2, 0, 0 },
        { 3, 0, 2, 0, 4, 0 },
        { 6, 0, 5, 0, 0, 2 }

它返回 Unresolved 谜题

编辑:checkRow 对于那些提出问题的人

public boolean checkRow(int[]row){
    HashSet<Integer> set = new HashSet<Integer>();
    for(int i = 0; i < row.length;i++){
        if(!set.add(row[i]) && row[i]>0){//Duplicate?
            return false;
                    }
                }
    return true;
}

Answer 1

问题在于，当值不正确时，它不会将空间重置为 0，因此，如果它达到了最大索引并且不正确，它就会离开它。下面的代码有效。只是等待我小组中的另一个人提供检查框的方法，但我可能最终不得不自己这样做。

public boolean fillBoard(int[][] board, int row, int col){
    int index = 1;              //Next value to try when an empty is found
    boolean solved = false;

    for(int i = row; i < width; i++){       //For each row
        for(int j = col; j < height; j++){  //For each column
            if(board[i][j]==0){             //0 represents empty
                while(!solved){             //While the puzzle is unsolved
                    board[i][j] = index;    //Try to fill with index
                    if(checker.checkRow(board[i]) 
                            && checker.checkColumn(columnToArray(board, j))
                            //&& checker.checkBox(<input>)
                            ){
                            solved = fillBoard(board, i, 0); //Next space
                    }
                    if(!solved) board[i][j] = 0;
                    if(index < width){
                        index++;
                    }else{
                        return false;
                    }                        
                }
            }
        }
    }
    puzzle = copyPuzzle(board);
    return true;
}