Consider an N x N chessboard whose top-left corner is colored white. And we have to cover all white cells. The only tool we 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. We have to cover all the white cells using the minimum number of tiles.
One example for N = 4 is,
The problem is to find the minimum number of tiles required as the value of N increases.
Is there a generic formulation or we need to iteratively identify the best possible solution manually.
Thank you.