ナンプレの正規化 ステップ・バイ・ステップ その４

はじめに

Step3では、「一番上に来る行のヒントパターン」に着目し、それを四進法の数字だと思って枝刈りをした。これをもう少し考える。

今回のソースコードはここ。

方針

上三行のヒント配置の確定までには

1. 転置+ボックス行の入れ替え
2. ボックス列の入れ替え
3. ボックス行内の行の入れ替え
4. 列の入れ替え

という手順を踏む。この際、「1. 転置+ボックス行の入れ替え」において、最初に「辞書順で最も小さくなる一番上の行のヒントパターン」を調べてしまい、それ以外の配置を弾く、という枝刈りを行った。

具体的には

1. ヘッドボックスインデックス(ソート)を調べて、それを最小値hb_minとして記憶
2. ヘッドボックスインデックス(ソート無し)を調べ、hb_minと一致していなければ弾く
3. ヘッドラインインデックス(ソート)を調べhb_minと一致していなければ弾く

としている。すぐに、最後の列の入れ替えの時に「ヘッドラインインデックス(ソート無し)を調べ、hb_minと一致していなければ弾く」という枝刈りをしたくなるが、これはヘッドラインインデックスの計算コストの方が枝刈りのメリットを上回り、トータル遅くなる。

なので、同じようなことを低コストでやる必要がある。

さて、一番上にくる行のヒントパターンがどうあるべきか、もう一度考えよう。

例えば最初に調べた「辞書順で最も小さくなる一番上の行のヒント数パターン」が(0,0,2)であった時、列の入れ替えに入る前にヒント数が(0,0,2)になっていることが保証される。次に調べるべきか、これらのヒントが、それぞれのボックスで「右寄せ」になっているかどうかである。

例えばヒントが二個ある場合、

011
101
110

の三パターンがありえる。しかし、このうち辞書順最小になりえるのは、いかなる数字が入っていようと

011

だけである。

この「右寄せ」は、各ボックス列について独立に判定できる。以上から、

1. 一番上の行のボックスごとのヒント数の組を調べる
2. 並び替えのパターンと、ヒントのパターンを調べ、「右寄せ」になっていないパターンは弾く

とすれば良い。

並び替えのパターンとヒントのパターンについてはちょっと面倒くさい。

例えば、ヒントの配置パターンが101だったとしよう。こいつに列の入れ替えを6パターン適用することを考える。

• 順序を全く変えない012という入れ替えを適用した場合、ヒント配置パターンは101になるため、これは弾かなければならない。
• しかし、最初と真ん中を入れ替える102という入れ替えを適用すると、ヒント配置パターンは011と右寄せになるため、これは再帰する必要がある。
• 同様に120というパターンを適用しても右寄せになる。

このように、「右寄せ」になるビットパターンだけ通すことで枝刈りをする。

実装

入力としては、ビットパターンが3bitなので8パターン、ボックス内の列の入れ替えが6パターンあるので、全部で48パターン。それぞれにtrue/falseを入れてやれば良い。そんなテーブルを作るスクリプトがこちら。

mktbl.rb

class Integer
  def to_b
    sprintf("%03b",self)
  end
end

flag = [true,true,false, true,false,false,false,true]

ai = []
8.times do |i|
  aj = []
  [0,1,2].permutation do |a|
    t = []
    t.push (i&4) >> 2
    t.push (i&2) >> 1
    t.push (i&1)
    j = 0
    j = j + t[0] * (1 << (2-a.index(0)))
    j = j + t[1] * (1 << (2-a.index(1)))
    j = j + t[2] * (1 << (2-a.index(2)))
    puts "#{t} #{i.to_b} #{j.to_b} #{a} #{flag[j]}"
    aj.push flag[j]
  end
  ai.push "{" + aj.join(",") + "}"
end
puts "{" + ai.join(",") + "}"

実行結果はこんな感じ。

