ぶどうの房パズルの解説

さて、先日は「ぶどうの房パズル」を取り上げた。

http://saito.hatenablog.jp/entry/20091001/1254387155

これのパズルに挑戦している人がいるようだ。

http://d.hatena.ne.jp/rg350/20091115/1258293910

全てのパターンについて条件を満すかどうかをチェックするという方針でプログラムが書かれている。 プログラム的には簡単だが、かなり膨大な計算を要するのでとても時間がかかってしまうことになる。

改善案

改善方法をひとつ解説しよう。

いきなり最上段の並びを全部埋める必要は無い。 まず左側を2個埋めてみよう。 とりあえず {1, 2} をあてはめると、その下には 1 が現れてしまい、 NG と判定できる。

1		2		○		○
	1		○		○
		○		○
			○

これから言えることは、 {1, 2} で始まる全ての並びは NG であるということだ。 {1, 2, 3, 4} も {1, 2, 6, 8} も {1, 2, 7, 5} も NG である。 一気に 56 種類の並びが NG として除去されてしまった。

同様に、 3 個目まで埋めてから NG と判定できる場合もある。 例えば {1, 3, 7} という並びだとこうなる。

1		3		7		○
	2		4		○
		2		○
			○

{1, 3, 7} で始まる 7 種類の並びは一気に NG 判定できるわけだ。

改善案の実装

以上を踏まえてプログラムを書くとこうなる。

#include <stdio.h>
#include <stdlib.h>

#define L 5  /* 段数を指定する。 */
#define N ((L+1)*L/2)

int answ[N+1], line[N+1], used[N+1];

void printansw(void) {
  for(int i=1, s=1; s<=N; s+=i, i++) printf("%3d ",answ[s]);
  printf("\n");
}

void trie(int depth) {
  if(depth>N) printansw();
  else if(line[depth]!=line[depth-1])
    for(int i=1; i<=N; i++) {
      if(!used[i]) {
        answ[depth]=i; used[i]=1; trie(depth+1); used[i]=0;
      }
    }
  else {
    int i=abs(answ[depth-1]-answ[depth-line[depth]]);
    if(!used[i]) {
      answ[depth]=i; used[i]=1; trie(depth+1); used[i]=0;
    }
}}

void init(void) {
  line[0]=0;
  for(int i=1; i<=N; i++) used[i]=0;
  for(int p=1, i=1; i<=L; i++) for(int j=0; j<i; j++, p++) line[p]=i;
}

int main(void) {
  init();
  trie(1);
  return 0;
}

更なる改善案

さて、この文章を書いている途中で今更ながら気付いたことがある。 上の例では「{1, 2} で『始まる』全ての並びは NG」と述べたが、実際には「{1, 2} を『含む』全ての並びは NG」である。 {1, 2} という並びはどこにも現れることが出来ない。

○		1		2		○
	○		1		○
		○		○
			○

○		○		○		○
	○		1		2
		○		1
			○

つまり、一旦 NG となったパターンを記憶しておけば、探索範囲を大幅に小さくすることが出来るはずなのだ。

実現するには幅優先探索に書き直す必要があったりして面倒なので、誰か実装してみてくれたらいいなぁと投げっぱなしにしてみる。

Document ID: 48ea28e0eda698ed41d55fe35b2457a1