12/03/25 12:25:26.16
>>15
>無駄がないようにしたい
下記のように■同士を最短距離でつなげたいという意味ですか？
□□□□□□□□□ ・右の図の○を■にしてすべての■をつなげたい
□■○■○■○■□ ・毎回違う結果にしたい
□○□○□○□○□ ・輪にならないようにしたい
□■○■○■○■□
□○□○□○□○□
□■○■○■○■□
□○□○□○□○□
□■○■○■○■□
□□□□□□□□□
これで全ての■がつながるなら24個の○のうち最低15個が■ですね。
15個の■と9個の□で全ての■をつなげた時は輪はありません。
以下の手順で全ての組み合わせが求まります。
１ 24個の○のうち15個を■、9個を□にした順列を順番に走査する。
２ 今調べている順列に上下左右が□の■があればボツ。
順列を再帰呼び出しで作り、
1～9個目の□の位置を決めるごとにその上下左右の■を調べ、
■の上下左右が全て□だったらその枝の走査を打ちきると効率的です。