数独问题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数组的字符复原,导致重新循环的时候,跳过了原本为空的字符。哈哈哈哈啊哈哈
012018-06-02
相似问题