最小公倍図形

初版：2011.12.01

最小公倍図形の問題は、２００５年のＧＰＣＣの課題の１つとして提起されましたが、あまり進展がなく、２０１１年に再度提起されました。
ゲームの説明は、[3] a) のＧＰＣＣのＨＰを参照されたい。同ＨＰによると、現在知られている最小公倍図形は、河原哲郎氏の発見されたＴペントミノ１２０個の解のみです。これ以下の解を探索するのが目標です。

deepgreenは、最小公倍図形の問題は制約条件が大変厳しいので、部分解合成法（NQueens問題のＳｏｌｖｅｒＱＪＨで使った方法）に向いている問題と思い挑戦してみました。

直 接、"最小" を狙うはの難しそうなので、探索範囲をＮ x Ｎの正方形の範囲に限定した探索プログラムを作成しました。ようやく、プログラムが完成し、Ｎ＝２１，２３，２５と範囲を広げて探索したところ、Ｎ＝２５ のところで、Ｔペントミノ６８個（３４０単位）の解がみつかりました。
２５ｘ２５の範囲では、この３４０単位の解が６個存在するだけで、より大きな解は存在しないこともわかりました。

Ｔペントミノ６８個が "最小" というためには、制約を外した探索が必要となりますので、別のプログラムを作る必要があります。（今のプログラムを改造すればできるかもしれません。時間ができたらやってみようと思っていますが、しばらくは手がでません）


-----　探索結果　-------------------------------------------------

探索方法 : 部分解合成法
         （１３ｘ１３の部品を４つ組み合わせて全体解を生成する方法 ）
         
探索範囲 : ２５ｘ２５の正方形に納まる範囲

探索結果 : ３４０単位（Ｔ＝６８，Ｏ＝８５）の解 ６個を検出
             解の一覧：ＨＪoin-13-ＳｙｍＣｈｅｃｋ−log.txt

探索時間 : 約３時間３０分

ＰＣ環境
   ＣＰＵ          : Intel Core i7-2600  3.4GHz
   メモリ          : ４ＧＢ
   使用ディスク容量：約３１ＧＢ（約４６６Ｍ個の部品を格納）
   ＯＳ            : Window7 Home Premium（３２ビット版）
  
プログラムサイズ   : 約１９５０行


【３４０単位の解の一例】

==== T-piece map (68) ====
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  02 03 .  .  .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  01 01 01 04 02 02 02 03 03 03 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  05 01 09 04 04 04 02 03 06 07 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  08 05 05 05 01 09 04 0a .  06 06 06 07 07 07 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  08 08 08 05 09 09 09 0a .  .  .  06 07 0b 0c .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  11 08 .  .  .  .  .  0a 0a 0a 0e 0f 0b 0b 0b 0c 0c 0c 10 .  .  .  .  .
 .  .  .  .  .  .  .  .  11 0d 0d 0d .  .  .  12 0e 0e 0e 0f 0f 0f 0b 0c 10 10 10 .  .  .  .  .
 .  .  .  .  .  .  16 11 11 11 0d 17 .  .  18 12 12 12 0e 0f .  .  .  .  .  .  10 15 .  .  .  .
 .  .  .  .  .  .  16 13 13 13 0d 17 .  .  18 12 14 14 14 19 .  .  .  .  1a 15 15 15 .  .  .  .
 .  .  .  .  .  16 16 16 13 .  17 17 17 18 18 18 1d 14 21 19 19 19 .  .  1a 1a 1a 15 .  .  .  .
 .  .  .  .  .  1b 1b 1b 13 .  1c 1c 1c 20 1d 1d 1d 14 21 19 1e 1e 1e 22 1a 1f 1f 1f .  .  .  .
 .  .  .  .  .  .  1b 26 .  .  23 1c 27 20 20 20 1d 21 21 21 25 1e 29 22 22 22 1f 2a .  .  .  .
 .  .  .  .  .  .  1b 26 23 23 23 1c 27 20 24 24 24 28 25 25 25 1e 29 22 .  .  1f 2a .  .  .  .
 .  .  .  .  .  .  26 26 26 2b 23 27 27 27 2c 24 31 28 28 28 25 29 29 29 .  32 2a 2a 2a .  .  .
 .  .  .  .  .  .  30 2b 2b 2b .  .  2c 2c 2c 24 31 28 2d 2d 2d 2e 2e 2e .  32 2f 2f 2f .  .  .
 .  .  .  .  .  .  30 30 30 2b .  .  .  .  2c 31 31 31 33 2d .  .  2e 38 32 32 32 2f .  .  .  .
 .  .  .  .  .  .  30 35 .  .  .  .  .  .  36 37 33 33 33 2d .  .  2e 38 34 34 34 2f .  .  .  .
 .  .  .  .  .  .  .  35 35 35 39 3a 36 36 36 37 37 37 33 .  .  .  38 38 38 34 .  .  .  .  .  .
 .  .  .  .  .  .  .  35 39 39 39 3a 3a 3a 36 37 3b 3b 3b .  .  .  .  .  3d 34 .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  39 3a 3e 3f .  .  .  3b 3c 3c 3c 40 3d 3d 3d .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  3e 3e 3e 3f 3f 3f .  3b 41 3c 44 40 40 40 3d .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  3e 3f 42 43 41 41 41 3c 44 40 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  42 42 42 43 43 43 41 44 44 44 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  42 43 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 
