解数独
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
方法一、递归+迭代法
首先想到的是迭代法，通过标志位的方法，多次迭代判断。
我们首先将未填充数字的位置（i，j）记录下来，遍历到末尾仍然不冲突，表示该数独有解。
整体思路：
1.首先创建标记位数组
2.创建递归函数
3.迭代
具体见代码，有详细的注释。
Swift
func solveSudoku(_ board: inout [[Character]]) {
var row:[[Bool]] = Array(repeating: Array(repeating: false, count: 9), count: 9)
var column:[[Bool]] = Array(repeating: Array(repeating: false, count: 9), count: 9)
var block:[[[Bool]]] = Array(repeating: Array(repeating: Array(repeating: false, count: 9), count: 3), count: 3)
var spaces:[(Int, Int)] = [(Int, Int)]()
for i in 0..<9 {
for j in 0..<9 {
let c = board[i][j];
if c == "." {
//位置空的记录下来，后续填充数字
spaces.append((i, j))
}else {
//有值的标记好，方便判断是否是有效数独
let num:Int = c.wholeNumberValue!
row[i][num-1] = true
column[j][num-1] = true
block[i/3][j/3][num-1] = true
}
}
}
var valid:Bool = false
func dfs(_ board: inout [[Character]], _ pos: Int) {
if pos == spaces.count {
//遍历结束了，无冲突，说明有解了
valid = true
return;
}
let (i, j) = spaces[pos]
for x in 1...9 {
if !valid && !row[i][x-1] && !column[j][x-1] && !block[i/3][j/3][x-1] {
//将当前值尝试填入【i，j】位置，后续不成立
board[i][j] = String(x).first!
//更新标记位
row[i][x-1] = true
column[j][x-1] = true
block[i/3][j/3][x-1] = true
//递归检查下一个空位置是否有解
dfs(&board, pos+1)
//在无解情况下，回溯到当前递归层时，我们还要将上述的三个值重新置为 False
row[i][x-1] = false
column[j][x-1] = false
block[i/3][j/3][x-1] = false
}
}
}
dfs(&board, 0)
}
OC
@implementation Number37 {
NSMutableArray *_rows;
NSMutableArray *_columns;
NSMutableArray *_subbox;
NSMutableArray *_space;
}
- (void)dfs:(NSMutableArray *)board pos:(NSInteger)pos valid:(BOOL *)valid {
//判断是否到末尾了，到末尾则有解
if (pos == _space.count) {
*valid = YES;
return;
}
NSInteger i = [[_space[pos] firstObject] integerValue];
NSInteger j = [[_space[pos] lastObject] integerValue];
for (NSInteger x=1; x<=9; x++) {
if (!*valid && ![_rows[i][x-1] boolValue] && ![_columns[j][x-1] boolValue] && ![_subbox[i/3][j/3][x-1] boolValue]) {
//将当前值填入i，j位置
board[i][j] = [NSString stringWithFormat:@"%ld", x];
//更新标记位
_rows[i][x-1] = _columns[j][x-1] = _subbox[i/3][j/3][x-1] = @(true);
//递归检查下一个空位置是否有解
[self dfs:board pos:pos+1 valid:valid];
//在无解情况下，回溯到当前递归层时，我们还要将上述的三个值重新置为 False
_rows[i][x-1] = _columns[j][x-1] = _subbox[i/3][j/3][x-1] = @(false);
}
}
}
//解数独
- (void)solveSudoku:(NSMutableArray *)board {
_rows = [NSMutableArray arrayWithCapacity:9];
_columns = [NSMutableArray arrayWithCapacity:9];
_subbox = [NSMutableArray arrayWithCapacity:3];
_space = [NSMutableArray array];
//填充数组
for (NSInteger i=0; i<9; i++) {
NSMutableArray *itemArr = [NSMutableArray array];
for (NSInteger j=0; j<9; j++) {
[itemArr addObject:@(false)];
}
[_rows addObject:itemArr];
}
for (NSInteger i=0; i<9; i++) {
NSMutableArray *itemArr = [NSMutableArray array];
for (NSInteger j=0; j<9; j++) {
[itemArr addObject:@(false)];
}
[_columns addObject:itemArr];
}
for (NSInteger i=0; i<3; i++) {
NSMutableArray *itemArr = [NSMutableArray array];
for (NSInteger j=0; j<3; j++) {
NSMutableArray *subItemArr = [NSMutableArray array];
for (NSInteger k=0; k<9; k++) {
[subItemArr addObject:@(false)];
}
[itemArr addObject:subItemArr];
}
[_subbox addObject:itemArr];
}
//先遍历数独，标记已存在的数据
for (NSInteger i=0; i<9; i++) {
for (NSInteger j=0; j<9; j++) {
NSString *c = board[i][j];
if ([c isEqualToString:@"."]) {
[_space addObject:@[@(i), @(j)]];
}else {
NSInteger num = [c integerValue];
_rows[i][num-1] = @(true);
_columns[j][num-1] = @(true);
_subbox[i/3][j/3][num-1] = @(true);
}
}
}
BOOL valid = false;
[self dfs:board pos:0 valid:&valid];
}
@end
