Depleting and retaining certain blocks(2)

先日のエントリにて掲載した問題の回答を検証するに当たり、コードを書いてみました。問題は以下のようなものでした。

さて、この問題には「壊してもよいブロック」と「必ず残るブロック(確定のブロック)」が一つずつあるようです。それは一体どれでしょうか。ただし、緑色で表されたブロックは「必ず残すブロック(すでに確定されたブロック)」であるとします。
Depleting and retaining certain blocks(1) - agwの日記

今回の検証では、実際の立体ピクロスのように三次元空間を扱うものではなく、上述の問題のような一列のブロックのみを解くものとしました。この問題は可能性のある組み合わせの中から条件に合致した解を選択する制約充足問題に置き換えることが出来そうです。

では制約条件を考えてみます。一列のブロックには残すブロックの状態によって丸や四角を伴った数字が与えられます。任天堂の定義によれば、

【普通数字】
普通数字は、残すブロックが連続していることをあらわしています。
立体ピクロス

【丸数字】
丸数字は、残すブロックが2つに分かれていることをあらわしています。
立体ピクロス

【四角数字】
四角数字は、残すブロックが3つ以上に分かれていることをあらわしています。
立体ピクロス

となっています。上述の問題で与えられている制約条件は「四角の6」ですので、「残すブロックは3つ以上に分かれており、その総数は6」となるように「壊してもよいブロック」と「必ず残すブロック」を決定していきます。そのためには、以下のような条件を考えれば良さそうです。

残すブロックの総数が与えられた数値と等しい
残すブロックの分割数が、普通数字、丸数字および四角数字の条件と合致する

さて、今回は問題をビットとして考えてみます。「必ず残すブロック(確定したブロック)」を1、すなわちビットが立った状態としてみましょう。また、ビットが0である場合は、未確定のブロックを表すものとします。上述の問題は、以下のような二進の値として表現することが出来ます。

00111010

ここで、制約条件も同じくビットを用いた表現に置き換えてみます。

立っているビットの総数が与えられた数値と等しい
連続して立っているビット群の総数が、普通数字、丸数字および四角数字の条件と合致する

一つ目の制約条件を検証するのには、Population Countというアルゴリズムを用いることが出来ます。

Population Countは大変有名なアルゴリズムで、インターネット上に資料が多いためここでは解説を割愛します。ビットを数える・探すアルゴリズムにて大変丁寧な解説がなされています。お勧めのページです。今回用いるコードは、Hacker's Delightに掲載されているものです。

int bitcount(int n) {
  n =    (n & 0x55555555) + (n >>  1 & 0x55555555);
  n =    (n & 0x33333333) + (n >>  2 & 0x33333333);
  n =    (n & 0x0f0f0f0f) + (n >>  4 & 0x0f0f0f0f);
  n =    (n & 0x00ff00ff) + (n >>  8 & 0x00ff00ff);
  return (n & 0x0000ffff) + (n >> 16 & 0x0000ffff);
}

さて、二つ目の制約条件を考えてみましょう。例えば問題の状態が00111010である場合、連続して立っているビット群は2つです。他の例も考えてみましょう。