Suppose you are given an n n checkerboard with some of the

Suppose you are given an n × n checkerboard with some of the squares deleted. You have a collection of 2 × 1 dominoes, which can be used to cover any two adjacent squares. Describe an algorithm to determine if the board can be “tiled” with dominoes, i.e., if we can place dominoes on the board (either horizontally or vertically) such that each one covers two squares (neither of which is deleted), and no two dominoes overlap. As an example, consider Figure 1.

Figure 1: Checkerboard with some squared deleted on the left, and a feasible domino tiling on the right.

Solution

Algorithm :

1. First count the cells left in n * n matrix

2. Now let the count of the cell be int x.

3. if ( int x = odd )

dominoes cant be placed one cell will left alone

4. if (int x = even)

Start from cell (1,1 )

if found a horizontal empty cell as adjacent ,

Place dominoes ( horizontaly)

   else

place dominoes (Verticaly)

Whenever a dominoes found next

move to the next cell

5.Repeat the step 4 till ( nth * n th ) cell is found