数独问题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
相似问题