数独问题leetcode37

来源:8-8 回溯法是经典人工智能的基础 N Queens

蓝胖子的编程梦

2018-06-01

 //老师,看了半天也觉得逻辑很对,帮帮我,看下子,哪里错了
 //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));
    }


写回答

1回答

蓝胖子的编程梦

提问者

2018-06-02

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

0
1
liuyubobobo
继续加油:)
2018-06-02
共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程