引用元：https://www.ioccc.org/2006/toledo1/toledo1.c
審査員・作者による説明：https://www.ioccc.org/2006/toledo1/hint.text
動作
ナイトツアーのソルバ。
$ gcc -o toledo1 toledo1.c
$ ./toledo1 11
01 16 27 22 03 18 47 52
26 23 02 17 46 51 04 19
15 28 25 50 21 48 53 56
24 35 30 45 62 55 20 05
29 14 61 34 49 44 57 54
36 31 38 41 60 63 06 09
13 40 33 64 11 08 43 58
32 37 12 39 42 59 10 07
スタート位置は指定できる。
右上から始める例。
$ ./toledo1 18
16 13 32 37 18 03 34 01
31 58 17 14 33 36 19 04
12 15 60 49 38 41 02 35
59 30 57 40 53 48 05 20
26 11 52 61 50 39 42 47
29 64 27 56 45 54 21 06
10 25 62 51 08 23 46 43
63 28 09 24 55 44 07 22
左下を飛び出た位置から始める例。
$ ./toledo1 90
56 49 16 45 64 43 14 11
17 46 55 60 15 12 35 42
50 57 48 63 44 65 10 13
47 18 61 54 59 34 41 36
28 51 58 33 62 53 24 09
19 04 29 52 25 32 37 40
02 27 06 21 30 39 08 23
05 20 03 26 07 22 31 38
01
飛び出た位置から始めるとSEGVすることもある。
解説
Warnsdorff’s ruleを使ってナイトツアーを解く。
これは、現在地からジャンプできるマスのうち、脱出経路が一番少ないマスを選択するというヒューリスティクス（経験則）。
一般のグラフで全ノードに1回ずつ到達するパスを探す問題（ハミルトニアン閉路問題）はNP完全だけれども、チェス盤面でのナイトツアーにおいてはこのヒューリスティクスだけでどの初期位置からでも解けることが知られているらしい。
よって、バックトラックのようなことをせず、greedyに一瞬で解けてしまう。
コードはチェッカーボード。
唯一の文字列リテラル（"\1\7(d\177yX\34"）は、ナイトの動ける方向を表している。