leetcode37.解数独

Question

问题遇到的现象和发生背景

CSDN https://mp.csdn.net/mp_blog/creation/editor/122429509

问题相关代码，请勿粘贴截图

class Solution {
public void solveSudoku(char[][] board) {
getNext(board);
}

private static List<String> getPossibleStatus(char[][] board,int x,int y){
    List<String> ans = new ArrayList<String>();
    ans.add("1");
    ans.add("2");
    ans.add("3");
    ans.add("4");
    ans.add("5");
    ans.add("6");
    ans.add("7");
    ans.add("8");
    ans.add("9");

    //检查行
    for(int i=0;i<9;i++){
        if(board[x][i]!='.'){
            if(board[x][i]==(char)i){
                ans.remove("1");
            }else if(board[x][i]=='2'){
                ans.remove("2");
            }else if(board[x][i]=='3'){
                ans.remove("3");
            }else if(board[x][i]=='4'){
                ans.remove("4");
            }else if(board[x][i]=='5'){
                ans.remove("5");
            }else if(board[x][i]=='6'){
                ans.remove("6");
            }else if(board[x][i]=='7'){
                ans.remove("7");
            }else if(board[x][i]=='8'){
                ans.remove("8");
            }else if(board[x][i]=='9'){
                ans.remove("9");
            }
        }
    }
    //检查列
    for(int i=0;i<9;i++){
        if(board[i][y]!='.'){
            if(board[i][y]=='1'){
                ans.remove("1");
            }else if(board[i][y]=='2'){
                ans.remove("2");
            }else if(board[i][y]=='3'){
                ans.remove("3");
            }else if(board[i][y]=='4'){
                ans.remove("4");
            }else if(board[i][y]=='5'){
                ans.remove("5");
            }else if(board[i][y]=='6'){
                ans.remove("6");
            }else if(board[i][y]=='7'){
                ans.remove("7");
            }else if(board[i][y]=='8'){
                ans.remove("8");
            }else if(board[i][y]=='9'){
                ans.remove("9");
            }
        }
    }
    //检查九宫格
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(board[(x/3)*3+i][(y/3)*3+j]!='.'){
                if(board[(x/3)*3+i][(y/3)*3+j]=='1'){
                    ans.remove("1");
                }else if(board[(x/3)*3+i][(y/3)*3+j]=='2'){
                    ans.remove("2");
                }else if(board[(x/3)*3+i][(y/3)*3+j]=='3'){
                    ans.remove("3");
                }else if(board[(x/3)*3+i][(y/3)*3+j]=='4'){
                    ans.remove("4");
                }else if(board[(x/3)*3+i][(y/3)*3+j]=='5'){
                    ans.remove("5");
                }else if(board[(x/3)*3+i][(y/3)*3+j]=='6'){
                    ans.remove("6");
                }else if(board[(x/3)*3+i][(y/3)*3+j]=='7'){
                    ans.remove("7");
                }else if(board[(x/3)*3+i][(y/3)*3+j]=='8'){
                    ans.remove("8");
                }else if(board[(x/3)*3+i][(y/3)*3+j]=='9'){
                    ans.remove("9");
                }
            }
        }
    }
    return ans;
}

//填入数据
private static char[][] fillNum(char[][] board,int x,int y,char ch){
    board[x][y] = ch;
    return board;
}

//更新
private static void getNext(char[][] board){
    boolean flag = true;
    for(int a=0;a<9;a++) {
        for (int b = 0; b < 9; b++) {
            if (board[a][b] == '.') {
                flag = false;
            }
        }
    }
    if(flag){
        return;
    }
    for(int x=0;x<9;x++) {
        for (int y=0;y<9;y++) {
            if (board[x][y] == '.') {
                List<String> ans = new ArrayList<String>();
                ans = getPossibleStatus(board, x, y);
                if (ans.size() == 1) {//找到唯一值
                    String temp = ans.get(0);
                    char[] target = temp.toCharArray();
                    board = fillNum(board, x, y, target[0]);
                    getNext(board);
                }
            }
        }
    }
}

}

运行结果及报错内容

只能求解每一步都仅有一个选项的数独，若出现某一步有两个或者以上的选项（但解只有一个）就会运行出错。

我的解答思路和尝试过的方法

思路：根据三个要求（1）每行的数不能重复（2）每列的数不能重复（3）九宫格内的数不能重复 求出每个格子最后可以填的数，将这些数放入一个列表中。如果列表的长度为1，即表明该格子只有一种选择，那么唯一可选的数就是解，将这个数填入数独中。以此类推，按上述方法多次循环遍历二维数组期望可以得到解。

我想要达到的结果

成功AC

Answer 1

