你一定听说过“数独”游戏。
如【图1.png】,玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个同色九宫内的数字均含1-9,不重复。
数独的答案都是唯一的,所以,多个解也称为无解。
本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的题目。但对会使用计算机编程的你来说,恐怕易如反掌了。
本题的要求就是输入数独题目,程序输出数独的唯一解。我们保证所有已知数据的格式都是合法的,并且题目有唯一的解。
格式要求:
输入9行,每行9个数字,0代表未知,其它数字为已知。
输出9行,每行9个数字表示数独的解。
例如:
输入(即图中题目):
005300000
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700
程序应该输出:
145327698
839654127
672918543
496185372
218473956
753296481
367542819
984761235
521839764
再例如,输入:
800000000
003600000
070090200
050007000
000045700
000100030
001000068
008500010
090000400
程序应该输出:
812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452
资源约定:
峰值内存消耗 < 256M
CPU消耗 < 2000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。
提交时,注意选择所期望的编译器类型。
DFS+回溯
二维数组填数,立马想到DFS。遍历到一个位置先看是不是0,如果是的话通过get_valid_nums拿到可以填的数,然后一个个试,不行就回溯。
递归逻辑倒是不难,主要是get_valid_nums里逻辑的判断,需要从1-9中过滤掉当前行已有的数和当前列已有的数以及当前3*3方格已有的数。
最后还有个check没写,但是想了想,get_valid_nums就已经check了,所以最后根本不用check,只要能填满就是答案。
Code
Python
def process_input():
global maps
for _ in range(9):
maps.append(list(map(int, list(input()))))
def check_map():
""" check maps valid """
return True
def print_maps():
global maps
for i in maps:
for j in i:
print(j, end='')
print()
def check_index(x, y):
return -1 < x < 9 and -1 < y < 9
def get_valid_nums(x, y):
set1 = set(maps[x])
set2 = set()
for i in range(9):
set2.add(maps[i][y])
set3 = set()
for i in range(-(x % 3), 3 - x % 3):
for j in range(-(y % 3), 3 - y % 3):
set3.add(maps[x + i][y + j])
return set(range(1, 10)) - set1 - set2 - set3
def dfs(x, y):
if x == 8 and y == 8 and check_map():
print_maps()
return
if not check_index(x, y):
return
if maps[x][y] == 0:
for num in get_valid_nums(x, y):
maps[x][y] = num
dfs(x + 1 if y == 8 else x, y + 1 if y < 8 else 0)
maps[x][y] = 0
else:
dfs(x + 1 if y == 8 else x, y + 1 if y < 8 else 0)
if __name__ == '__main__':
maps = list()
process_input()
dfs(0, 0)