hexomino.cpp

// HEXOMINO PUZZLE (PP #600)
//
// 2012.03.15 coded by 心如

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

const Bw = 16;  // Board-Width
const Bh = 21;  // Board-Height
const Sw = 11;  // Space-Width
const Sh = 19;  // Space-Height
const Sp = 17;  // Start-Point(Bw+1)
const Mp = 315; // Maximum-search-point
const Dp = 172; // Deko-Point
const Fv = 36;  // frame-value

// チップパターンのデータ
struct cip {
    int id, s1, s2, s3, s4, s5;
};
struct cip chip_data[] = {
    { 1,  1,  2,  3,  4,  5},
    { 1, 16, 32, 48, 64, 80},   // 2
   
    { 2,  1,  2,  3,  4, 20},
    { 2,  1,  2,  3,  4, 16},
    { 2,  1, 16, 32, 48, 64},
    { 2,  1, 17, 33, 49, 65},
    { 2, 16, 32, 48, 64, 63},
    { 2, 16, 32, 48, 64, 65},
    { 2, 16, 15, 14, 13, 12},
    { 2, 16, 17, 18, 19, 20},   // 10
   
    { 3,  1,  2,  3,  4, 19},
    { 3,  1,  2,  3,  4, 17},
    { 3, 16, 15, 32, 48, 64},
    { 3, 16, 17, 32, 48, 64},
    { 3, 16, 32, 48, 47, 64},
    { 3, 16, 32, 48, 49, 64},
    { 3, 16, 17, 15, 14, 13},
    { 3, 16, 15, 17, 18, 19},   // 18
   
    { 4,  1,  2,  3,  4, 18},
    { 4, 16, 15, 14, 17, 18},
    { 4, 16, 32, 31, 48, 64},
    { 4, 16, 32, 33, 48, 64},   // 22
   
    { 5,  1,  2, 17, 33, 49},
    { 5, 16, 15, 14, 13, 32},
    { 5, 16, 17, 18, 19, 32},
    { 5, 16, 32, 48, 47, 49},   // 26
   
    { 6,  1, 16, 15, 32, 48},
    { 6,  1, 17, 18, 33, 49},
    { 6, 16, 15, 14, 17, 33},
    { 6, 16, 17, 18, 15, 31},
    { 6, 16, 15, 14, 13, 31},
    { 6, 16, 17, 18, 19, 33},
    { 6, 16, 32, 33, 48, 47},
    { 6, 16, 32, 31, 48, 49},   // 34
   
    { 7,  1, 16, 32, 31, 48},
    { 7,  1, 17, 33, 34, 49},
    { 7, 16, 17, 15, 14, 30},
    { 7, 16, 15, 17, 18, 34},
    { 7, 16, 15, 14, 13, 30},
    { 7, 16, 17, 18, 19, 34},
    { 7, 16, 15, 32, 48, 49},
    { 7, 16, 17, 32, 48, 47},   // 42
   
    { 8,  1, 16, 32, 48, 47},
    { 8,  1, 17, 33, 49, 50},
    { 8, 16, 15, 14, 13, 29},
    { 8, 16, 17, 18, 19, 35},   // 46
   
    { 9, 16, 15, 32, 33, 48},
    { 9, 16, 17, 32, 31, 48},
    { 9, 16, 17, 15, 14, 31},
    { 9, 16, 15, 17, 18, 33},   // 50
   
    {10, 16, 15, 17, 32, 48},
    {10, 16, 32, 31, 33, 48},
    {10, 16, 15, 17, 18, 32},
    {10, 16, 17, 15, 14, 32},   // 54
   
    {11,  1,  2,  3, 16, 18},
    {11,  1,  2,  3, 17, 19},
    {11,  1, 16, 32, 33, 48},
    {11,  1, 17, 33, 32, 49},
    {11, 16, 15, 17, 18,  2},
    {11, 16, 17, 18,  2, 19},
    {11, 16, 15, 32, 48, 47},
    {11, 16, 17, 32, 48, 49},   // 62
   
    {12,  1,  2,  3, 19, 20},
    {12,  1,  2,  3, 16, 15},
    {12,  1, 16, 15, 14, 13},
    {12,  1, 17, 18, 19, 20},
    {12, 16, 15, 31, 47, 63},
    {12, 16, 17, 33, 49, 65},
    {12, 16, 32, 48, 47, 63},
    {12, 16, 32, 48, 49, 65},   // 70
   
    {13,  1,  2,  3, 18, 34},
    {13,  1,  2,  3, 17, 33},
    {13, 16, 15, 14, 32, 48},
    {13, 16, 17, 18, 32, 48},
    {13, 16, 32, 31, 30, 48},
    {13, 16, 32, 33, 34, 48},
    {13, 16, 32, 31, 33, 34},
    {13, 16, 32, 33, 31, 30},   // 78
   