$ ruby mktbl.rb
[0, 0, 0] 000 000 [0, 1, 2] true
[0, 0, 0] 000 000 [0, 2, 1] true
[0, 0, 0] 000 000 [1, 0, 2] true
[0, 0, 0] 000 000 [1, 2, 0] true
[0, 0, 0] 000 000 [2, 0, 1] true
[0, 0, 0] 000 000 [2, 1, 0] true
[0, 0, 1] 001 001 [0, 1, 2] true
[0, 0, 1] 001 010 [0, 2, 1] false
[0, 0, 1] 001 001 [1, 0, 2] true
[0, 0, 1] 001 010 [1, 2, 0] false
[0, 0, 1] 001 100 [2, 0, 1] false
[0, 0, 1] 001 100 [2, 1, 0] false
[0, 1, 0] 010 010 [0, 1, 2] false
[0, 1, 0] 010 001 [0, 2, 1] true
[0, 1, 0] 010 100 [1, 0, 2] false
[0, 1, 0] 010 100 [1, 2, 0] false
[0, 1, 0] 010 001 [2, 0, 1] true
[0, 1, 0] 010 010 [2, 1, 0] false
[0, 1, 1] 011 011 [0, 1, 2] true
[0, 1, 1] 011 011 [0, 2, 1] true
[0, 1, 1] 011 101 [1, 0, 2] false
[0, 1, 1] 011 110 [1, 2, 0] false
[0, 1, 1] 011 101 [2, 0, 1] false
[0, 1, 1] 011 110 [2, 1, 0] false
[1, 0, 0] 100 100 [0, 1, 2] false
[1, 0, 0] 100 100 [0, 2, 1] false
[1, 0, 0] 100 010 [1, 0, 2] false
[1, 0, 0] 100 001 [1, 2, 0] true
[1, 0, 0] 100 010 [2, 0, 1] false
[1, 0, 0] 100 001 [2, 1, 0] true
[1, 0, 1] 101 101 [0, 1, 2] false
[1, 0, 1] 101 110 [0, 2, 1] false
[1, 0, 1] 101 011 [1, 0, 2] true
[1, 0, 1] 101 011 [1, 2, 0] true
[1, 0, 1] 101 110 [2, 0, 1] false
[1, 0, 1] 101 101 [2, 1, 0] false
[1, 1, 0] 110 110 [0, 1, 2] false
[1, 1, 0] 110 101 [0, 2, 1] false
[1, 1, 0] 110 110 [1, 0, 2] false
[1, 1, 0] 110 101 [1, 2, 0] false
[1, 1, 0] 110 011 [2, 0, 1] true
[1, 1, 0] 110 011 [2, 1, 0] true
[1, 1, 1] 111 111 [0, 1, 2] true
[1, 1, 1] 111 111 [0, 2, 1] true
[1, 1, 1] 111 111 [1, 0, 2] true
[1, 1, 1] 111 111 [1, 2, 0] true
[1, 1, 1] 111 111 [2, 0, 1] true
[1, 1, 1] 111 111 [2, 1, 0] true
{{true,true,true,true,true,true},{true,false,true,false,false,false},{false,true,false,false,true,false},{true,true,false,false,false,false},{false,false,false,true,false,true},{false,false,true,true,false,false},{false,false,false,false,true,true},{true,true,true,true,true,true}}

デバッグ用の出力もあるので説明は不要と思う。もっとエレガントに書けそうな気がするが、使い捨てのスクリプトなので気にしないことにする。

これをC++コードに取り込む。

bool hlb_table[8][6] = {{true, true, true, true, true, true}, {true, false, true, false, false, false}, {false, true, false, false, true, false}, {true, true, false, false, false, false}, {false, false, false, true, false, true}, {false, false, true, true, false, false}, {false, false, false, false, true, true}, {true, true, true, true, true, true}};

そして、最初に3つのヒントパターンをもらってから、入れ替えの組み合わせとヒントパターンの組み合わせが「右寄せ」かどうか調べて弾く。

一番上の行のヒントパターンを３つ返す関数が(書くまでも無いが)こちら。Sudokuクラスのメンバ関数になっている。

  int headline_bits(int &h1, int &h2, int &h3) {
    h1 = 0;
    h2 = 0;
    h3 = 0;
    for (int i = 0; i < 3; i++) {
      if (data[i] != 0) h1 += (1 << (2 - i));
      if (data[i + 3] != 0) h2 += (1 << (2 - i));
      if (data[i + 6] != 0) h3 += (1 << (2 - i));
    }
  }

列の入れ替えの枝刈りがこちら。もともとautoでまわしていたループが、入れ替えのインデックスが必要になったので通常のループカウンタ付きのfor文になってる。この時、「一番右」のボックスから調べると枝刈りの効率が良い(ほとんどの場合、一番右にしかヒントがいないから)。

  void perm_columns(Sudoku &g) {
    int h1, h2, h3;
    g.headline_bits(h1, h2, h3);
    for (int k = 0; k < 6; k++) {
      if (!hlb_table[h3][k])continue;
      int *ak = perm3[k];
      for (int j = 0; j < 6; j++) {
        if (!hlb_table[h2][j])continue;
        int *aj = perm3[j];
        for (int i = 0; i < 6; i++) {
          if (!hlb_table[h1][i])continue;
          int *ai = perm3[i];
          Sudoku g2 = g.perm_columns(ai, aj, ak).renumbering();
          if (min.head() < g2.head()) continue;
          perm_restrbox(g2);
        }
      }
    }
  }

結果

枝刈り前。

$ time ./a.out sample.txt > test.txt
./a.out sample.txt > test.txt  7.37s user 0.03s system 98% cpu 7.493 total

枝刈り後。

$ time ./a.out sample.txt > sample.minlex
./a.out sample.txt > sample.minlex  3.29s user 0.02s system 99% cpu 3.334 total

$ diff sample.minlex ../step3/sample.minlex 

二倍弱ですか。まぁこんなものかな。

まとめ

とりあえずナイーブに組んだ時よりは40倍ちょっと高速化したけど、まだまだ高速化の余地がありそう。もちろんSIMD化とかそういう高速化もあるけれど、アルゴリズムレベルで落とせそうな枝がもっとある気がする・・・

その5へ続く。