数独问题leetcode37

Question

 //老师，看了半天也觉得逻辑很对，帮帮我，看下子，哪里错了
 //i均是从0开始计数
    private boolean[][] col = new boolean[9][10];          //col[i][j] = true ,代表第i列数字j被用了
    private boolean[][] row = new boolean[9][10];          //row[i][j] = true ,代表第i行数字j被用了
    private boolean[][] pane = new boolean[9][10];         //pane[i][j] = true ,代表第i个3*3的放格中数字j被用了

    public void solveSudoku(char[][] board) {
        int countNum = 0;
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = charToInt(board[i][j]);
                    col[j][num] = true;
                    row[i][num] = true;
                    pane[getPaneNumber(i, j)][num] = true;
                }
            }
        putNumber( board, 0, 0);

    }

    //rowNum,colNum为当前处理字符的坐标
    private void putNumber( char[][] board, int rowNum, int colNum) {
       if (rowNum == 9)
           return;
       //不是空格字符，直接处理下一个字符
        if (board[rowNum][colNum] != '.') {
            if (colNum == 8)
                putNumber(board, rowNum + 1, 0);
            else
                putNumber( board, rowNum, colNum + 1);
            return;
        }
        //处理字符
        for (int i = 1; i <= 9; i++) {
            if (!col[colNum][i] && !row[rowNum][i] && !pane[getPaneNumber(rowNum, colNum)][i]) {
                board[rowNum][colNum] = String.valueOf(i).charAt(0);
                col[colNum][i] = true;
                row[rowNum][i] = true;
                pane[getPaneNumber(rowNum, colNum)][i] = true;
                if (colNum == 8)
                    putNumber( board, rowNum + 1, 0);
                else
                    putNumber( board, rowNum, colNum + 1);
                col[colNum][i] = false;
                row[rowNum][i] = false;
                pane[getPaneNumber(rowNum, colNum)][i] = false;
            }
        }

    }


    //根据横纵坐标获得代表方格的数字
    private int getPaneNumber(int x, int y) {
        if (x >= 0 && x < 3 && y >= 0 && y < 3)
            return 0;
        if (x >= 3 && x < 6 && y >= 0 && y < 3)
            return 1;
        if (x >= 6 && x < 9 && y >= 0 && y < 3)
            return 2;

        if (x >= 0 && x < 3 && y >= 3 && y < 6)
            return 3;
        if (x >= 3 && x < 6 && y >= 3 && y < 6)
            return 4;
        if (x >= 6 && x < 9 && y >= 3 && y < 6)
            return 5;

        if (x >= 0 && x < 3 && y >= 6 && y < 9)
            return 6;
        if (x >= 3 && x < 6 && y >= 6 && y < 9)
            return 7;
//        if (x >= 6 && x < 9 && y >= 6 && y < 9)
        return 8;
    }

    private int charToInt(char c) {
        return Integer.valueOf(String.valueOf(c));
    }

Answer 1

提问者 蓝胖子的编程梦 2018-06-02 00:16:55

终于搞懂了，原来我在回溯的时候没有把board数组的字符复原，导致重新循环的时候，跳过了原本为空的字符。哈哈哈哈啊哈哈

• liuyubobobo #1

  继续加油：）