Sudoku

C / C# / Go / Rust / Java / Python / Ruby で数独を解くプログラム

実行環境

お手元のマシンで動かすか、または Vagrant をご利用ください。

vagrant up
vagrant ssh

実行方法

ルートディレクトリ、または言語別のフォルダ内で下記のコマンドを実行してください。

# 実行
make run

# コンパイラ・ランタイムのバージョン表示
make version

手動で実行する際は、以下の引数を渡してください。

数独ファイルへのパス
読み込む行数

入力データ

Kaggle から数独のデータセット (sudoku.csv) をダウンロードして、クローンした直下に配置してください。

このデータは、一行目がコメント、二行目から問題と回答のペアがカンマ区切りで格納されています。

quizzes,solutions
004300209005009001070060043006002087190007400050083000600000105003508690042910300,864371259325849761971265843436192587198657432257483916689734125713528694542916378

処理の流れ

問題の一括読み込み
解析
答え合わせ

数独解析アルゴリズム

縦・横・マスで使用済みかどうかを、それぞれ9ビットのデータで管理します。そのうえで、ある位置にどの数字が設定できるかは、縦・横・マスの OR を取って反転させれば取得できます。もし、立っているのが1ビットのみ = 設定可能な値が1種類のみであれば、そこに値を設定します。
これを、設定可能な箇所がなくなるまで繰り返します。

例：Xの位置には何が設定可能か

     ﾏｽ --7-54---
     ↓ 001011000
+---+---+---+---+---+---+
| X - 4 | 3 - - | 2 - 9 | ← 横
| - - 5 | - - 9 | - - 1 |   9----432-
| - 7 - | - 6 - | - 4 3 |   100001110
+---+---+---+---+---+---+
| - - 6 | - - 2 | - 8 7 |
| 1 9 - | - - 7 | 4 - - |
| - 5 - | - 8 3 | - - - |
+---+---+---+---+---+---+
| 6 - - | - - - | 1 - 5 |
| - - 3 | 5 - 8 | 6 9 - |
| - 4 2 | 9 1 - | 3 - - |
+---+---+---+---+---+---+
  ↑ 縦
---6----1
000100001

-------------
   000100001 (縦)
OR 100001110 (横)
OR 001011000 (ﾏｽ)
-------------
   101111111

反転させると、010000000 となる.
つまり、一番左上には "8" を設定できる。