分治法解决棋盘覆盖

L型骨牌覆盖棋盘：

问题描述：

      在一个2k×2k 个方格组成的棋盘中，有一个方格与其它不同，称该方格为特殊方格，且称该棋盘为一特殊棋盘。棋盘覆盖问题如下：

• 要求用图示的4种L形态骨牌覆盖给定的特殊棋盘
• 限制条件：覆盖给定特殊棋盘上除特殊方格（红色）以外的所有方格
• 限制条件：任何2个L型骨牌不得重叠覆盖  
• 

解决思路：

                                  

1：必须在一个2k×2k 个方格组成的棋盘中，那是因为只有是2的k次方才能用四种L形骨牌完全覆盖（除去特殊方块）。

2：在2k×2k 的棋盘中，可以将其平均分为4份，正如上图中那样。

3：按照第二步进行递直到分为1*1的棋盘，此时有      if(size==1) return;  

代码：

tr：棋盘左上角的行号

tc：棋盘左上角的列号  

dr：特殊方格左上角的行号

dc：特殊方格左上角的列号  

size:棋盘规格（边长）

运行结果：

说明：

2k

1:  0是特殊方格所在的位置

2: 在任何一个2k×2k 的棋盘中用到L型骨牌的个数为(4^k-1)/3

#include "stdafx.h"
#include <iostream>
#include <iomanip>
using namespace std;
int Board[8][8];//8*8棋盘 
int tile=1; //骨牌编号 从1开始
void CheesBoard(int tr,int tc,int dr,int dc,int size);


int _tmain(int argc, _TCHAR* argv[])
{
	CheesBoard(0,0,4,6,8);
	for(int i=0;i<8;i++){
		for(int j=0;j<8;j++){
			cout<<setw(3)<<Board[i][j];
		}
		cout<<endl;
	}
	int a;
	cin>>a;
	return 0;
}
void CheesBoard(int tr,int tc,int dr,int dc,int size){
	if(size==1) return;
	int t=tile++;//L型骨牌编号
	int s=size/2;//分割棋盘
 //操作左上角子棋盘 
	if(dr<tr+s&&dc<tc+s){//如果特殊方格在此棋盘中
		CheesBoard(tr,tc,dr,dc,s);
	}
	else{//特殊方格不在此棋盘中
		Board[tr+s-1][tc+s-1]=t; //用编号为t的骨牌覆盖右下角  
		CheesBoard(tr,tc,tr+s-1,tc+s-1,s);//操作其余方格
	}
//操作右上角子棋盘 
	if(dr<tr+s&&dc>=tc+s){//如果特殊方格在此棋盘中
		CheesBoard(tr,tc+s,dr,dc,s);
	}
	else{//特殊方格不在此棋盘中
		Board[tr+s-1][tc+s]=t;//用编号为t的骨牌覆盖左下角 
		CheesBoard(tr,tc+s,tr+s-1,tc+s,s); //操作其余方格  
	}
 //操作左下角子棋盘  
	if(dr>=tr+s&&dc<tc+s){//如果特殊方格在此棋盘中 
		CheesBoard(tr+s,tc,dr,dc,s);
	}
	else{//特殊方格不在此棋盘中
		Board[tr+s][tc+s-1]=t;//用编号为t的骨牌覆盖右上角
		CheesBoard(tr+s,tc,tr+s,tc+s-1,s);//操作其余方格
	}
//操作右下角子棋盘 
	if(dr>=tr+s&&dc>=tc+s){//如果特殊方格在此棋盘中
		CheesBoard(tr+s,tc+s,dr,dc,s);
	}
	else{//特殊方格不在此棋盘中
		Board[tr+s][tc+s]=t;//用编号为t的骨牌覆盖左上角
		CheesBoard(tr+s,tc+s,tr+s,tc+s,s);//操作其余方格
	}
}

运行结果：

说明：

2k

1:  0是特殊方格所在的位置

2: 在任何一个2k×2k 的棋盘中用到L型骨牌的个数为(4^k-1)/3