# 096 : 数独

数独（あるいはナンバープレース、ナンプレ）とは人気があるパズルの名前である。起源は不明だが、その評判はラテン方格 (Latin Squares) と呼ばれる同様な、そしてはるかに難しいパズルを考案したレオンハルト・オイラーの貢献によるものに違いない。しかしながら、数独パズルの目的は、9×9の格子に対して、それぞれの行、それぞれの列、それぞれの3×3の枠が1から9の数字を含むように空白（もしくは0）を埋めることである。下に、一般的なパズルの開始状態とその解答の例を示す。

![](https://1547764285-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MCo5FMwYZBPuRk-sNIY%2F-Mf6YrlFXi1Ur_xN5y3I%2F-Mf6ZRM8XJK-lap4KsEz%2Fimage.png?alt=media\&token=5fbfa671-6939-46eb-a7f2-bf8aed1c12d7)

![](https://1547764285-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MCo5FMwYZBPuRk-sNIY%2F-Mf6YrlFXi1Ur_xN5y3I%2F-Mf6Z_B8nVgZoUAOOr_B%2Fimage.png?alt=media\&token=88f2a6f1-c242-479d-b268-43347eb45e64)

うまく作られている数独パズルは、ただ一つの解を持ち、推論によって解くことができる。ただし、選択肢を消去するために「仮定とテスト」方式を用いる必要があるかもしれない（これについては様々な意見がある）。

探索の複雑さがパズルの難易度を決定する。上に挙げた例は、単純で直接的な推論によって解く事ができるため、簡単であると考えられる。

6kバイトのテキストファイル [sudoku.txt](https://projecteuler.net/project/resources/p096_sudoku.txt)（右クリックで "名前をつけてリンク先を保存"）には、ただ一つの解を持つ、様々な難易度の50の数独パズルが含まれている。（上の例題はこのファイルにおける最初のパズルである。）

50すべてのパズルを解き、それぞれの解答の左上隅にある3桁の数の合計を求めよ。例えば上の解答例の左上隅の3桁の数は483である。
