最近碰到一個學弟問我一個問題相當困難，我用STL寫了一個程式，
可是還是需要花相當久的時間才能解出，po在這裡看看各位高手
有無好解法？
設計一拼盤遊戲程式，其規格如下：
一、拼盤內有八塊面積相同，形狀不同的積木，其尺寸如
下：
■■■□□□□□ ■■□□□□□□ ■■□□□□□□ ■■□□□□□□
■□□□□□□□ ■■■■□□□□ ■■■□□□□□ ■■□□□□□□
■□□□□□□□ ■■□□□□□□ ■■■□□□□□ □■■□□□□□
■■■□□□□□ □□□□□□□□ □□□□□□□□ □■■□□□□□
□□□□□□□□ □□□□□□□□ □□□□□□□□ □□□□□□□□
□□□□□□□□ □□□□□□□□ □□□□□■■□ □□□□□□■■
□□□□□■■■ □□□□■■■■ □□□□□■■□ □□□□□□■■
□□□■■■■■ □□□□■■■■ □□□□■■■■ □□□□■■■■
拼盤可分為8*8的小正方形，而每個積木各佔8個小正方形，上圖中每個拼
盤內各顯示兩個積木的形狀。
二、下圖為八塊積木組合成正方形拼盤的一個例子。
┌──────┬────┐
│ │ │
│ ┌──┐ │ ꄠ │
│ │ │ ├────┤
├─┘ ┌┴─┴┐ ┌┤
│ │ │ ││
├───┴┐ ┌┴─┬┘│
│ │ꄠ│ │ │
│ ┌┴─┘ │ │
└───┴─────┴─┘
三、設計此拼盤遊戲程式，功能如下：
利用電腦解出這個拼盤遊戲，共有多少種組合，同時須將
各種組合列印在螢幕上。
***************
有一點要注意：方塊是可以旋轉或鏡射的。
經過我的分析，發現該問題實在是組合爆炸
，即使使用了經驗法則來展樹一樣需要很久的時間，我並沒有花時間全部跑完
，估計也許需要半個小時到一個小時的時間。依我的看法這類題目是沒有辦法
在比賽的時候做出來的，只是平時無聊好玩。做此問題的時候用到一個主要的
經驗法則：那就是如果目前所剩沒有被磚塊佔滿的地方是連續的，就把該連續
區塊的面積算出來，如果可以被8整除，代表有希望繼續做下去，如果不能被
8整除的話，那塊地方是絕對沒辦法被填滿的，因為所有的方塊都是由8格組成
。用如此方法可以在展樹約第三層〈也就是擺了第三塊磚〉的時候就把絕大多
數不可能的狀況刪除掉，可是即使是如此，速度還是非常慢。如果依照你的問
題，也就是磚塊可以鏡射及旋轉的話，那麼第一層有約250種擺法，第二層平
均有140種擺法，第三層平均有100種擺法，第四層平均有50種擺法，第五層平
均有10種擺法，到這裡已經有約1750000000種可能性了，這才到第五層而已，
要到第八層才算完畢喔...。
下面是我寫的程式，很慢...不過應該是對的。我還沒跑完過，有時間的人
可以幫我研究一下我哪裡多浪費時間了.... sigh...
// 注意，本程式需用具有STL的compiler來編譯
/*
Problem description
===================
Use the following blocks with variation of their spins and flips to
fill a 8x8 grid completely.
■■■ □□■■■ ■■□□ ■■■■ ■■□ □■■□ ■■□ □□■■
■□□ ■■■■■ ■■■■ ■■■■ ■■■ □■■□ ■■□ □□■■
■□□ ■■□□ ■■■ ■■■■ □■■ ■■■■
■■■ □■■
Write a program to produce all solutions of the problem.
Sample result
==============
※※※※●●●●
※□□※●●●●
※□□※□□□□
□□●●●□□■
□□●●●□□■
■■■●○○■■
■■■●○○■■
■■○○○○■■
*** source code written by Cherng-yann Ing. All rights reserved.
*/
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
using namespace std;
struct Vector
{
short row, col;
Vector() {}
Vector(short _row, short _col)
: row(_row), col(_col)
{}
bool isInside(int r1, int c1, int r2, int c2)
{
return row >= r1 && col >= c1 && row < r2 && col < c2;
}
};
inline Vector operator + (const Vector &a, const Vector &b)
{
return Vector(a.row + b.row, a.col + b.col);
}
inline bool operator > (const Vector &a, const Vector &b)
{
if (a.row > b.row)
return true;
if (a.row < b.row)
return false;
if (a.col > b.col)
return true;
return false;
}
inline bool operator == (const Vector &a, const Vector &b)
{
return a.row == b.row && a.col == b.col;
}
#define NumDotPerBlock 8
struct Block
{
Vector b[8];
Vector & operator [] (int index)
{
return b[index];
}
void normalize()
{
int i, j, m;
Vector t;
Vector upperLeft = b[0];
for(i=1;i<NumDotPerBlock;i++)
{
if (b[i].row < upperLeft.row)
upperLeft.row = b[i].row;
if (b[i].col < upperLeft.col)
upperLeft.col = b[i].col;
}
for(i=0;i<NumDotPerBlock;i++)
{
b[i].row -= upperLeft.row;
b[i].col -= upperLeft.col;
}
for(i=0;i<NumDotPerBlock;i++)
{
m = i;
for(j=i+1;j<NumDotPerBlock;j++)
{
if (b[j] > b[m])
m = j;
}
if (m != i)
{
t = b[m];
b[m] = b[i];
b[i] = t;
}
}
}
void getFlipHoriz(const Block &blk)
{
int i;
for(i=0;i<NumDotPerBlock;i++)
{
b[i].col = -blk.b[i].col;
b[i].row = blk.b[i].row;
}
normalize();
}
void getFlipVert(const Block &blk)
{
int i;
for(i=0;i<NumDotPerBlock;i++)
{
b[i].col = blk.b[i].col;
b[i].row = -blk.b[i].row;
}
normalize();
}
void getSpin(const Block &blk)
{
int i;
for(i=0;i<NumDotPerBlock;i++)
{
b[i].row = -blk.b[i].col;
b[i].col = blk.b[i].row;
}
normalize();
}
void show()
{
Vector iv;
Vector lowerRight;
int i;
short map[8][8];
memset(map, 0, sizeof(map));
lowerRight = b[0];
for(i=0;i<NumDotPerBlock;i++)
{
map[b[i].row][b[i].col] = 1;
if (b[i].row > lowerRight.row)
lowerRight.row = b[i].row;
if (b[i].col > lowerRight.col)
lowerRight.col = b[i].col;
}
for(iv.row=0;iv.row<=lowerRight.row;iv.row++)
{
for(iv.col=0;iv.col<=lowerRight.col;iv.col++)
{
if (map[iv.row][iv.col] == 0)
cout << "□";
else
cout << "■";
}
cout << endl;
}
}
};
bool operator == (const Block &a, const Block &b)
{
int i;
for(i=0;i<NumDotPerBlock;i++)
if (!(a.b[i] == b.b[i]))
return false;
return true;
}
#define MaxBlocks 37
vector<Block> blocks;
short blockData[] =
{
0, 0, 0, 1, 0, 2,
1, 0,
2, 0,
3, 0, 3, 1, 3, 2,
0, 3, 0, 4, 0, 5,
1, 0, 1, 1, 1, 2, 1, 3, 1, 4,
0, 0, 0, 1,
1, 0, 1, 1, 1, 2, 1, 3,
2, 0, 2, 1,
0, 0, 0, 1, 0, 2, 0, 3,
1, 0, 1, 1, 1, 2, 1, 3,
0, 0, 0, 1,
1, 0, 1, 1, 1, 2,
2, 0, 2, 1, 2, 2,
0, 1, 0, 2,
1, 1, 1, 2,
2, 0, 2, 1, 2, 2, 2, 3,
/*
■■■□□□□□ ■■□□□□□□ ■■□□□□□□ ■■□□□□□□
■□□□□□□□ ■■■■□□□□ ■■■□□□□□ ■■□□□□□□
■□□□□□□□ ■■□□□□□□ ■■■□□□□□ □■■□□□□□
■■■□□□□□ □□□□□□□□ □□□□□□□□ □■■□□□□□
□□□□□□□□ □□□□□□□□ □□□□□□□□ □□□□□□□□
□□□□□□□□ □□□□□□□□ □□□□□■■□ □□□□□□■■
□□□□□■■■ □□□□■■■■ □□□□□■■□ □□□□□□■■
□□□■■■■■ □□□□■■■■ □□□□■■■■ □□□□■■■■
*/
0, 0, 0, 1,
1, 0, 1, 1,
2, 1, 2, 2,
3, 1, 3, 2,
0, 2, 0, 3,
1, 2, 1, 3,
2, 0, 2, 1, 2, 2, 2, 3,
};
#define NOT_OCCUPIED 9
#define OCCUPIED 10
#define MaxMapHeight 8
#define MaxMapWidth 8
struct BlockOperator
{
short blk;
Vector pos;
BlockOperator(short _blk, Vector _pos)
: blk(_blk), pos(_pos)
{
}
};
typedef vector<BlockOperator> BlockOperators;
typedef short MapArray[MaxMapHeight][MaxMapWidth];
bool blkUsed[MaxBlocks];
struct Map;
class heuristic
{
public:
MapArray map;
short accumulatedArea[64];
void dfs(Vector v, int pattern)
{
static Vector directions[4] =
{ Vector(0, 1),
Vector(1, 0),
Vector(0, -1),
Vector(-1, 0), };
if (map[v.row][v.col] == NOT_OCCUPIED)
{
map[v.row][v.col] = pattern;
accumulatedArea[pattern] ++;
int i;
Vector u;
for(i=0;i<4;i++)
{
u = v + directions[i];
if (u.isInside(0, 0, 8, 8))
{
dfs(u, pattern);
}
}
}
}
bool judge(MapArray _map, Map *m)
{
int i, j;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
if (_map[i][j] == NOT_OCCUPIED)
map[i][j] = NOT_OCCUPIED;
else
map[i][j] = OCCUPIED;
for(i=0;i<64;i++)
accumulatedArea[i] = 0;
int count = 0;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
if (map[i][j] == NOT_OCCUPIED)
{
dfs(Vector(i, j), count++);
}
}
for(i=0;i<count;i++)
{
if (accumulatedArea[i] % 8 != 0)
return false;
}
return true;
}
};
struct Map
{
MapArray map;
short & operator () (int dx, int dy)
{
return map[dx][dy];
}
short & operator () (const Vector &p)
{
return map[p.row][p.col];
}
void clear()
{
Vector i;
for(i.row=0;i.row<MaxMapHeight;i.row++)
for(i.col=0;i.col<MaxMapWidth;i.col++)
(*this)(i) = NOT_OCCUPIED;
}
Map()
{
clear();
}
bool canContinue()
{
return heuristic().judge(map, this);
}
bool canPerform(BlockOperator op)
{
int i;
Block &block = blocks[op.blk];
Vector p;
for(i=0;i<NumDotPerBlock;i++)
{
p = op.pos + block[i];
if (!p.isInside(0, 0, MaxMapHeight, MaxMapWidth))
return false;
if ((*this)(p) != NOT_OCCUPIED)
return false;
}
return true;
}
void enumOperators(BlockOperators &bos)
{
Vector i;
int b;
for(i.row=0;i.row<MaxMapHeight;i.row++)
for(i.col=0;i.col<MaxMapWidth;i.col++)
{
for(b=0;b<MaxBlocks;b++)
if (!blkUsed[b])
if (canPerform(BlockOperator(b, i)))
{
bos.push_back(BlockOperator(b, i));
}
}
}
void fill(short blk, Vector pos, short value)
{
int i;
Block &block = blocks[blk];
Vector p;
for(i=0;i<NumDotPerBlock;i++)
{
p = pos + block[i];
(*this)(p) = value;
}
}
void perform(BlockOperator op)
{
fill(op.blk, op.pos, op.blk);
}
void unperform(BlockOperator op)
{
fill(op.blk, op.pos, NOT_OCCUPIED);
}
void show()
{
Vector i;
for(i.row=0;i.row<MaxMapHeight;i.row++)
{
for(i.col=0;i.col<MaxMapWidth;i.col++)
if ((*this)(i) == NOT_OCCUPIED)
cout << " ." ;
else
cout << setw(2) << (*this)(i);
cout << endl;
}
}
};
Map map;
bool addBlockWithoutDup(const Block &blk)
{
int i;
for(i=blocks.size()-1;i>=0;i--)
{
if (blocks[i] == blk)
return true;
}
blocks.push_back(blk);
return false;
}
void loadData() // 此處產生所有的方塊，包括旋轉和鏡射
{
int i, j, k = 0;
blocks.resize(MaxBlocks);
for(i=0;i<MaxBlocks;i++)
{
for(j=0;j<NumDotPerBlock;j++)
{
blocks[i][j].row = blockData[k++];
blocks[i][j].col = blockData[k++];
}
blocks[i].normalize();
}
Block temp, temp1;
//下面的迴圈產生鏡射，有分左又鏡射及上下鏡射
for(i=blocks.size()-1;i>=0;i--)
{
temp.getFlipHoriz(blocks[i]);
addBlockWithoutDup(temp);
temp.getFlipVert(blocks[i]);
addBlockWithoutDup(temp);
}
//下面的迴圈產生對於每個方塊的四種選轉變化
for(i=blocks.size()-1;i>=0;i--)
{
temp.getSpin(blocks[i]);
addBlockWithoutDup(temp);
temp1.getSpin(temp);
addBlockWithoutDup(temp1);
temp.getSpin(temp1);
addBlockWithoutDup(temp);
}
}
void showBlocks()
{
int i;
for(i=0;i<blocks.size();i++)
{
cout << i << endl;
if (i==58)
{
cout << "hello" << endl;
}
blocks[i].show();
cout << endl;
}
}
void tryMove(int depth)
{
if (depth == 8)
{
map.show();
cout << endl;
return;
}
if (!map.canContinue())
return;
BlockOperators ops;
map.enumOperators(ops);
short i;
for(i=0;i<ops.size();i++)
{
if (depth < 2)
cout << depth << ":" << i << " out of " << ops.size() << endl;
// 上面兩行印出前面兩階的展樹狀況。
if (map.canPerform(ops[i]))
{
map.perform(ops[i]);
blkUsed[ops[i].blk] = true;
tryMove(depth+1);
blkUsed[ops[i].blk] = false;
map.unperform(ops[i]);
}
}
}
int main()
{
loadData();
tryMove(0);
return 0;
}
--
Chaos is the best description of the constant state of human society.
Therefore, dynamic balance is required for us to to survive when vital fault
occurrs. So in the society, we don't chase for peace and order, but existence
and survival, instead.
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: h51.s81.ts30.hi
> -------------------------------------------------------------------------- <
發信人: [email protected] (小光光), 看板: C_and_CPP
標 題: Re: 拼磚塊問題
發信站: 小魚的紫色花園 (Sun Dec 6 19:32:40 1998)
轉信站: Ptt!warp.m6.ntu!fpg
※ 引述《[email protected] (應)》之銘言：
: 二、下圖為八塊積木組合成正方形拼盤的一個例子。
: ┌──────┬────┐
: │ │ │
: │ ┌──┐ │ ꄠ │
: │ │ │ ├────┤
: ├─┘ ┌┴─┴┐ ┌┤
: │ │ │ ││
: ├───┴┐ ┌┴─┬┘│
: │ │ꄠ│ │ │
: │ ┌┴─┘ │ │
: └───┴─────┴─┘
: 三、設計此拼盤遊戲程式，功能如下：
: 利用電腦解出這個拼盤遊戲，共有多少種組合，同時須將
: 各種組合列印在螢幕上。
: ***************
: 有一點要注意：方塊是可以旋轉或鏡射的。
我沒看你的程式是怎麼寫的...看不太懂, compiler 也不支援 STL
我猜測你的問題在於遞迴的方式上, 大概是
每一層是針對某一個磚塊, 找出可以放的位置然後遞迴下去
我的做法是從另一個角度看這個問題
從盤面上左上角數過來第一個空白位置,
已知這格空白位置一定會被填到,
於是乎我遞迴找一塊可以填入的磚塊
我沒有檢查過程中相連空白是否為 8 的倍數,
執行時間不到一秒, 共 48 組解
這程式花了我大約 70 分鐘
=================================================
#include <stdio.h>
int ans;
int map[10][10];
int used[8];
int nblock[8]; // 各種形狀之旋轉數
int block[8][8][8][2]; // 磚塊座標 [編號][旋轉][第k個座標][xy座標]
int blockdata[8][8][8]={ // 磚塊資料
{{1,1,1,1},
{1,0,0,1},
{1,0,0,1}},
{{1,1,1,1},
{1,1,1,1}},
{{0,1,1},
{0,1,1},
{1,1,0},
{1,1,0}},
{{1,1,1,1},
{0,1,1,0},
{0,1,1,0}},
{{1,1,1},
{1,1,1},
{0,1,0},
{0,1,0}},
{{0,1},
{0,1},
{1,1},
{1,1},
{1,1}},
{{1,1,1},
{1,1,1},
{1,1,0}},
{{0,0,1,1},
{0,0,1,1},
{1,1,1,1}}};
void Add(int item[8][8],int to)
{
int temp[8][2];
int i,j,p=0;
int sx,sy;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
if(item[i][j]) {
if(p==0) {
sx=i; sy=j;
}
temp[p][0]=i-sx;
temp[p][1]=j-sy;
p++;
}
for(i=0;i<nblock[to];i++)
if(memcmp(block[to][i],temp,sizeof(int)*8*2)==0)
return;
memcpy(block[to][nblock[to]++],temp,sizeof(int)*8*2);
}
void Init(void)
{
int i,j,k;
int tmpblock[8][8][8];
for(i=0;i<10;i++)
map[i][0]=map[0][i]=map[9][i]=map[i][9]=1;
for(k=0;k<8;k++) { // 將磚塊轉以座標表示
for(i=0;i<8;i++)
for(j=0;j<8;j++) {
tmpblock[0][i][j]=blockdata[k][i][j];
tmpblock[1][i][j]=blockdata[k][7-i][j];
tmpblock[2][i][j]=blockdata[k][i][7-j];
tmpblock[3][i][j]=blockdata[k][7-i][7-j];
tmpblock[4][i][j]=blockdata[k][j][i];
tmpblock[5][i][j]=blockdata[k][7-j][i];
tmpblock[6][i][j]=blockdata[k][j][7-i];
tmpblock[7][i][j]=blockdata[k][7-j][7-i];
}
for(i=0;i<8;i++)
Add(tmpblock[i],k);
}
}
int CanPut(int x,int y,int a,int b)
{
int i;
for(i=1;i<8;i++)
if(map[x+block[a][b][i][0]][y+block[a][b][i][1]])
return 0;
return 1;
}
void Put(int x,int y,int a,int b,int num)
{
int i;
for(i=0;i<8;i++)
map[x+block[a][b][i][0]][y+block[a][b][i][1]]=num;
}
void Print(void)
{
int i,j;
const char symbol[8*2+1]="※●□■§┼ˇ。";
printf("%d\n",ans);
for(i=1;i<=8;i++) {
for(j=1;j<=8;j++)
printf("%c%c",symbol[(map[i][j]-1)*2],
symbol[(map[i][j]-1)*2+1]);
printf("\n");
}
}
void Run(int a,int x,int y)
{
int i,j;
if(a==8) {
ans++;
Print();
return;
} else
while(map[x][y]) {
y++;
if(y==9) {
x++;
y=1;
}
}
for(i=0;i<8;i++)
if(!used[i])
for(j=0;j<nblock[i];j++)
if(CanPut(x,y,i,j)) {
Put(x,y,i,j,a+1);
used[i]=1;
Run(a+1,x,y);
used[i]=0;
Put(x,y,i,j,0);
}
}
int main(void)
{
Init();
Run(0,1,1);
return 0;
}
--
★ Origin:
︿︱︿ 小魚的紫色花園
﹀ fpg.m4.ntu.edu.tw (140.112.214.200)