==== O-piece map (85) ====
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  01 01 .  .  .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  02 02 03 03 04 04 01 01 05 05 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  02 02 03 03 04 04 06 06 05 05 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  07 07 08 08 09 09 0a 0a .  06 06 0b 0b 0c 0c .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  07 07 08 08 09 09 0a 0a .  .  .  0b 0b 0c 0c .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  0d 0d .  .  .  .  .  0e 0e 0f 0f 10 10 11 11 12 12 13 13 .  .  .  .  .
 .  .  .  .  .  .  .  .  0d 0d 14 14 .  .  .  0e 0e 0f 0f 10 10 11 11 12 12 13 13 .  .  .  .  .
 .  .  .  .  .  .  15 15 16 16 14 14 .  .  17 17 18 18 19 19 .  .  .  .  .  .  1a 1a .  .  .  .
 .  .  .  .  .  .  15 15 16 16 1b 1b .  .  17 17 18 18 19 19 .  .  .  .  1c 1c 1a 1a .  .  .  .
 .  .  .  .  .  1d 1d 1e 1e .  1b 1b 1f 1f 20 20 21 21 22 22 23 23 .  .  1c 1c 24 24 .  .  .  .
 .  .  .  .  .  1d 1d 1e 1e .  25 25 1f 1f 20 20 21 21 22 22 23 23 26 26 27 27 24 24 .  .  .  .
 .  .  .  .  .  .  28 28 .  .  25 25 29 29 2a 2a 2b 2b 2c 2c 2d 2d 26 26 27 27 2e 2e .  .  .  .
 .  .  .  .  .  .  28 28 2f 2f 30 30 29 29 2a 2a 2b 2b 2c 2c 2d 2d 31 31 .  .  2e 2e .  .  .  .
 .  .  .  .  .  .  32 32 2f 2f 30 30 33 33 34 34 35 35 36 36 37 37 31 31 .  38 38 39 39 .  .  .
 .  .  .  .  .  .  32 32 3a 3a .  .  33 33 34 34 35 35 36 36 37 37 3b 3b .  38 38 39 39 .  .  .
 .  .  .  .  .  .  3c 3c 3a 3a .  .  .  .  3d 3d 3e 3e 3f 3f .  .  3b 3b 40 40 41 41 .  .  .  .
 .  .  .  .  .  .  3c 3c .  .  .  .  .  .  3d 3d 3e 3e 3f 3f .  .  42 42 40 40 41 41 .  .  .  .
 .  .  .  .  .  .  .  43 43 44 44 45 45 46 46 47 47 48 48 .  .  .  42 42 49 49 .  .  .  .  .  .
 .  .  .  .  .  .  .  43 43 44 44 45 45 46 46 47 47 48 48 .  .  .  .  .  49 49 .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  4a 4a 4b 4b .  .  .  4c 4c 4d 4d 4e 4e 4f 4f .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  4a 4a 4b 4b 50 50 .  4c 4c 4d 4d 4e 4e 4f 4f .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  51 51 50 50 52 52 53 53 54 54 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  51 51 55 55 52 52 53 53 54 54 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  55 55 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 
---------------- (end) -----------------------------------------------------------------------------



[1] 処理論理の説明

　　作成予定（時期未定）

[2] ソースコード

     処理論理の説明とあわせて公開予定
　　（ ソースのみでよいから見たいという方は直接deepgreen宛てにメールをください ）

[3] 参考情報
　　a)  ＧＰＣＣ, http://hp.vector.co.jp/authors/VA003988/gpcc/gpcc.htm

Home