質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.35%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

2回答

2544閲覧

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

grape_ll

総合スコア83

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

0クリップ

投稿2021/12/02 02:55

編集2021/12/02 06:33

イメージ説明

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

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

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

###制約条件の定式化の例
イメージ説明
文字に異なる整数を入れて筆算を完成させる問題を例にすると,制約条件はうえのようになり,これはprologで次のように書くことで解くことが出来ました.

prolog

1:- use_module(library(clpfd)). 2send([[S,E,N,D], [M,O,R,E], [M,O,N,E,Y]]) :- 3Digits = [S,E,N,D,M,O,R,Y], 4Carries = [C1,C2,C3,C4], 5Digits ins 0..9, 6Carries ins 0..1, 7 8M #= C4, 9O + 10 * C4 #= M + S + C3, 10N + 10 * C3 #= O + E + C2, 11E + 10 * C2 #= R + N + C1, 12Y + 10 * C1 #= E + D, 13M #>= 1, S #>= 1, 14all_different(Digits), 15 16label(Digits).

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

y_waiwai

2021/12/02 04:03

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

2021/12/02 04:52

> 各変数の値に関する制約条件をすべて列挙する形で,この制約充足問題を定式化したい ガクモン的な解をお求めであれば、そのテのサイトをお探しになった方が良いかと思います。
guest

回答2

0

ベストアンサー

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

C

1#include <stdio.h> 2 3char a[16] = { 4 0, 0, 0, -1, // 0, 1, 2, (3) 5 0, 0, 0, -1, // 4, 5, 6, (7) 6 0, 0, -1, -1, // 8, 9, (10) 7 -1, -1, -1, -1 8}; 9 10void proc(int i, int k) 11{ 12 if (i == 10) { 13 for (i = 0; i < 10; ) { 14 if (a[i] > 0) printf(" %d", a[i]); 15 if (++i % 4 == 0) putchar('\n'); 16 } 17 puts("\n"); 18 } 19 else if (a[i]) proc(i+1, k); 20 else { 21 if (a[i+1] == 0) 22 a[i] = a[i+1] = k, proc(i+2, k+1), a[i] = a[i+1] = 0; 23 if (a[i+4] == 0) 24 a[i] = a[i+4] = k, proc(i+1, k+1), a[i] = a[i+4] = 0; 25 } 26} 27 28int main(void) 29{ 30 proc(0, 1); 31}

実行結果

text

1 1 1 2 2 3 3 2 3 4 4 4 5 1 1 2 6 3 4 2 7 3 4 8 9 1 2 2 10 1 3 3 11 4 4 12 13 1 2 3 14 1 2 3 15 4 4 16

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

C

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

実行結果

text

1 (a,b) (c,f) (d,e) (g,h) 2 (a,b) (c,f) (d,g) (e,h) 3 (a,d) (b,c) (e,f) (g,h) 4 (a,d) (b,e) (c,f) (g,h)

投稿2021/12/02 09:02

編集2021/12/02 09:40
kazuma-s

総合スコア8224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

a~hの8個のマス全てを1回だけ通る一筆書きな経路(例: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 とせよ.(同じ要素を2回使うな)
  • x_i と x_(i+1) との間の市街区距離は1とせよ

みたいな?


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

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

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

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

投稿2021/12/02 04:16

編集2021/12/02 07:58
fana

総合スコア11996

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fana

2021/12/02 04:19

※念のため補足: 一筆書きな経路が得られたならば,畳の配置はマスを順番に2つずつペアにしていくだけ. > 例:fcbadehg で言えば,(f,c) (b,a) (d,e) (h,g)
grape_ll

2021/12/02 06:43 編集

質問の意図が見えにくくなってしまい申し訳ございません. 質問内容の追記の方に簡潔にまとめさせていただきました. 求めたいニュアンスとしては,おっしゃられているようなものだと私も認識しております. 敷き詰め方を網羅する仮定で用いた条件,だということになると思います. 一筆書きで二つをペアにすれば敷き詰め方を表現できるという発想は持ち合わせていなかったので大変ありがたいです.
ikadzuchi

2021/12/02 15:49

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

2021/12/03 01:19

私がそもそもの質問の意図を読み違えていたのかもしれませんが… 「ある特定の問題(今回の8マス並び限定の話)」とはせずに(=一般化した状態で?)制約条件がどうのっていう話って書けるんでしょうか? 部屋の形状が未知な状態でどうやって書くのか? というのが想像つかないです. とりあえず今回の8マスにおいて「一筆書き」という話を捨てるならば > x_i と x_(i+1) との間の市街区距離は1とせよ この条件において「ここで i は偶数」という話にして,ここに x_i < x_(i+1) みたいな大小関係の条件でも設ければよいのかな?とか思います(が,それで合っているでしょうか?)
fana

2021/12/03 01:23

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

2021/12/03 01:57

動くコードだけを示した回答にベストアンサーが移ったところを見ると, > 制約条件をすべて列挙する形で,この制約充足問題を定式化… とかいう側の話に関しては,どうでもよかった模様^^
ikadzuchi

2021/12/03 04:57

> 「ある特定の問題(今回の8マス並び限定の話)」とはせずに(=一般化した状態で?)制約条件がどうのっていう話って書けるんでしょうか? そこは私もあまり分からないところです(分かったら回答を書くところです)が、数学的に何かしら存在しそうな気はするんですよね…。今回の質問がそこまで考えるべきものかどうかは分かりませんが。 > 「逆順でも同じパターンになるじゃん」っていう話でしょうか? それもありますし、他にも始点と終点がつながるパターンでは始点の位置で畳枚数分増えますね。あとは純粋に別パターンの一筆書きができることもあります。 ┌─┬─┐ ├─┼─┤ ├─┼─┤ ├─┼─┤例えばこれは └─┴─┘ ┌──┐ └┐┌┘ ┌┘└┐こう通るパターンが始点の位置で8種類(および逆順で2倍)と └──┘ ───┐ ┌──┘ └──┐こう通るパターンがあります。 ───┘
fana

2021/12/03 05:23

あーなるほど,ループはともかく,違う経路形状でも行けちゃうやつが…… 「列挙するコードを書け」って言われたら「手続き」を考えればよいだけなのですが, 「制約条件を書け」言われると難しいなぁ. > 今回の質問がそこまで考えるべきものかどうかは分かりませんが ・例の図における未知数と領域,制約の部分は畳敷き詰め問題だとどうなるのか ・畳の敷き詰め方を網羅するプログラムの方針 のどちらも解決してない状態でフィニッシュしているので,そもそも何も考えなくてよかった模様です. (結局 teratail の質問ってのは,動くらしいコードが貼られればそれでおk)
fana

2021/12/03 05:29 編集

話を一般化しようとか考えると,まずマップ形状をどう表すのか?というところから… 2次元のグリッド状の世界においてN個の点 P_1 ~ P_N が存在していて 点 P_i の座標は ( X_i, Y_i ) として与えられるとき…… とか何とか言う書き出しになるのか?
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.35%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問