问题描述
给定一个 9 * 9 的数独棋盘（二维数组），其中只有数字 1~9 或字符 .，用字符 . 代表棋盘位置没有填充数字，要求找出数独的解（题目保证每个输入只有唯一的解）。题目链接：**点我**
样例输入输出
输入：
5 3 . . 7 . . . .
6 . . 1 9 5 . . .
. 9 8 . . . . 6 .
8 . . . 6 . . . 3
4 . . 8 . 3 . . 1
7 . . . 2 . . . 6
. 6 . . . . 2 8 .
. . . 4 1 9 . . 5
. . . . 8 . . 7 9
输出：
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
问题解法
直接用递归回溯的方法进行求解，在递归过程中，每次填充数字前先判断要填充的数字是否合法，可以根据此进行剪枝，从而减少不必要的递归。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
| class Solution
{
private static final int BOARD_SIZE = 9;
private boolean isSudokuValid(char[][] board)
{
for (int i = 0; i < BOARD_SIZE; i++)
{
boolean[] isRowCellUsed = new boolean[BOARD_SIZE];
boolean[] isColCellUsed = new boolean[BOARD_SIZE];
for (int j = 0; j < BOARD_SIZE; j++)
{
if (isRowCellUsed[board[i][j] - '1'])
{
return false;
}
else
{
isRowCellUsed[board[i][j] - '1'] = true;
}
if (isColCellUsed[board[j][i] - '1'])
{
return false;
}
else
{
isColCellUsed[board[j][i] - '1'] = true;
}
}
}
int blockSize = 3;
for (int i = 0; i < blockSize; i++)
{
for (int j = 0; j < blockSize; j++)
{
boolean[] isBlockCellUsed = new boolean[BOARD_SIZE];
for (int row = 0; row < blockSize; row++)
{
for (int col = 0; col < blockSize; col++)
{
int cellNum = board[i * blockSize + row][j * blockSize + col] - '1';
if (isBlockCellUsed[cellNum])
{
return false;
}
else
{
isBlockCellUsed[cellNum] = true;
}
}
}
}
}
return true;
}
private boolean isCellNumValid(char[][] board, int rowIndex, int colIndex, int num)
{
char numChar = (char) (num + '0');
for (int i = 0; i < BOARD_SIZE; i++)
{
if (board[rowIndex][i] == numChar)
{
return false;
}
if (board[i][colIndex] == numChar)
{
return false;
}
}
int rowBlockIndex = rowIndex / 3;
int colBlockIndex = colIndex / 3;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (board[rowBlockIndex * 3 + i][colBlockIndex * 3 + j] == numChar)
{
return false;
}
}
}
return true;
}
private boolean findSolveSudoku(char[][] board, int leftCell)
{
if (leftCell == 0)
{
return isSudokuValid(board);
}
for (int i = 0; i < BOARD_SIZE; i++)
{
for (int j = 0; j < BOARD_SIZE; j++)
{
if (board[i][j] == '.')
{
for (int k = 1; k <= 9; k++)
{
if (isCellNumValid(board, i, j, k))
{
board[i][j] = (char) (k + '0');
boolean isFind = findSolveSudoku(board, leftCell - 1);
if (isFind)
{
return true;
}
board[i][j] = '.';
}
}
return false;
}
}
}
return false;
}
public void solveSudoku(char[][] board)
{
int leftCell = 0;
for (int i = 0; i < BOARD_SIZE; i++)
{
for (int j = 0; j < BOARD_SIZE; j++)
{
if (board[i][j] == '.')
{
leftCell++;
}
}
}
findSolveSudoku(board, leftCell);
}
}
|