数独ソルバー

9×9の数独を二国同盟を使って解こうと思います。

データ構造

候補はそのマスの縦横四角をチェックして入れられる数字です。
例えば1,3,5が入るなら、kouho[1],[3],[5]の値を1、kouho[0]を3、それ以外は0です。

nikoku.cpp

//数字を入れるマス
class masu {
public:
    int number = 0;         //マスに入っている値
    int col, row;           //マスが入っている小区画の位置
    int kouho[9 + 1];   //マスに入りうる候補
};

//全てのマスをまとめたもの
class table {
public:
    masu square[9][9];
};

プログラム

二国同盟とは

二国同盟は、入れるマスが2択に絞られている数字が2つあり、そのマスが全く同じ時、対象のマスはその2つの数字のどちらかが必ず入るという手法です。

[二国同盟-数独の解き方]http://www.sudokugame.org/solv/pairs.php

関数

上記の候補を使って対象となるマスをまず探します。

nikoku.cpp

void rowUnion(table &table){
    //1行目から9行目まで
    for (int i = 0; i < 9; ++i){
        //各数字がどのマスを候補に持つか
        int nitaku[saizu + 1][2] = { 0 };
        for (int k = 1; k < 9 + 1; ++k){
            vector<int> temp;
            for (int j = 0; j < 9; ++j){
                if (table.square[i][j].kouho[k] == 1){
                    temp.push_back(j);
                }
            }
            //候補となるマスが2つしかなければ
            if (temp.size() == 2){
                nitaku[k][0] = temp[0];
                nitaku[k][1] = temp[1];
            }
        }

これで2択に絞られている数字がわかりました。

二国同盟のチェック

nitaku[k][0]とnitaku[k][1]が数字kの入るマスなので、これが一致するかを確認します。

nikoku.cpp

//各数字について
for (int k = 1; k < saizu + 1; ++k){
    //その数字が入るマスが2択であれば
    if (nitaku[k][0] != 0){
        for (int m = k + 1; m < saizu + 1; ++m){
            //同じマスを2択として持つ数字を探す
            if ((nitaku[k][0] == nitaku[m][0]) 
                && (nitaku[k][1] == nitaku[m][1])){
                //2択であるマスをa,bとする
                int a = nitaku[k][0];
                int b = nitaku[k][1];
                //2つのマスの候補を一旦すべて消す
                for (int n = 0; n < saizu + 1; ++n){
                    table.square[i][a].kouho[n] = 0;
                    table.square[i][b].kouho[n] = 0;
                }
                //2つの候補だけの状態にする
                table.square[i][a].kouho[k] = 1;
                table.square[i][a].kouho[m] = 1;
                table.square[i][a].kouho[0] = 2;

                table.square[i][b].kouho[k] = 1;
                table.square[i][b].kouho[m] = 1;
                table.square[i][b].kouho[0] = 2;
            }
        }
    }
}

難問ナンプレを手で解くときは効果的な二国同盟ですが、このコードを使って解いたところかえって遅くなりました。候補が1つしかないマスを確定させるのと、候補が少ないマスから探索するのは速くなったので、二国同盟の出現頻度が少ないのが原因かなと。