スキップしてメイン コンテンツに移動

投稿

8月, 2010の投稿を表示しています

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