SSブログ
English Version

1辺が1から10までの正方形のレイアウトパズル [Puzzle]

 旧Twitterのタイムラインで1辺が1から10までの10個の正方形を傾けずにできるだけ面積の小さい長方形内に並べるというパズルを見かけました。

 探索プログラムを作るより、手を使って解いた方が速そうだったのでエクセル上で考えてみました。



 上記のメッセージへのリプライで書いたように面積が 405 の長方形に収めることができます。また、この面積が最小であることを演繹的に証明することもできそうです。

 しかし、それ程凝らない作りであれば探索プログラムを作るのも割合簡単なので作ってみました。枝刈りのロジックを殆ど実装していない状態ではありますが、今時のパソコンであれば直ぐに全探索できるだろうという予測に反して意外にも全探索を完了するのに20分弱掛かりました。

★追記 2024/09/14 {
 高速化してみました。今、使える実行環境が貧弱なノートPC(Celeron(R) 1.10GHz、RAM 4GB)で変更前のプログラムの実行時間が以前測定した20分弱から35分になったので通常使用しているディスクトップPCより1.8倍遅いと言うことになります。高速化した結果、上記と同様の条件での探索時間は35秒でした。最小面積の解をカウントしない場合(serchでのリカーシブコールの条件式を等号無しの不等式のみにする)の実行時間は11秒程度でした。下記のソースもアップデートしました。
}
★追記 2024/09/16 {
 配置可能かのチェックロジックをx/y軸を分離し、y軸の判断処理をx軸ループ外に配置することで高速化しました。
 上記と同様のノートPCでの実行時間が15秒になりました(解をカウントせずserchのみの処理であれば7秒)。下記のソースもアップデートしました。

 探索プログラムを実行時の画面キャプチャを貼っておきます。スクリプトで実行前後に時刻を表示しています。
 全探索の結果として10個の正方形が収まる長方形の最小面積は 405 で、この盤面では同じ面積の回答が 1,073,184 通りあることも判りました。

探索プログラムの実行結果
※変更 2024/09/14

 プログラムを作ったのでこのパズルの一般的な名称があるのか「PuzzleSquareJP」のサイトで探してみましたが見当たりませんでした(掲載数が膨大にあるので最初の10ページくらいしかチェックしていません^^;)。

 ソースも貼っておきます。

正方形配置パズルの探索プログラム(C言語)
/*********************************************** square layout puzzle solver 1..10 square are layouted minimun Rectangle Ver 0.01 2024/09/12 by skyriver Ver 0.02 2024/09/14 08:50 faster Ver 0.03 2024/09/15 21:00 faster ***********************************************/ #include <stdio.h> #define MAXSQUARE 10 #define SUMAREA (MAXSQUARE*(MAXSQUARE+1)*(MAXSQUARE*2+1)/6) #define SOLCOUNT 1 // 0:not count solusions #define MAXBOARDX (MAXSQUARE * 4) #define MAXBOARDY (MAXSQUARE * 4) #if 01 #define FIRST_XPOS (MAXBOARDX / 3 + 2) #define FIRST_YPOS (MAXBOARDY / 3 + 2) #else #define FIRST_XPOS ( MAXSQUARE - 3) #define FIRST_YPOS (MAXBOARDY - MAXSQUARE - 6) #endif typedef struct { int x; int y; } Point_t; typedef struct { Point_t min; Point_t max; } Reqt_t; Reqt_t Square[ MAXSQUARE + 1 ]; char Board[ MAXBOARDY ][ MAXBOARDX ]; //int MinSize = 406; // answer area size int MinSize = (int)(SUMAREA*1.08); // answer area size int Size; // work int SolCnt; // answer counter void DelSquare( int size, int xpos, int ypos ) { for( int y = ypos; y < ypos + size; y++ ) { for( int x = xpos; x < xpos + size; x++ ) { Board[ y ][ x ] = 0; } } } void FillSquare( int size, int xpos, int ypos ) { for( int y = ypos; y < ypos + size; y++ ) { for( int x = xpos; x < xpos + size; x++ ) { Board[ y ][ x ] = size; } } } void disp( Reqt_t req ) { Reqt_t *spnt; printf( "\n\narea size = %3d, ( %2d x %2d ) " ,MinSize ,req.max.x - req.min.x + 1 ,req.max.y - req.min.y + 1 ); spnt = &Square[ 0 ]; for( int ssize = 1; ssize < MAXSQUARE; ssize++ ) { spnt++; FillSquare( ssize, spnt->min.x, spnt->min.y ); } for( int y = 0; y < MAXBOARDY; y++ ) { printf( "\n%2d : ", y ); for( int x = 0; x < MAXBOARDX; x++ ) { int c; c = Board[y][x]; if( c == 0 ) { c = '.'; } else if( c > 9 ) { c += 'A' - 10; } else { c += '0'; } putchar( c ); } } spnt = &Square[ 0 ]; for( int ssize = 1; ssize < MAXSQUARE; ssize++ ) { spnt++; DelSquare( ssize, spnt->min.x, spnt->min.y ); } } // size <- size of square // area <- area value of rectangle // req <- min & max point of rectangle void search( int sqsize, Reqt_t req ) { int *ckpnt; Reqt_t nreq; int chky[ MAXSQUARE ]; // outside flag for y for( int y = 0; y < MAXBOARDY - sqsize; y++ ) { int yen = y + sqsize - 1; Reqt_t *spnt = &Square[ MAXSQUARE ]; ckpnt = &chky[ 0 ]; for( int sq = MAXSQUARE - sqsize; sq; sq--, spnt--, ckpnt++ ) { *ckpnt = ( y <= spnt->max.y && y + sqsize > spnt->min.y ) ? 0 : 1; } Square[ sqsize ].min.y = y; Square[ sqsize ].max.y = yen; nreq.min.y = y < req.min.y ? y : req.min.y; nreq.max.y = yen > req.max.y ? yen : req.max.y; for( int x = 0; x < MAXBOARDX - sqsize; x++ ) { int checkx = 1; spnt = &Square[ MAXSQUARE ]; ckpnt = &chky[ 0 ]; for( int sq = MAXSQUARE - sqsize; sq; sq--, spnt--, ckpnt++ ) { if( *ckpnt == 0 && x <= spnt->max.x && x + sqsize > spnt->min.x ) { checkx = 0; break; } } if( checkx != 0 ) { int xen = x + sqsize - 1; Square[ sqsize ].min.x = x; Square[ sqsize ].max.x = xen; nreq.min.x = x < req.min.x ? x : req.min.x; nreq.max.x = xen > req.max.x ? xen : req.max.x; Size = (nreq.max.x - nreq.min.x + 1) * (nreq.max.y - nreq.min.y + 1); #if SOLCOUNT if( Size <= MinSize ) { if( sqsize != 1 ) { search( sqsize - 1, nreq ); } else { if( Size == MinSize ) { SolCnt++; } else { MinSize = Size; SolCnt = 1; disp( nreq ); } } } #else if( Size < MinSize ) { if( sqsize != 1 ) { search( sqsize - 1, nreq ); } else { MinSize = Size; disp( nreq ); } } #endif } } } } int main( int argc, char *argv[] ) { Reqt_t req; printf( "\nSquare layout puzzle solver Ver 0.03\n size:%d\n", MAXSQUARE ); req.min.x = FIRST_XPOS; req.min.y = FIRST_YPOS; req.max.x = FIRST_XPOS + MAXSQUARE - 1; req.max.y = FIRST_YPOS + MAXSQUARE - 1; Square[ MAXSQUARE ] = req; FillSquare( MAXSQUARE, FIRST_XPOS, FIRST_YPOS ); search( MAXSQUARE - 1, req ); printf( "\ncomplete searching.\nsame area size answer are %d.\n", SolCnt ); return( 0 ); }
★変更 Ver0.02 2024/09/14




★追記 2024/09/12
 上記の探索では1辺が10の正方形の位置は固定なので10の正方形が中心の位置にあるものしか探索できていません。
 試しに10の正方形が左下にある場合を探索してみた結果が下図になります。

10の正方形が左下の場合の探索結果

★変更 2024/09/13 下記の記述を修正しました

 上図の探索は10の正方形を左下に固定した場合であり、10の正方形が下側(縦並び)と左側(横並び)の場合のカウント結果です。10の正方形が上側(縦並び)と右側(横並び)の場合も考慮するとこの探索結果の2倍の解があることになります。

 従って10の正方形が中心にある場合と合わせると解の総数は下記の値になります。

   4,017,384 ( = 1,472,100 x 2 + 1,073,184 )通り



★追記 2024/09/18
 16までの正方形を最小の長方形に配置する探索を単純に行うととてつもなく時間が掛かります。何時間かかけて見つけた解(size:1520 = 40 x 38)が下図です。

16サイズまでの正方形の配置例(最小の長方形ではない)


 サイズ15までの最小解を見る(全てをチェックしたわけではないのですが)と最大の正方形は端に配置されているものが含まれることから、格納する長方形の角に最大の正方形を固定して探索することにします(この条件で最小解が得られるという保証はないのですが・・)

 それでも探索時間が膨大にかかるので下記の高速化手法を考えました。
  1. スキャンサイズの最小化
     最小四角形へ配置する探索で既知の最小面積は上図の 1520(40x38)のほぼ正方形なので盤面サイズを40x38,41x37~76x20とyをデクリメントしxをその時点での長方形の最小面積をyで割った値にして全探索します。結果的に格納する長方形をほぼ正方形から長~い長方形までを全探索することになります。

  2. 幅1ギャップでの枝刈り
     幅が1のギャップには最後に配置するサイズ1の正方形しか入れることができず殆どがデッドスペースになります。この幅1のギャップの総面積が(スキャン長方形のサイズ - 正方形の面積の総和)を超えた場合はその先の探索を打ち切って枝刈りするようにしました。

 上記を実装した探索プログラムを実行した結果が下図になります。図中の x マークは上記の幅1のギャップです。最小面積は 1512(54 x 28)で実行時間は1時間29分でした。

16サイズまでの正方形の配置の探索プログラム実行画面(Ver0.03)




★追記 2024/09/20 探索状態を観察し、次の高速化を行いました。

  • Ver0.03では未チェックだった正方形の対角線上の幅1ギャップのチェックを追加
  • 大きい正方形の配置から配置しているが、次の正方形の探索条件を「配置探索対象正方形のサイズが3以上で幅1ギャップ以外の空きスペースが4個以上またはサイズが2以下」の条件に変更
  • 解を発見した場合、同じサイズの長方形の探索を中断

 得られた最小解は今までと同様に size = 1512, ( 54 x 28 ) です。記念として探索結果を貼っておきます(クリックすると実行開始から終了までの画面表示が見えます)。

16サイズまでの正方形の配置の探索プログラム実行画面(Ver0.04)


 今回の最適化と実行環境をノートPCからディスクトップ(Win11要求仕様未達の古いPC)に変更したことで探索時間は 59分17秒 となり、下記の目標を達成できました。^^



★追記 2024/09/21 次の探索に進む条件を見直し高速化 {

 上記で次の探索へ進む条件での「空きスペースが4個以上」の部分が、サイズ3の正方形の探索(次の探索のサイズ2の正方形の面積が4なので))のみを考慮しているようでしっくりきませんでした。もっと汎用的に考えれば、幅1のギャップは最後に配置するサイズ1の正方形のみが使用可能なので全てのサイズの正方形の配置探索に適応できるように次探索へ進む条件を「幅1のギャップの総面積が(スキャン中の長方形の面積 - 全正方形の面積の総和 + 1)以下」に変更しました。
 その結果、下図(クリックで表示範囲拡大)に示すように探索時間は 45分51秒 になりました。

16サイズまでの正方形の配置の探索プログラム実行画面(Ver0.04改)

}




★追記 2024/09/21
 1辺が1~13の13個の正方形を最小面積の長方形へ配置する方法を探索してみました。プログラム作成当初は結果がでるまでかなり時間が掛かっていましたが、今では4秒程度で最小面積=836(38 x 22)の解が得られます。




★追記 2024/09/24
 旧Twiiterのタイムラインで情報提供頂き、Wolfram Demonstrations Project の「Tightly Packed Squares」のページで本パズルで1辺が3~32までの探索結果を表示するデモが見れます(ソースも開示されている模様)。1辺が33以上は未だに未解決のようなので興味のある人は挑戦してみては如何でしょうか?


nice!(0)  コメント(0) 
共通テーマ:趣味・カルチャー