改一下getNext方法，某一步有两个或者以上的选项时依次递归试验填充

class Solution {
    public void solveSudoku(char[][] board) {
        getNext(board,0,0);
    }
    private static List<String> getPossibleStatus(char[][] board,int x,int y){
        List<String> ans = new ArrayList<String>();
        ans.add("1");
        ans.add("2");
        ans.add("3");
        ans.add("4");
        ans.add("5");
        ans.add("6");
        ans.add("7");
        ans.add("8");
        ans.add("9");

        //检查行
        for(int i=0;i<9;i++){
            if(board[x][i]!='.'){
                if(board[x][i]==(char)i){
                    ans.remove("1");
                }else if(board[x][i]=='2'){
                    ans.remove("2");
                }else if(board[x][i]=='3'){
                    ans.remove("3");
                }else if(board[x][i]=='4'){
                    ans.remove("4");
                }else if(board[x][i]=='5'){
                    ans.remove("5");
                }else if(board[x][i]=='6'){
                    ans.remove("6");
                }else if(board[x][i]=='7'){
                    ans.remove("7");
                }else if(board[x][i]=='8'){
                    ans.remove("8");
                }else if(board[x][i]=='9'){
                    ans.remove("9");
                }
            }
        }
        //检查列
        for(int i=0;i<9;i++){
            if(board[i][y]!='.'){
                if(board[i][y]=='1'){
                    ans.remove("1");
                }else if(board[i][y]=='2'){
                    ans.remove("2");
                }else if(board[i][y]=='3'){
                    ans.remove("3");
                }else if(board[i][y]=='4'){
                    ans.remove("4");
                }else if(board[i][y]=='5'){
                    ans.remove("5");
                }else if(board[i][y]=='6'){
                    ans.remove("6");
                }else if(board[i][y]=='7'){
                    ans.remove("7");
                }else if(board[i][y]=='8'){
                    ans.remove("8");
                }else if(board[i][y]=='9'){
                    ans.remove("9");
                }
            }
        }
        //检查九宫格
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(board[(x/3)*3+i][(y/3)*3+j]!='.'){
                    if(board[(x/3)*3+i][(y/3)*3+j]=='1'){
                        ans.remove("1");
                    }else if(board[(x/3)*3+i][(y/3)*3+j]=='2'){
                        ans.remove("2");
                    }else if(board[(x/3)*3+i][(y/3)*3+j]=='3'){
                        ans.remove("3");
                    }else if(board[(x/3)*3+i][(y/3)*3+j]=='4'){
                        ans.remove("4");
                    }else if(board[(x/3)*3+i][(y/3)*3+j]=='5'){
                        ans.remove("5");
                    }else if(board[(x/3)*3+i][(y/3)*3+j]=='6'){
                        ans.remove("6");
                    }else if(board[(x/3)*3+i][(y/3)*3+j]=='7'){
                        ans.remove("7");
                    }else if(board[(x/3)*3+i][(y/3)*3+j]=='8'){
                        ans.remove("8");
                    }else if(board[(x/3)*3+i][(y/3)*3+j]=='9'){
                        ans.remove("9");
                    }
                }
            }
        }
        return ans;
    }

    //填入数据
    private static char[][] fillNum(char[][] board,int x,int y,char ch){
        board[x][y] = ch;
        return board;
    }

    //更新方法改为递归
    //更新
    private static boolean getNext(char[][] board,int x, int y){
        if(x==9){
            //所有行已填充，返回true，标志该遍历路线填充成功
            return true;
        }
        if(y==9){
            //超过最后一列格子时，跳到下一行的第一列
            return getNext(board, x+1, 0);
        }
        if(board[x][y]!='.'){
            //已有数字的格子跳过
            return getNext(board, x, y+1);
        }
        //获取所有可以填的数字
        List<String> ans = getPossibleStatus(board, x, y);
        if(ans.size() == 0){
            //没有可以填的数字，返回false，标志该遍历路线填充失败
            return false;
        }
        for(int i=0;i<ans.size();i++){
            //所有可以填的数字依次试验
            String temp = ans.get(i);
            char[] target = temp.toCharArray();
            board = fillNum(board, x, y, target[0]);
            boolean flag = getNext(board, x, y+1);
            //flag表示当前格子填充数字ans[i]后往后遍历是否可以填充成功
            if(flag){
                //返回true,标志该遍历路线填充成功
                return true;
            }
            //flag为false表示当前格子不能填充数字ans[i]，将其回复为点
            fillNum(board, x, y, '.');
        }
        //没有找到可以填充到当前格子，并使得后续遍历填充成功的数字（说明上一步填充有错误），返回false,标志该遍历路线填充失败
        return false;
    }
}