畳み敷き詰め問題の制約条件

Question

###質問内容
上図に示すようなスペースが確保されていて，各マスは11の正方形です．
ここに12の長方形の畳を4枚敷き詰める方法を全て見つけようとしています．
例えば，(a, b), (d, e), (g, h), (c, f)といった感じで置くなどです．
このとき，各変数の値に関する制約条件をすべて列挙する形で，この制約充足問題を定式化したいのですが，どのようにするのがよいのでしょうか．

個人的には，最初は各変数の値を0で埋めて置き，畳を置いたマスの変数は1にするのようなものを考えたのですが，解を網羅的に求めるプログラムを具体的に考え付くことができていない現状です．

CやJava，prologでやり方をご指導いただければ幸いです．

###制約条件の定式化の例

文字に異なる整数を入れて筆算を完成させる問題を例にすると，制約条件はうえのようになり，これはprologで次のように書くことで解くことが出来ました．

:- use_module(library(clpfd)).
send([[S,E,N,D], [M,O,R,E], [M,O,N,E,Y]]) :-
Digits = [S,E,N,D,M,O,R,Y],
Carries = [C1,C2,C3,C4],
Digits ins 0..9,
Carries ins 0..1,

M #= C4,
O + 10 * C4 #= M + S + C3,
N + 10 * C3 #= O + E + C2,
E + 10 * C2 #= R + N + C1,
Y + 10 * C1 #= E + D,
M #>= 1, S #>= 1,
all_different(Digits),

label(Digits).

###追記
何を教えていただきたいのか不明瞭の陽でしたので次の二つに目まとめさせていただきます．
・例の図における未知数と領域，制約の部分は畳敷き詰め問題だとどうなるのか
・畳の敷き詰め方を網羅するプログラムの方針(C, Java, prolog)

Comments

[y_waiwai]

で、しつもんはなんでしょうか

[jimbe]

> 各変数の値に関する制約条件をすべて列挙する形で，この制約充足問題を定式化したい

ガクモン的な解をお求めであれば、そのテのサイトをお探しになった方が良いかと思います。

Answer 1

C だとこんな風に書けます。

#include <stdio.h>

char a[16] = {
	 0,  0,  0, -1,  // 0, 1, 2, (3)
	 0,  0,  0, -1,  // 4, 5, 6, (7)
	 0,  0, -1, -1,  // 8, 9, (10)
	-1, -1, -1, -1
};

void proc(int i, int k)
{
	if (i == 10) {
		for (i = 0; i < 10; ) {
			if (a[i] > 0) printf(" %d", a[i]);
			if (++i % 4 == 0) putchar('\n');
		}
		puts("\n");
	}
	else if (a[i]) proc(i+1, k);
	else {
		if (a[i+1] == 0)
			a[i] = a[i+1] = k, proc(i+2, k+1), a[i] = a[i+1] = 0;
		if (a[i+4] == 0)
			a[i] = a[i+4] = k, proc(i+1, k+1), a[i] = a[i+4] = 0;
	}
}
	
int main(void)
{
	proc(0, 1);
}

実行結果

 1 1 2
 3 3 2
 4 4

 1 1 2
 3 4 2
 3 4

 1 2 2
 1 3 3
 4 4

 1 2 3
 1 2 3
 4 4

追記
結果の表示を変えたい場合は、

    if (i == 10) {
		static char c[] ="abc.def.gh";
        for (k = 1, i = 0; i < 10; i++)
			if (a[i] == k) printf(" (%c,%c)", c[i], c[i+(a[i+1]==k++ ? 1 : 4)]);
        putchar('\n');
    }

実行結果

 (a,b) (c,f) (d,e) (g,h)
 (a,b) (c,f) (d,g) (e,h)
 (a,d) (b,c) (e,f) (g,h)
 (a,d) (b,e) (c,f) (g,h)

Answer 2

何を回答として求めているのかよくわかりませんが，

a～hの8個のマス全てを１回だけ通る一筆書きな経路（例：fcbadehg）を列挙すればよいのでしょうから，
それを「制約条件がどうの」いう話のフォーマット(?)に落とし込めばよいのではないでしょうか．
何をどう書けばそういう話を満たすのかよくわかりませんが

• [x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7] という8個の変数に要素 { a,b,c,d,e,f,g,h }　を入れてみろ．
• 条件として x_i != x_j, whre i!=j とせよ．（同じ要素を２回使うな）
• x_i と x_(i+1) との間の市街区距離は1とせよ

みたいな？

---

[追記]
実際に「C言語とかで列挙する処理を実装する」となった場合は，上記のような「一筆書きで…」みたいには考えずに，
何と言うか「ふつーに」探索木的な話で粛々と探索していく処理を書くので良いような気がします．

