ペントミノ（pentomino）の改良版

// pentomino
//
//  2012.03.18 ───── coded by 心如

#include <iostream>
#include <string>
#include <ctime>
using namespace std;

const Bw = 16;  // Board-Width
const Bh = 12;  // Board-Height
const Sw = 6;   // Space-Width
const Sh = 10;  // Space-Height
const Sp = Bw + 1;  // Start-Point
const Mp = Sh * Bw + Sw;
const Fv = 13;  // frame_value

//チップパターンのデータ
struct chip{
    int id, s1, s2, s3, s4;
};
struct chip chip_data[] = {
    { 1,  1,  2,  3,  4},
    { 1, 16, 32, 48, 64}, // 2
   
    { 2,  1,  2,  3, 16},
    { 2,  1,  2,  3, 19},
    { 2,  1, 16, 32, 48},
    { 2,  1, 17, 33, 49},
    { 2, 16, 32, 48, 47},
    { 2, 16, 32, 48, 49},
    { 2, 16, 15, 14, 13},
    { 2, 16, 17, 18, 19}, // 10
   
    { 3,  1,  2,  3, 17},
    { 3,  1,  2,  3, 18},
    { 3, 16, 15, 32, 48},
    { 3, 16, 17, 32, 48},
    { 3, 16, 32, 31, 48},
    { 3, 16, 32, 33, 48},
    { 3, 16, 17, 15, 14},
    { 3, 16, 15, 17, 18}, // 18
   
    { 4,  1,  2, 17, 33},
    { 4, 16, 15, 14, 32},
    { 4, 16, 17, 18, 32},
    { 4, 16, 32, 31, 33}, // 22
   
    { 5,  1,  2, 16, 18},
    { 5,  1, 16, 32, 33},
    { 5,  1, 17, 33, 32},
    { 5, 16, 17, 18,  2}, // 26
   
    { 6, 16, 15, 17, 32}, // 27
   
    { 7,  1, 17, 18, 34},
    { 7,  1, 16, 15, 31},
    { 7, 16, 15, 31, 30},
    { 7, 16, 17, 33, 34}, // 31
   
    { 8,  1, 17, 18, 19},
    { 8,  1, 16, 15, 14},
    { 8, 16, 15, 31, 47},
    { 8, 16, 17, 33, 49},
    { 8, 16, 32, 31, 47},
    { 8, 16, 32, 33, 49},
    { 8,  1,  2, 16, 15},
    { 8,  1,  2, 18, 19}, // 39
   
    { 9,  1, 16, 15, 32},
    { 9,  1, 17, 18, 33},
    { 9, 16, 15, 17, 33},
    { 9, 16, 17, 15, 31},
    { 9, 16, 15, 14, 31},
    { 9, 16, 17, 18, 33},
    { 9, 16, 17, 32, 31},
    { 9, 16, 15, 32, 33}, // 47
   
    {10, 16, 32, 31, 30},
    {10,  1,  2, 16, 32},
    {10,  1,  2, 18, 34},
    {10, 16, 32, 33, 34}, // 51
   
    {11,  1, 16, 32, 31},
    {11,  1, 17, 33, 34},
    {11, 16, 15, 14, 30},
    {11, 16, 17, 18, 34}, // 55
   
    {12, 16, 15, 32, 31},
    {12, 16, 17, 32, 33},
    {12,  1, 16, 17, 32},
    {12,  1, 16, 17, 33},
    {12,  1, 16, 17, 15},
    {12,  1, 16, 17, 18},
    {12,  1,  2, 16, 17},
    {12,  1,  2, 17, 18} // 63
};

class Puzzle{
    int cnt;
    int cpm;
    int board[Bw * Bh];
    int chip_use[Fv];
public:
    Puzzle();
    void disp();
    void play(int);
};

Puzzle::Puzzle(){
    int i, j;
   
    cnt = 0;
    cpm = sizeof(chip_data) / sizeof(chip);
    // ボードの初期化
    for(i = 0; i < Bw * Bh; i++){
        board[i] = Fv;
    }
    for(i =0; i < Sh; i++){
        for(j = 0; j < Sw; j++){
            board[Sp + i * Bw + j] = 0;
        }
    }
    for(i = 0; i < Fv; i++){
        chip_use[i] = 0;
    }
}

// パズルの表示
void Puzzle::disp(){
    string ppp[] = {
        "・", "１", "２", "３", "４", "５", "６", "７", "８", "９",
        "Ａ", "Ｂ", "Ｃ", "┃"
    };
    printf(" %d 回目 (%5.3f 秒)\n",
        cnt++, (float )clock() / CLOCKS_PER_SEC);
    cout << "┏━━━━━━┓" << endl;
    for(int y = 1; y < 11; y++){
        for(int x = 0; x < 8; x++){
            cout << ppp[board[y * Bw + x]];
        }
        cout << endl;
    }
    cout << "┗━━━━━━┛" << endl;
}

// パズルの探索
void Puzzle::play(int sp){
    int idn, p1, p2, p3, p4;
    // 探索点の確認
    if(board[sp + 1] != 0 && board[sp + Bw] != 0) return;
//  if(board[sp + 1] == 0 || board[sp + Bw] == 0){
        for(int i = 0; i < cpm; i++){   // チップ数だけ確認
            if(chip_use[chip_data[i].id] != 0){
                continue;   // チップが使用中なら次へ
            }
            if(board[p1 = sp + chip_data[i].s1] != 0 ||
               board[p2 = sp + chip_data[i].s2] != 0 ||
               board[p3 = sp + chip_data[i].s3] != 0 ||
               board[p4 = sp + chip_data[i].s4] != 0){
                continue;   // チップが置けないなら次へ
            }
            // チップの配置
            idn = chip_data[i].id;
            board[sp] = idn;
            board[p1] = idn;
            board[p2] = idn;
            board[p3] = idn;
            board[p4] = idn;
            chip_use[idn] = 1;
            // 次の空きを探す
            int np = sp;
            while(np++ < Mp){
                if(board[np] == 0){
                    break;
                }
            }
            if(np <= Mp){
                play(np); // 次のチップを探索
            }
            else{
                disp(); // 解を表示
            }
            // チップの除去
            board[sp] = 0;
            board[p1] = 0;
            board[p2] = 0;
            board[p3] = 0;
            board[p4] = 0;
            chip_use[idn] = 0;
        }
//  }
}

// メイン・ルーチン
int main(){
    Puzzle pzl;
    pzl.disp();
    pzl.play(Sp);
}
─────

　過去記事で紹介したプログラムに比べて、実行時間の短縮が出来ました。

　もっと、短縮できる方法がないか、引き続き研究したいと思います。

（by　心如）

タグ：改良 パズル