White Cover

4.2

8 votes
Basic Programming, Recursion, Medium, Backtracking, Mathematics
Problem

Consider an n×n chessboard whose top-left corner is colored white. But Alice likes darkness, so she wants you to cover those white cells for her. The only tool you have are black L-shaped tiles each of which covers 3 unit cells.

Formally, each tile covers 3 unit cells satisfying the following:

  • Two of the cells are adjacent to the third (shares a side). 
  • All three of the cells do not lie on the same row or same column. 

No two tiles should overlap (cover the same cell) or go outside the board. Since these tiles cost a lot, you have to cover all the white cells using the minimum number tiles.

Input Format

  • The first line contains a positive integer T, the number of test cases, satisfying 1T10.
  • Each of the next T lines contains a positive integer n, the dimension of the chessboard, satisfying 1n1000.  

Output Format

  • For each test case, print on the first line the minimum number of tiles needed to cover all the white cells. If it is not possible to cover all the white cells using L-shaped tiles, print 1 instead.
  • If it indeed is possible to cover all the white cells, print n lines each containing n space separated integers. Let's call the minimum number of tiles X. Then we will denote each tile with a unique positive integer between 1 and X. Any cell that is covered by tile i should contain the number i. Any cell not covered by any tile should contain the number 0.
  • The printed grid should represent a valid covering. If there are multiple ways to cover the cells, you can print any one of them.
  • Refer to the sample case for more understanding. 
Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

In case of n=1, there's a single cell which is white. Since one tile needs 3 empty cells, there's no way to cover this cell.

In case of n=4, one possible covering (represented by the sample output) is the following:

Editor Image

?