Best Small Program

最高のスモールプログラム

受賞者:Oscar Toledo G.

引用元: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")は、ナイトの動ける方向を表している。