最难数独的快速解法 – python

转载于: www.jianshu.com/p/1b2ee6539…

• python3、numpy的学习
• 递归算法

世界最难数独

芬兰数学家因卡拉，花费3个月时间设计出了世界上迄今 难度最大的 数独游戏，而且它只有一个答案。因卡拉说只有思考能力最快、头脑最聪明的人才能激活成功教程这个游戏

数独解法

有很多，这里练习用排除+递归回溯法。

1. 排除法很直观

• 根据已知的数字，排除同一行、同一列、同一九宫格内相同的数字
• 同一九宫格内，如果存在某一行/列上猜测有两个同一数字，那大数独同一行/列也能排除
• 新解出的数字，加入到先进先出队列(栈) – FIFO Queue

2. 猜测+回溯法

• 如果已经没有任何已知的数字，那就只能猜测了
• 把猜测数字加入到后进先出（LastInFirstOut）队列 – LIFO Queue
• 递归写法，画流程图会比较容易理解！！

根据流程图写代码，会很轻松，逻辑也不会乱：

 def sudo_solve_iter(self): # 排除法解题 self.sudo_exclude() # logger.debug(f'excluded, current result:\n{self.value}') if self.verify_value(): if self.get_num_count() == 81: # solve success return else: logger.info(f'current no. of fixed answers: {self.get_num_count()}') point = self.get_best_point() index = 0 items = self.add_to_queue(point, index) logger.info(f'add to LIFO queue and guessing {items[index]}/{items}: ' f'{[x.point for x in self.record_queue.queue]}') self.guess_times += 1 return self.sudo_solve_iter() while True: if self.record_queue.empty(): # raise Exception('Sudo is wrong, no answer!') logger.error(f'Guessed {self.guess_times} times. Sudo is wrong, no answer!') exit() # check value ERROR, need to try next index or rollback record = self.record_queue.get() point = record.point index = record.point_index + 1 items = record.value[point] self.value = record.value logger.info(f'Recall! Pop previous point, {items} @{point}') # 判断索引是否超出范围 # if not exceed，则再回溯一次 if index < len(items): items = self.add_to_queue(point, index) logger.info(f'guessing next index: answer={items[index]}/{items} @{point}') self.guess_times += 1 return self.sudo_solve_iter() 复制代码

实战

最难数独，需要猜测109次？！确实很变态啊！不过就算i3级别的旧电脑，也只要0.3s左右。

/home/kevin/git/sudo-py3/venv/bin/python /home/kevin/git/sudo-py3/sudo-recur.py DEBUG:__main__:current no. of fixed answers: 21 DEBUG:__main__:add to LIFO queue and guessing 3/[3, 9]: [(7, 6)] DEBUG:__main__:current no. of fixed answers: 22 DEBUG:__main__:add to LIFO queue and guessing 5/[5, 9]: [(7, 6), (6, 6)] DEBUG:__main__:current no. of fixed answers: 25 DEBUG:__main__:add to LIFO queue and guessing 6/[6, 8, 9]: [(7, 6), (6, 6), (5, 6)] DEBUG:__main__:verify failed. dup in col 0 DEBUG:__main__:Recall! Pop previous point, [6, 8, 9] @(5, 6) DEBUG:__main__:guessing next index: answer=8/[6, 8, 9] @(5, 6) DEBUG:__main__:current no. of fixed answers: 29 DEBUG:__main__:add to LIFO queue and guessing 2/[2, 4, 6]: [(7, 6), (6, 6), (5, 6), (5, 1)] DEBUG:__main__:verify failed. dup in col 0 ... DEBUG:__main__:guessing next index: answer=3/[2, 3, 8] @(4, 3) DEBUG:__main__:current no. of fixed answers: 41 DEBUG:__main__:add to LIFO queue and guessing 1/[1, 4]: [(7, 6), (6, 6), (6, 1), (6, 3), (4, 3), (1, 1)] DEBUG:__main__:verify failed. dup in row 0 DEBUG:__main__:Recall! Pop previous point, [1, 4] @(1, 1) DEBUG:__main__:guessing next index: answer=4/[1, 4] @(1, 1) DEBUG:__main__:current no. of fixed answers: 42 DEBUG:__main__:add to LIFO queue and guessing 1/[1, 6, 8]: [(7, 6), (6, 6), (6, 1), (6, 3), (4, 3), (1, 1), (4, 1)] DEBUG:__main__:verify failed. dup in row 4 DEBUG:__main__:Recall! Pop previous point, [1, 6, 8] @(4, 1) DEBUG:__main__:guessing next index: answer=6/[1, 6, 8] @(4, 1) DEBUG:__main__:verify failed. dup in row 0 DEBUG:__main__:Recall! Pop previous point, [1, 6, 8] @(4, 1) DEBUG:__main__:guessing next index: answer=8/[1, 6, 8] @(4, 1) DEBUG:__main__:verify failed. dup in row 0 DEBUG:__main__:Recall! Pop previous point, [1, 6, 8] @(4, 1) DEBUG:__main__:Recall! Pop previous point, [1, 4] @(1, 1) DEBUG:__main__:Recall! Pop previous point, [2, 3, 8] @(4, 3) DEBUG:__main__:guessing next index: answer=8/[2, 3, 8] @(4, 3) DEBUG:__main__:current no. of fixed answers: 33 DEBUG:__main__:add to LIFO queue and guessing 2/[2, 3]: [(7, 6), (6, 6), (6, 1), (6, 3), (4, 3), (3, 3)] DEBUG:__main__:current no. of fixed answers: 42 DEBUG:__main__:add to LIFO queue and guessing 3/[3, 4]: [(7, 6), (6, 6), (6, 1), (6, 3), (4, 3), (3, 3), (7, 1)] DEBUG:__main__:current no. of fixed answers: 45 DEBUG:__main__:add to LIFO queue and guessing 1/[1, 6]: [(7, 6), (6, 6), (6, 1), (6, 3), (4, 3), (3, 3), (7, 1), (4, 1)] DEBUG:__main__:verify failed. dup in row 0 DEBUG:__main__:Recall! Pop previous point, [1, 6] @(4, 1) DEBUG:__main__:guessing next index: answer=6/[1, 6] @(4, 1) INFO:__main__:Done! guessed 109 times, in 0.540sec INFO:__main__:Puzzle: [[8 0 0 0 0 0 0 0 0] [0 0 3 6 0 0 0 0 0] [0 7 0 0 9 0 2 0 0] [0 5 0 0 0 7 0 0 0] [0 0 0 0 4 5 7 0 0] [0 0 0 1 0 0 0 3 0] [0 0 1 0 0 0 0 6 8] [0 0 8 5 0 0 0 1 0] [0 9 0 0 0 0 4 0 0]] INFO:__main__:Answer: [[8 1 2 7 5 3 6 4 9] [9 4 3 6 8 2 1 7 5] [6 7 5 4 9 1 2 8 3] [1 5 4 2 3 7 8 9 6] [3 6 9 8 4 5 7 2 1] [2 8 7 1 6 9 5 3 4] [5 2 1 9 7 4 3 6 8] [4 3 8 5 2 6 9 1 7] [7 9 6 3 1 8 4 5 2]] 复制代码

源码：github.com/kevinnj/s…

参考：Python秒解最难数独 – 杨仕航的博客 http://yshblog.com/blog/74

预告1：会写一个小网站，秒解任何你输入的数独题目 mysudo.herokuapp.com/

• 预告2：添加扫一扫功能，人工智能识别拍摄的数独题目，Opencv抓图 + CNN卷积网络识别。
• 预告3：集成到微信小程序