数独データ構造

数独用データ構造の自分用メモ

単純には、char cell[81]; とし、各セルの値を 0~9 で保持すればよい。
が、このようなデータ構造では確定しているセルを探す処理が非効率になる。

一案としては、数値を 0b000000001, 0b000000010, … 0b100000000 で 1~9 を表すことにし、
short cell[81]; でセルの数字を、short candidates[81]; で候補数字をビットパターンで表す方法がある。
こうしておけばビット演算で、確定しているセルを探す処理が効率的になる。

もう一つの方法としては、1つの数字が候補として生きているかどうかを1つのビットボードで表す方法がある。
1つのビットボードを ushort * 9 で表すとすれば、全部の候補は ushort * 9 * 9 なので 182バイトとなる。