    {14,  1,  2, 18, 19, 20},
    {14,  1,  2, 16, 15, 14},
    {14, 16, 32, 31, 47, 63},
    {14, 16, 32, 33, 49, 65},   // 82
   
    {15,  1, 17, 18, 19, 35},
    {15,  1, 16, 15, 14, 30},
    {15,  1, 16, 32, 31, 47},
    {15,  1, 17, 33, 34, 50},
    {15, 16, 15, 14, 30, 29},
    {15, 16, 17, 18, 34, 35},
    {15, 16, 15, 31, 47, 46},
    {15, 16, 17, 33, 49, 50},   // 90
   
    {16,  1, 17, 18, 34, 35},
    {16,  1, 16, 15, 31, 30},
    {16, 16, 15, 31, 30, 46},
    {16, 16, 17, 33, 34, 50},   // 94
   
    {17,  1, 17, 18, 33, 32},
    {17,  1, 16, 15, 32, 33},
    {17, 16, 17, 18,  2, 33},
    {17, 16, 15, 17, 31, 33},   // 98
   
    {18,  1, 17, 18, 19, 34},
    {18,  1, 16, 15, 14, 31},
    {18, 16, 17, 32, 31, 47},
    {18, 16, 15, 32, 33, 49},
    {18, 16, 17, 15, 31, 30},
    {18, 16, 15, 17, 33, 34},
    {18, 16, 15, 31, 30, 47},
    {18, 16, 17, 33, 34, 49},   // 106
   
    {19,  1, 17, 18, 19, 33},
    {19,  1, 16, 15, 14, 32},
    {19, 16, 15, 14, 31, 47},
    {19, 16, 17, 18, 33, 49},
    {19, 16, 15, 14, 32, 33},
    {19, 16, 17, 18, 32, 31},
    {19, 16, 32, 31, 33, 47},
    {19, 16, 32, 31, 33, 49},   // 114
   
    {20,  1,  2, 17, 33, 32},
    {20,  1,  2, 17, 33, 34},
    {20,  1, 16, 32, 31, 33},
    {20,  1, 17, 33, 32, 34},
    {20, 16, 17, 18,  2, 32},
    {20, 16, 17, 18,  2, 34},
    {20, 16, 17, 18, 32, 34},
    {20, 16, 15, 14, 32, 30},   // 122
   
    {21,  1,  2, 16, 18, 19},
    {21,  1,  2, 16, 15, 18},
    {21,  1, 17, 33, 32, 48},
    {21,  1, 16, 32, 33, 49},
    {21,  1, 17, 18, 19,  3},
    {21, 16, 17, 18,  2,  3},
    {21, 16, 15, 31, 47, 48},
    {21, 16, 17, 33, 49, 48},   // 130
   
    {22,  1,  2, 18, 19, 34},
    {22,  1,  2, 16, 15, 32},
    {22, 16, 17, 15, 31, 47},
    {22, 16, 15, 17, 33, 49},
    {22, 16, 15, 32, 33, 34},
    {22, 16, 17, 32, 31, 30},
    {22, 16, 32, 31, 30, 47},
    {22, 16, 32, 33, 34, 49},   // 138
   
    {23,  1,  2, 18, 19, 35},
    {23,  1,  2, 16, 15, 31},
    {23,  1, 16, 15, 31, 47},
    {23,  1, 17, 18, 34, 50},
    {23, 16, 15, 31, 30, 29},
    {23, 16, 17, 33, 34, 35},
    {23, 16, 32, 31, 47, 46},
    {23, 16, 32, 33, 49, 50},   // 146
   
    {24,  1,  2, 18, 34, 35},
    {24,  1,  2, 16, 32, 31},
    {24,  1, 17, 33, 34, 35},
    {24,  1, 16, 32, 31, 30},
    {24, 16, 15, 14, 30, 46},
    {24, 16, 17, 18, 34, 50},
    {24, 16, 32, 31, 30, 46},
    {24, 16, 32, 33, 34, 50},   // 154
   
    {25,  1,  2, 18, 34, 33},
    {25,  1,  2, 16, 32, 33},
    {25,  1,  2, 16, 18, 32},
    {25,  1,  2, 16, 18, 34},
    {25,  1, 16, 32, 33, 34},
    {25,  1, 17, 33, 32, 31},
    {25, 16, 32, 31, 30, 14},
    {25, 16, 32, 33, 34, 18},   // 162
   
    {26,  1, 17, 18, 33, 34},
    {26,  1, 16, 15, 32, 31},
    {26,  1, 17, 16, 15, 31},
    {26,  1, 16, 17, 18, 34},
    {26,  1, 16, 17, 33, 34},
    {26,  1, 16, 17, 32, 31},
    {26, 16, 15, 14, 31, 30},
    {26, 16, 17, 18, 33, 34},   // 170
   
