A 回答 (4件)
- 最新から表示
- 回答順に表示
No.4
- 回答日時:
「計算では厳しいですね」という表現は何を表すのか, ってのが問題かなぁ. 「あっち」世界だと
計算 = 「なにか」する
なので, 「プログラムで見付ける」というのは「計算」の範疇に入る. で, 「プログラムで見付かる」以上は「計算でできる」となっちゃうわけ.
さらにいうとハミルトン閉路問題を一般化した巡回セールスマン問題はいろいろとやられていて, 今だと数万点 (質問にあわせると数万の「ます目」) でも解けるケースはある. つまり「1個見付ければいい」というだけであればたぶんそんなに難しくない.
No.3
- 回答日時:
> やはり、計算では厳しいですね、、
難しそうですね。
ちら、と調べてみたんですが、お題は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.2
- 回答日時:
> こんなにもたくさん出されているのですが、計算で出されたのですか?もし計算で出すことが可能であるならば、ぜひ教えていただきたいです。
いや、Pythonと言う言語でプログラムを組んだ、と言うより改造して使って調べました。
元ネタは次のページにあります。
欲張り法 (greedy strategy):
http://www.nct9.ne.jp/m_hiroi/light/pyalgo22.html
要するに(5×6より)30手目まで判定して、次の一手を仮定した場合、次のマスが初手(つまり1手目ですよね)を含むかどうか調べて、含まなかったら捨てる、と言う力技で解決しています。
・・・ちなみに、計算には結構時間かかりますよ。フツーの「騎士の巡歴」問題でも、この問題設定だと(1, 1)から始めても4000通り以上解は存在する模様なので。
No.1
- 回答日時:
ちょっと設定が曖昧です。
最初にナイトはどこにいるのでしょうか?一応、左上隅((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
設定が曖昧で申し訳ございません…
始点はどこでも構わないです。
こんなにもたくさん出されているのですが、計算で出されたのですか?もし計算で出すことが可能であるならば、ぜひ教えていただきたいです。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
継承元と継承先での変数
-
VBA 九九 Do While
-
ExcelのマクロVBA動作を軽くす...
-
matlabで計算終了
-
VBAの再計算が反映されない件に...
-
タクシー料金の問題です
-
VBでReplace
-
60進数の四則計算
-
0xf0=256?
-
EXCELなどで「返す」という表現
-
切り上げたい
-
傾いた四角形内の範囲の条件式
-
エクセルで特定のセルのみを任...
-
三菱シーケンサー works2 の日...
-
アドオン利率を実質年率に変換
-
BASICでモンテカルロ法
-
VB6.0でのバイナリデータの扱い...
-
fortran dlog2
-
排他的論理和 BCC(水平パリテ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
排他的論理和 BCC(水平パリテ...
-
VBAの再計算が反映されない件に...
-
バッチファイルでウインドウを...
-
変化させるセルが変化しない
-
EXCELなどで「返す」という表現
-
傾いた四角形内の範囲の条件式
-
エクセルで特定のセルのみを任...
-
CとFORTRANの計算速度はどちら...
-
Visual C++でdebugとreleaseで...
-
モジュラス103の計算とは何でし...
-
なぜオーバーフローになるので...
-
VB6で正確なミリ秒を計測したい...
-
VBでReplace
-
引き放し法による除算アルゴリ...
-
matlabで計算終了
-
CRC8を教えてください
-
VBAで関数をつくる
-
Excel VBAの残業時間の合計計算...
-
等高線を計算したい
おすすめ情報