ペントミノ（pentomino.cpp、改）

// pentomino
//
//  2012.03.03 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
const Cpm = 63;

//チップパターンのデータ
struct cip{
 int id, s1, s2, s3, s4;
};
struct cip cd[] = {
 { 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 Timer{
  clock_t stime;
public:
  Timer(){ stime = clock(); }
  float GetTime();
};

float Timer::GetTime(){
  return (float )(clock() - stime) / CLOCKS_PER_SEC;
}

class Puzzle{
  Timer st;
  int cnt;
  int bd[Bw * Bh];
  int puse[Fv];
public:
  Puzzle();
  void disp();
  void play(int);
};

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

// パズルの表示
void Puzzle::disp(){
  string ppp[] = {
    "・",
    "あ", "い", "う", "え", "お",
    "か", "き", "く", "け", "こ",
    "さ", "し", "□"
  };
  cout << cnt << "回目 ("<< st.GetTime() << "秒)" << endl;
  for(int y = 0; y < Bh; y++){
    for(int x = 0; x < Sw + 2; x++){
      cout << ppp[bd[y * Bw + x]];
    }
    cout << endl;
  }
}

// パズルの探索
void Puzzle::play(int sp){
  int idn, p1, p2, p3, p4;
  // 探索場所の確認
  if( bd[sp + 1] != 0 && bd[sp + Bw] != 0){
    return;
  }
  // チップ数だけ確認
  for(int i = 0; i < Cpm; i++){
    // チップが使用中か確認
    if(puse[idn = cd[i].id] != 0) continue;
    // チップが置けるか？
    if(bd[p1 = sp + cd[i].s1] != 0) continue;
    if(bd[p2 = sp + cd[i].s2] != 0) continue;
    if(bd[p3 = sp + cd[i].s3] != 0) continue;
    if(bd[p4 = sp + cd[i].s4] != 0) continue;
    // チップの配置
    bd[sp] = idn;
    bd[p1] = idn;
    bd[p2] = idn;
    bd[p3] = idn;
    bd[p4] = idn;
    puse[idn] = 1;
    // 次の空きを探す
    int np = sp;
    while(np++ < Mp){
      if(bd[np] == 0) break;
    }
    if(np <= Mp){
      play( np); // 次のチップを探索
    }
    else{
      cnt++; // 解のカウント
      disp(); // 解を表示
    }
    // チップの除去
    bd[sp] = 0;
    bd[p1] = 0;
    bd[p2] = 0;
    bd[p3] = 0;
    bd[p4] = 0;
    puse[idn] = 0;
  }
}

int main(){
  Puzzle pzl;
  pzl.disp();
  pzl.play( Sp);
}
─────

タグ：パズル