NO IMAGE

ペントミノ Pentomino

ペントミノ=Pentomino = Penta + Omino とは、正方形(Omino)を 5個(Penta)繋げて作られる図形です。

5個の正方形の組合せでできる12種類のピースを箱に詰めるパズルを、ペントミノといいます。入れ方は2,339通り。コンピュータ計算ですべての解が分かっています。

ペントミノの入れ方を計算するプログラム

考え方は、箱の隅から順にピースを置いてゆき、置けなくなったら別の向きやピースを試してみる、ということになります。
具体的にどうすればいいのでしょう?
いろいろな方法がありますが、ペントミノパズルの場合、最小単位の正方形を一つのセルとみなし、6×10のセルからなる長方形の箱にピースを入れる方法が一般的と思います。
箱は、6×10のセルの周りに枠を加えたboard[][]という2次元配列で表します。
ピースは、構造体pentoを新規に定義します。
ピースを箱の左隅から置いてゆき、隙間なく全部のピースを置くことができれば成功です。

C言語プログラムで概要を説明します。

【0】ソースファイルの先頭でプリプロセッサ命令 #include でstdio.hとstring.hのヘッダファイルをインクルードしています。
【1】定数、外部変数を定義します。
【2】構造体pentoを定義します。
【3】関数initを定義します。
【4】関数displayを定義します。
【5】関数check_boardを定義します。
【6】関数serchを定義します。
【7】main関数です。

main

まず、mainです。
init→display→searchの3つのステップでペントミノの入れ方を計算しています。

init(初期化)

それでは、init(初期化)のところから確認します。

初期化の前に、定数と外部変数を定義しています。
◆定数の定義
    PIECE_NO  12(ピースの総数)
    UNUSE         0(ピース未使用)
    USE              1( ピース使用)
    INHIBIT      -1(箱の枠部分)
    EMPTY          0(ピースが置かれていない状態)
    MAX_X        12(枠を含めた箱の横方向の大きさ)
    MAX_Y          8(枠を含めた箱の縦方向の大きさ)
箱は10*6ですので、枠はその周囲1コマずつ。よってMAX_X, MAX_Yは2大きい数字になります。
◆外部変数の定義
    char board[MAX_X][MAX_Y]  
    int use_piece[PIECE_NO]
    int seq_no
    int size_x
    int size_y
実際にピースが入る大きさ10*6は、size_x =10, size_y =6としています。
seq_noは、入れ方につけた番号です。プログラムが終了すると sep_no = 2339になっているはずです。
init(初期化)は、init board(箱の初期化)とinit piece(ピースの初期化)の2つのステップからなります。
◆箱の状態の初期化
init boardは、ピースを入れる箱(枠含む)に番地を付けて(board[MAX_X][MAX_Y])、それぞれの状態を初期化しています。 枠の部分は INHIBIT = -1、枠の内側は(初期はピースが置いていないので)EMPTY = 0としています。
◆ピースの状態(使用・未使用)の初期化
init pieceは、ピースに番号を付けて(use_piece[PIECE_NO])、それぞれの状態(使用、未使用)をあらわします。最初ピースは未使用なので UNUSE = 0です。

ピースの定義

use_pieceでは、ピースに番号を付けて、使用か未使用かの情報を得ました。
今度は、pieceで、実際のピースの形を定義します。
さらにpieceは90°回転させたり裏返したりできますから、最大8通りのつぎのようになります。

display(結果の表示)

NO IMAGE
最新情報をチェックしよう!

パズルの最新記事8件

>最強のWordPressテーマ「THE THOR」

最強のWordPressテーマ「THE THOR」

本当にブロガーさんやアフィリエイターさんのためになる日本一のテーマにしたいと思っていますので、些細なことでも気が付いたのであればご報告いただけると幸いです。ご要望も、バグ報告も喜んで承っております!

日本国内のテーマでナンバー1を目指しております。どうか皆様のお力をお貸しください。よろしくおねがいいたします。

CTR IMG