$3(a)$

Now, we are given the following $8*8$ checkerboard with a missing cell $(0).$Draw the checkerboard after dividing it into $4$ sub $-$checkerboards such that

$$ each sub$-$checkerboard is a square, and

$$ each sub$-$checkerboard contains exactly either a missing cell $(0)$ or a cell

covered by a triomino.

Hint: Place a triomino at a suitable location to divide the checkerboard.

$3($b$)$

We represent the checkerboard by using a two$-$dimensional integer arrayQuestion $3.$

A triomino can be arranged as one of the followings.

In this question, we are given a checkerboard with a missing cell $($denoted by $"0"),$ and

we are asked to tile it by using triominoes. An example is provided in Figure $1.$

$($a$)$ before tiling

$($b$)$ after tiling

Figure $1.$ An example of tiling a checkerboard with a missing cell

$3($a$)$ Now, we are given the following $88$ checkerboard with a missing cell $("0").$

Draw the checkerboard after dividing it into $4$ sub$-$checkerboards such that:

each sub$-$checkerboard is a square, and

each sub$-$checkerboard contains exactly either a missing cell $("0")$ or a cell

covered by a triomino.

Hint: Place a triomino at a suitable location to divide the checkerboard.

$3($b$)$ We represent the checkerboard by using a two$-$dimensional integer array

$A[0..m-1,0..m-1],$ where $m$ is a power of two. For example, the value of $m$ can be $2,4,$

$8,16,32,$dots.. Suppose that, in the two$-$dimensional array $A,$ the missing cell is set to

$0$ and the other cells are initialized to $-1.$

Write an algorithm $($i$.$e$.,$ pseudo$-$code$)$ using divide$-$and$-$conquer to fill the two$-$

dimensional array $A[0..m-1,0..m-1]$ to satisfy all the following conditions:

all cells $($except the missing cell$)$ are assigned positive integers,

only the cells belonging to the same triomino can be assigned the same integer.

Please refer to the sample output in Figure $1($b$).$

A$[0..$m$1,0..$m$1],$ where m is a power of two. For example, the value of m can be $2,4,$

$8,16,32,......$ Suppose that, in the two$-$dimensional array A$,$ the missing cell is set to $0$ and the other cells are initialized to $1.$

Write an algorithm $($i$.$e$.,$ pseudo$-$code$)$ using divide$-$and$-$conquer to fill the two$-$dimensional array A$[0..$m$1,0..$m$1]$ to satisfy all the following conditions:

$$ all cells $($except the missing cell$)$ are assigned positive integers,

$$ only the cells belonging to the same triomino can be assigned the same integer.

Please refer to the sample output in Figure $1($b$).$