    {27,  1,  2, 17, 18, 33},
    {27,  1,  2, 16, 17, 33},
    {27,  1, 16, 17, 18, 32},
    {27,  1, 16, 15, 17, 33},
    {27, 16, 15, 14, 32, 31},
    {27, 16, 17, 18, 32, 33},
    {27, 16, 15, 31, 32, 33},
    {27, 16, 17, 31, 32, 33},   // 178
   
    {28,  1, 16, 15, 17, 32},
    {28,  1, 16, 17, 18, 33},
    {28, 16, 15, 17, 32, 33},
    {28, 16, 15, 17, 32, 31},   // 182
   
    {29,  1,  2, 17, 18, 34},
    {29,  1,  2, 16, 17, 32},
    {29, 16, 15, 32, 31, 30},
    {29, 16, 17, 32, 33, 34},   // 186
   
    {30,  1,  2,  3, 16, 17},
    {30,  1,  2,  3, 18, 19},
    {30,  1, 16, 17, 15, 14},
    {30,  1, 16, 17, 18, 19},
    {30,  1, 16, 17, 32, 48},
    {30,  1, 16, 17, 33, 49},
    {30, 16, 32, 31, 48, 47},
    {30, 16, 32, 33, 48, 49},   // 194
   
    {31,  1,  2,  3, 17, 18},
    {31,  1, 16, 15, 17, 18},
    {31, 16, 15, 32, 31, 48},
    {31, 16, 17, 32, 33, 48},
   
    {32,  1,  2,  3, 16, 19},
    {32,  1, 16, 32, 48, 49},
    {32,  1, 17, 33, 48, 49},
    {32,  3, 16, 17, 18, 19},
   
    {33,  1,  2, 17, 18, 19},
    {33,  1,  2, 15, 16, 17},
    {33, 16, 17, 32, 33, 49},
    {33, 15, 16, 31, 32, 47},
   
    {34,  1,  2,  3, 16, 32},
    {34,  1,  2,  3, 19, 35},
    {34,  1,  2, 16, 32, 48},
    {34,  1,  2, 18, 34, 50},
    {34, 16, 32, 31, 30, 29},
    {34, 16, 32, 33, 34, 35},
    {34, 16, 32, 48, 47, 46},
    {34, 16, 32, 48, 49, 50},
   
    {35,  1,  2, 16, 17, 18},
    {35,  1, 16, 17, 32, 33}
};

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

Puzzle::Puzzle(){
    int i, j;
    cnt = 0;    // 解の数をクリア
    // ボードの初期化
    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;
        }
    }
    board[Dp] = 0;
    // チップの使用フラグをクリア
    for(i = 0; i < Fv; i++){
        chip_use[i] = 0;
    }
}

// パズルの表示
void Puzzle::disp(){
    int i, j, n = 0;
    string ppp[] = {
        "・",
        "１", "２", "３", "４", "５",
        "６", "７", "８", "９", "Ａ",
        "Ｂ", "Ｃ", "Ｄ", "Ｅ", "Ｆ",
        "Ｇ", "Ｈ", "Ｉ", "Ｊ", "Ｋ",
        "Ｌ", "Ｍ", "Ｎ", "Ｏ", "Ｐ",
        "Ｑ", "Ｒ", "Ｓ", "Ｔ", "Ｕ",
        "Ｖ", "Ｗ", "Ｘ", "ｙ", "Ｚ",
        "□"
    };
    printf(" %d 回目 (%5.3f 秒)\n",
        cnt++, (float )clock() / CLOCKS_PER_SEC);
    for(i = 0; i < Bh; i++){
        for(j = 0; j < Bw; j++){
            if(j < 14) cout << ppp[ board[n]];
            n++;
        }
        cout << endl;
    }
}

// パズルの探索
void Puzzle::play( int sp){
    int cpm = sizeof(chip_data) / sizeof(cip);  // チップの置き方の数
    int i, np, idn, p1, p2, p3, p4, p5;
    // 探索場所の確認
    if( board[sp + 1] != 0 && board[sp + Bw] != 0) return;
    for(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 ||
            board[p5 = sp + chip_data[i].s5] != 0) continue;
        // チップの配置
        idn = chip_data[i].id;
        board[sp] = idn;
        board[p1] = idn;
        board[p2] = idn;
        board[p3] = idn;
        board[p4] = idn;
        board[p5] = idn;
        chip_use[idn] = 1;
        // 次の空きを探す
        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;
        board[p5] = 0;
        chip_use[idn] = 0;
    }
}

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

　1000個の解を計算するのに、25.61秒掛かっています。これは、1秒に40個弱の解しか計算できていないことを意味します。このパズルの解は、数十億通りあると言われていますので、このペースでは何年、あるいは何十年も掛かることになりそうです。

　さらなる高速化を目指して、アルゴリズムの改良を図りたいと思います。

（by　心如）