チェス 論理クイズ

5×6のチェス盤で、ナイトが全てのマスを一回ずつ訪れて、スタートしたマスに戻る道を見つける。
この道を教えてください。

No.1 回答者： cametan_42 回答日時： 2020/10/07 23:54

ちょっと設定が曖昧です。

最初にナイトはどこにいるのでしょうか?

一応、左上隅((x, y) = (1, 1)とします)を始点としても16通りくらい解はありますね。

1
1 22 27 12 7 16
28 11 30 15 26 13
21 2 23 8 17 6
10 29 4 19 14 25
3 20 9 24 5 18

2
1 22 25 12 7 16
24 11 30 15 26 13
21 2 23 8 17 6
10 29 4 19 14 27
3 20 9 28 5 18

3
1 22 27 10 7 16
28 11 30 15 26 9
21 2 23 8 17 6
12 29 4 19 14 25
3 20 13 24 5 18

4
1 22 25 10 7 16
24 11 30 15 26 9
21 2 23 8 17 6
12 29 4 19 14 27
3 20 13 28 5 18

5
1 14 25 10 29 16
24 5 30 15 20 9
13 2 11 26 17 28
6 23 4 19 8 21
3 12 7 22 27 18

6
1 14 21 10 29 16
22 5 30 15 20 9
13 2 11 26 17 28
6 23 4 19 8 25
3 12 7 24 27 18

7
1 14 25 6 29 16
24 5 30 15 20 7
13 2 11 26 17 28
10 23 4 19 8 21
3 12 9 22 27 18

8
1 14 21 6 29 16
22 5 30 15 20 7
13 2 11 26 17 28
10 23 4 19 8 25
3 12 9 24 27 18

9
1 10 7 22 25 16
8 21 2 17 6 23
11 30 9 24 15 26
20 3 28 13 18 5
29 12 19 4 27 14

10
1 10 7 20 25 16
8 21 2 17 6 19
11 30 9 24 15 26
22 3 28 13 18 5
29 12 23 4 27 14

11
1 10 5 22 25 16
4 21 2 17 6 23
11 30 9 24 15 26
20 3 28 13 18 7
29 12 19 8 27 14

12
1 10 5 20 25 16
4 21 2 17 6 19
11 30 9 24 15 26
22 3 28 13 18 7
29 12 23 8 27 14

13
1 18 11 26 3 16
10 27 2 17 12 25
19 30 21 6 15 4
22 9 28 13 24 7
29 20 23 8 5 14

14
1 18 11 22 3 16
10 27 2 17 12 23
19 30 21 6 15 4
26 9 28 13 24 7
29 20 25 8 5 14

15
1 18 7 26 3 16
8 27 2 17 12 25
19 30 21 6 15 4
22 9 28 13 24 11
29 20 23 10 5 14

16
1 18 7 22 3 16
8 27 2 17 12 23
19 30 21 6 15 4
26 9 28 13 24 11
29 20 25 10 5 14

この回答へのお礼

設定が曖昧で申し訳ございません…
始点はどこでも構わないです。
こんなにもたくさん出されているのですが、計算で出されたのですか？もし計算で出すことが可能であるならば、ぜひ教えていただきたいです。

お礼日時：2020/10/08 00:04

No.2 回答者： cametan_42 回答日時： 2020/10/08 00:17

> こんなにもたくさん出されているのですが、計算で出されたのですか？もし計算で出すことが可能であるならば、ぜひ教えていただきたいです。

いや、Pythonと言う言語でプログラムを組んだ、と言うより改造して使って調べました。
元ネタは次のページにあります。

欲張り法 (greedy strategy):
http://www.nct9.ne.jp/m_hiroi/light/pyalgo22.html

要するに(5×6より)30手目まで判定して、次の一手を仮定した場合、次のマスが初手(つまり1手目ですよね)を含むかどうか調べて、含まなかったら捨てる、と言う力技で解決しています。
・・・ちなみに、計算には結構時間かかりますよ。フツーの「騎士の巡歴」問題でも、この問題設定だと(1, 1)から始めても4000通り以上解は存在する模様なので。

この回答へのお礼

そうなのですか！やはり、計算では厳しいですね、、
道が分かって良かったです。ご回答ありがとうございました！

お礼日時：2020/10/08 00:50

No.3 回答者： cametan_42 回答日時： 2020/10/08 01:57

> やはり、計算では厳しいですね、、

難しそうですね。
ちら、と調べてみたんですが、お題はA closed knight's tour(閉じた騎士の巡歴)と言い、数学的にはグラフ理論のハミルトン閉路問題の1つ、との事です。

ハミルトン閉路問題:
https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F …

計算でやるとしたら、もうバリバリの数学者、しかもグラフ理論の専門家向けの問題の模様です。

NP完全な問題との事で、平たく言うと、「虱潰しに解を探すしかやりようがない」らしい(笑)。スマートな数学的な解法、ってのは取り敢えず無いみたいですね(色々と定理は発見されてるらしいですが・・・・・・)。

NP完全問題:
https://www.math.nagoya-u.ac.jp/~garrigue/lectur …

曰く

「NP完全問題を，しらみつぶしによる方法より本質的に効率よく解くことのできるアルゴリズムは存在しないと考えている。｣

No.4 回答者： Tacosan 回答日時： 2020/10/08 23:57

「計算では厳しいですね」という表現は何を表すのか, ってのが問題かなぁ. 「あっち」世界だと

計算 = 「なにか」する
なので, 「プログラムで見付ける」というのは「計算」の範疇に入る. で, 「プログラムで見付かる」以上は「計算でできる」となっちゃうわけ.

さらにいうとハミルトン閉路問題を一般化した巡回セールスマン問題はいろいろとやられていて, 今だと数万点 (質問にあわせると数万の「ます目」) でも解けるケースはある. つまり「1個見付ければいい」というだけであればたぶんそんなに難しくない.