最も難しい数独の高速解法-python
6941 ワード
転載于:www.jianshu.com/p/1b2ee6539… python 3、numpyの学習 再帰アルゴリズム 世界で一番数えにくい
フィンランドの数学者インカラは、世界でこれまでで最も難しい数独ゲームを3ヶ月かけて設計し、答えは一つしかない.カラは思考力が最も速く、頭が最も賢い人だけがこのゲームを解くことができると言ったからだ.
数独解法
たくさんありますが、ここでは排除+再帰遡及法を練習します.排除法は直感的 既知の数字に基づいて、同じ行、同じ列、同じ一九宮格内の同じ数字 を除外する.同一九宮格内に、ある行/列に同じ数字が2つあると推測される場合、大数独同一行/列も を排除することができる.新しく解いた数字は、先進先出キュー(スタック)-FIFO Queue に加わる推測+遡及法 既知の数字がない場合は、 しか推測できません.推測数字を後進先出(LastInFirstOut)キュー-LIFO Queue に加える再帰的な書き方で、フローチャートを描くと分かりやすい!!
フローチャートに基づいてコードを書くと、簡単で論理も乱れません.
実戦
最も数独を数えにくくて、109回推測する必要がありますか?!確かに変態ですね.しかし、i 3級の古いパソコンでも0.3 s程度しかありません.
ソース:github.com/kevinqqnj/s…
参考:Python秒解最难数独-杨仕航のブログhttp://yshblog.com/blog/74
予告1:小さなサイトを書いて、あなたが入力した数独のテーマmysudoを秒解します.herokuapp.com/予告2:スイープ機能を追加し、人工知能で撮影した数独テーマを識別し、Opencvグリップ+CNNボリュームネットワーク識別. 予告3:マイクロメッセージウィジェット に統合
フィンランドの数学者インカラは、世界でこれまでで最も難しい数独ゲームを3ヶ月かけて設計し、答えは一つしかない.カラは思考力が最も速く、頭が最も賢い人だけがこのゲームを解くことができると言ったからだ.
数独解法
たくさんありますが、ここでは排除+再帰遡及法を練習します.
フローチャートに基づいてコードを書くと、簡単で論理も乱れません.
def sudo_solve_iter(self):
#
self.sudo_exclude()
# logger.debug(f'excluded, current result:
{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回推測する必要がありますか?!確かに変態ですね.しかし、i 3級の古いパソコンでも0.3 s程度しかありません.
/home/kevinqq/git/sudo-py3/venv/bin/python /home/kevinqq/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/kevinqqnj/s…
参考:Python秒解最难数独-杨仕航のブログhttp://yshblog.com/blog/74
予告1:小さなサイトを書いて、あなたが入力した数独のテーマmysudoを秒解します.herokuapp.com/