棋盘覆盖问题

 

 

 

算法分析，以4*4的方格为例，特殊方格只能在左上，右上，左下，右下四个区间中的一个。排列形式可能是如下几种

（1）特殊方格在左上区域，那么其他几个区域的特殊方格可定，一定分布方式如下,用1标识其他几个区域的特殊方格

 

		1
	1	1

 （2）特殊方格在右上区域，那么其他几个区域的特殊方格可定，一定分布方式如下,用1标识其他几个区域的特殊方格

 

	1
	1	1

（3）特殊方格在左下区域，那么其他几个区域的特殊方格可定，一定分布方式如下,用1标识其他几个区域的特殊方格

 

	1	1
		1

（4）特殊方格在右下区域，那么其他几个区域的特殊方格可定，一定分布方式如下,用1标识其他几个区域的特殊方格

	1	1
	1

因此问题分解为特殊方格在一个区域，其余三个1分别变成三个不同区域的特殊方格，确定这三个方格的位置后，再分别对这四个区域进行递归解决子问题直到问题的解为最小解。

代码：

 

//棋盘覆盖问题，by lilywangcn
public class CheckBoard {
	private static int size=3;
	private static int edge=power(2,size);
	private static int[][] board=new int[edge][edge];
	private static int tile=1;
	public static void main(String[] args){
		int x=1;
		int y=1;
		board[x][y]=-1;  //设置第x行，第y列为特殊方格
		print();
		checkboard(0,0,x,y,size);
		System.out.println("after:");
		print();
	}
	
	
	public static void checkboard(int tr, int tc, int dr,int dc, int size){
		if(size==1) return ;
		else{
			size=size-1;
			int edge=power(2,size);
			
			if(dr<tr+edge&&dc<tc+edge){ //特殊方格在左上区域
				checkboard(tr,tc,dr,dc,size);
			}else{
				board[tr+edge-1][tc+edge-1]=tile;  //特殊方格不在左上区域，确定左上区域的特殊方格
				checkboard(tr,tc,tr+edge-1,tc+edge-1,size);
			}
			
			//右上区域
			if(dr<tr+edge&&dc>=tc+edge){
				checkboard(tr,tc+edge,dr,dc,size);
			}else{
				board[tr+edge-1][tc+edge]=tile;
				checkboard(tr,tc+edge,tr+edge-1,tc+edge,size);
			}
			
			//左下区域
			if(dr>=tr+edge&& dc<tc+edge){
				checkboard(tr+edge,tc,dc,dr,size);
			}else{
				board[tr+edge][tc+edge-1]=tile;
				checkboard(tr+edge,tc,tr+edge,tc+edge-1,size);
			}
			
			//右下区域
			if(dr>=tr+edge&& dc>=tc+edge){
				checkboard(tr+edge,tc+edge,dc,dr,size);
			}else{
				board[tr+edge][tc+edge]=tile;
				checkboard(tr+edge,tc+edge,tr+edge,tc+edge,size);
			}
			
			tile++;
		//	System.out.println("tile:" +tile);
		//	print();
		}
	}
	private static void print(){
		for(int i=0;i<edge;i++){
			for(int j=0;j<edge;j++)
			{
				System.out.print(board[i][j]+ " ");
			}
			System.out.println("");
		}
	}
	private static int power(int a,int o){
		int result=1;
		for(int i=0;i<o;i++)
			result*=a;
		return result;
	}
}

 

 运行结果：

size=2的时候：4*4=16

 

 

0 0 0 0 

0 -1 0 0 

0 0 0 0 

0 0 0 0 

after :

0 0 0 0 

0 -1 1 0 

0 1 1 0 

0 0 0 0 

 

size=3的时候：8*8=64；

 

0 0 0 0 0 0 0 0 

0 -1 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 

after:

0 0 0 0 0 0 0 0 

0 -1 1 0 0 2 2 0 

0 1 1 0 0 0 2 0 

0 0 0 0 2 0 0 0 

0 0 0 3 4 0 0 0 

0 3 0 0 0 0 4 0 

0 3 3 0 0 4 4 0 

0 0 0 0 0 0 0 0