2010年8月23日月曜日

Pythonワンライナーで数独を解いてみた

このブログ記事をはてなブックマークに追加

GIGAZINE数学のエキスパートが3ヶ月かけて作成した「世界一難しい数独」なるものがあったので、即席でPythonワンライナー(一行プログラム)を作ったら1秒かからず解けた。問題を作るのは大変でも解析プログラムで一瞬とは儚い。

python -c "import sys;L=[];S=lambda D:(0in D)and[L.append(D.index(0)),[(D.__setitem__(L[-1],i),S(D),D.__setitem__(L.pop(),0))for i in set(range(1,10))-set(D[L[-1]/9*9:L[-1]/9*9+9]+D[L[-1]%9:81:9]+[d for n in(0,1,2)for d in D[L[-1]/27*27+L[-1]%9/3*3+n*9:L[-1]/27*27+L[-1]%9/3*3+n*9+3]])]]or([sys.stdout.write('%d'%d+('\n'if i%9==8 else' '))for i,d in enumerate(D)],sys.exit());S([int(c)if c!='.'else 0for c in'..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..'])"

コードの最後のリスト内の文字列が9行9列の数独の問題となっていて、上の行の数字から順に入っている。未知の部分はドット(.)で表している。上記のコードではGIGAZINEの問題となっている。

因みにPythonによるもっと効率の良いアルゴリズムについてはSolving Every Sudoku Puzzleが参考になるかも。

以下、ワンライナーによる出力結果。

1 4 5 3 2 7 6 9 8 8 3 9 6 5 4 1 2 7 6 7 2 9 1 8 5 4 3 4 9 6 1 8 5 3 7 2 2 1 8 4 7 3 9 5 6 7 5 3 2 9 6 4 8 1 3 6 7 5 4 2 8 1 9 9 8 4 7 6 1 2 3 5 5 2 1 8 3 9 7 6 4

3 コメント:

匿名 さんのコメント...

そらスクリプトで自動化すれば一瞬で答え出ますよ。

9×9なんですからw

匿名 さんのコメント...

すごい。
できれば解説してほしいです…

匿名 さんのコメント...

こいつクズだなwwwwwww