Chessboard coverage problem (divide and conquer)

Problem description ： In a $2^k\ast 2^k(k>0)$ The chessboard of , There is only one special square that is different from other squares , Now we're going to use... As shown in the figure below L Dominoes cover all squares except special squares , Any two dominoes cannot overlap , give A covering method .

This problem can divide the chessboard into four quadrants of the same size , Then this special square must exist in one of the quadrants , According to the different quadrants of the square ,L The arrangement of dominoes ：

In this way, there can be one in the four quadrants “ Special grid ”, Meet the conditions of partition .

One of the most important characteristics of divide and conquer is that a complex large problem can be decomposed into several small problems with the same properties or solution ideas , And small problems are easier to solve .

In the process of code implementation, you need to create a two-dimensional array with the same size as the initial chessboard to save the number of dominoes covered by each square of the chessboard .

java Code

public class Solution {
    
	int tile; 												//  Number of dominoes , from 1 Start 
	int[][] board; 											//  A two-dimensional array corresponding to the initial chessboard 

	public Solution(int size) {
     							//  Constructors , initialization 
		board = new int[size][size];
		tile = 1;
	}

	// (tr,tc) Indicates the row and column number of the square in the upper left corner of a quadrant ,(dr,dc) Indicates the row and column number of a special square , The row and column number in the upper left corner of the initial chessboard (0,0)
	public void chessBoard(int tr, int tc, int dr, int dc, int size) {
    
		if (size == 1) {
     									//  Recursive export 
			return;
		}
		
		int t = tile++; 									//  Take dominoes 
		int s = size >> 1; 									//  Split the chessboard 
		//  Consider the upper left quadrant 
		if (dr < tr + s && dc < tc + s) {
     					//  Special squares handle this quadrant in this quadrant 
			chessBoard(tr, tc, dr, dc, s);
		} else {
     													//  Special squares are not in this quadrant 
			board[tr + s - 1][tc + s - 1] = t; 						// t Dominoes cover the bottom right corner of the quadrant 
			chessBoard(tr, tc, tr + s - 1, tc + s - 1, s); 			//  Treat the lower right corner as a special square and continue to work on the quadrant 
		}
		//  Consider the upper right quadrant 
		if (dr < tr + s && dc >= tc + s) {
    					//  Special squares handle this quadrant in this quadrant 
			chessBoard(tr, tc + s, dr, dc, s);
		} else {
     													//  Special squares are not in this quadrant 
			board[tr + s - 1][tc + s] = t; 							// t Dominoes cover the bottom left corner of the quadrant 
			chessBoard(tr, tc + s, tr + s - 1, tc + s, s); 			//  Treat the lower left corner as a special square and continue to work on the quadrant 
		}
		//  Consider the lower left quadrant 
		if (dr >= tr + s && dc < tc + s) {
     					//  Special squares handle this quadrant in this quadrant 
			chessBoard(tr + s, tc, dr, dc, s);
		} else {
     													//  Special squares are not in this quadrant 
			board[tr + s][tc + s - 1] = t; 							// t Dominoes cover the top right corner of the quadrant 
			chessBoard(tr + s, tc, tr + s, tc + s - 1, s); 			//  Treat the upper right corner as a special square and continue to work on the quadrant 
		}
		//  Consider the lower right quadrant 
		if (dr >= tr + s && dc >= tc + s) {
     				//  Special squares handle this quadrant in this quadrant 
			chessBoard(tr + s, tc + s, dr, dc, s);
		} else {
     													//  Special squares are not in this quadrant 
			board[tr + s][tc + s] = t; 								// t Dominoes cover the top left corner of the quadrant 
			chessBoard(tr + s, tc + s, tr + s, tc + s, s); 			//  Treat the upper left corner as a special square and continue to work on the quadrant 
		}
	}

	public static void main(String[] args) {
    
		int k = 3;
		int size = 1 << k;
		Solution s = new Solution(size);
		int tr = 1;											//  The line number of the special square 
		int tc = 2;											//  Column numbers of special squares 
		s.board[tr][tc] = 0; 								//  For special squares 0 Express 
		s.chessBoard(0, 0, tr, tc, size);
		//  Print overlay results 
		for (int i = 0; i < size; i++) {
    
			for (int j = 0; j < size; j++) {
    
				System.out.print(s.board[i][j] + "\t");
			}
			System.out.println();
		}
	}	
}

Running results （0 Indicates the position of a special square ,3 The same number represents a dominoes ）

Time complexity analysis

use $T(k)$ Means solving a problem $2^k\ast 2^k$ The time of the chessboard

• $k=1$,$T(k)=O(1)$
• $k>1$,$T(k)=4T(k-1)$

$\therefore T(k)=O(4^k)$