aのマスに着目すれば畳の置き方は (a,b) か (a,d) の２通りしかないので，ここで探索の枝が二股に分かれる
→　その各枝の先で今度は別のマスに着目して…

みたいな．
残りの隣接マスが1個になったマスに関してはその時点で畳の置き方が確定するので，探索木はそれほど深くならないように思います．

• (a,b) と置くパターンならその時点で (c,f) が定まるので，その先は２通りのみ．
• (a,d) と置くパターンでも同様に (g,h) が定まるので，２通りのみ．

Comments

[fana]

※念のため補足：
一筆書きな経路が得られたならば，畳の配置はマスを順番に２つずつペアにしていくだけ．

> 例：fcbadehg

で言えば，(f,c) (b,a) (d,e) (h,g)

[grape_ll]

質問の意図が見えにくくなってしまい申し訳ございません．
質問内容の追記の方に簡潔にまとめさせていただきました．

求めたいニュアンスとしては，おっしゃられているようなものだと私も認識しております．
敷き詰め方を網羅する仮定で用いた条件，だということになると思います．

一筆書きで二つをペアにすれば敷き詰め方を表現できるという発想は持ち合わせていなかったので大変ありがたいです．

[ikadzuchi]

今回の8マスに限ってはすべての敷き詰めが一筆書きできそうですが、常に可能なわけではないですし、そもそも一筆書きと敷き詰めが多対一に対応するのは解法として筋が悪いと思います。
┌─┬┬┐例えば4×4マスで左図の敷き詰めは一筆書きができません。
├─┤││
├┬┼┴┤
││├─┤
└┴┴─┘

[fana]

私がそもそもの質問の意図を読み違えていたのかもしれませんが…

「ある特定の問題（今回の8マス並び限定の話）」とはせずに（＝一般化した状態で？）制約条件がどうのっていう話って書けるんでしょうか？
部屋の形状が未知な状態でどうやって書くのか？　というのが想像つかないです．

とりあえず今回の8マスにおいて「一筆書き」という話を捨てるならば

> x_i と x_(i+1) との間の市街区距離は1とせよ

この条件において「ここで i は偶数」という話にして，ここに
x_i < x_(i+1)
みたいな大小関係の条件でも設ければよいのかな？とか思います（が，それで合っているでしょうか？）

[fana]

> 多対一

というのは，「逆順でも同じパターンになるじゃん」っていう話でしょうか？
だとしたらそれを防止する制約条件は……どう書けばよいのだろう？
x_0 < x_7
とか…？

[fana]

動くコードだけを示した回答にベストアンサーが移ったところを見ると，

> 制約条件をすべて列挙する形で，この制約充足問題を定式化…

とかいう側の話に関しては，どうでもよかった模様^^

[ikadzuchi]

> 「ある特定の問題（今回の8マス並び限定の話）」とはせずに（＝一般化した状態で？）制約条件がどうのっていう話って書けるんでしょうか？
そこは私もあまり分からないところです(分かったら回答を書くところです)が、数学的に何かしら存在しそうな気はするんですよね…。今回の質問がそこまで考えるべきものかどうかは分かりませんが。

> 「逆順でも同じパターンになるじゃん」っていう話でしょうか？
それもありますし、他にも始点と終点がつながるパターンでは始点の位置で畳枚数分増えますね。あとは純粋に別パターンの一筆書きができることもあります。
┌─┬─┐
├─┼─┤
├─┼─┤
├─┼─┤例えばこれは
└─┴─┘
┌──┐
└┐┌┘
┌┘└┐こう通るパターンが始点の位置で8種類(および逆順で2倍)と
└──┘
───┐
┌──┘
└──┐こう通るパターンがあります。
───┘

[fana]

あーなるほど，ループはともかく，違う経路形状でも行けちゃうやつが……

「列挙するコードを書け」って言われたら「手続き」を考えればよいだけなのですが，
「制約条件を書け」言われると難しいなぁ．

> 今回の質問がそこまで考えるべきものかどうかは分かりませんが

・例の図における未知数と領域，制約の部分は畳敷き詰め問題だとどうなるのか
・畳の敷き詰め方を網羅するプログラムの方針

のどちらも解決してない状態でフィニッシュしているので，そもそも何も考えなくてよかった模様です．
（結局 teratail の質問ってのは，動くらしいコードが貼られればそれでおｋ）

[fana]

話を一般化しようとか考えると，まずマップ形状をどう表すのか？というところから…

２次元のグリッド状の世界においてN個の点 P_1 ～ P_N が存在していて
点 P_i の座標は ( X_i, Y_i ) として与えられるとき……

とか何とか言う書き出しになるのか？