1. In the Domino Tiling problem, you are given a 2^k x 2^k checkerboard with alt
ID: 3566267 • Letter: 1
Question
1. In the Domino Tiling problem, you are given a 2^k x 2^k checkerboard with alternating black and white squares. Two squares already have red tiles placed on them. You are required to fully tile the rest of the board with domino-shaped tiles, that is, rectangular tiles one square tall and two squares wide. Tiles can be rotated. There are two versions of the problem. (a) Both red tiles are on squares of the same color, either black or white. Prove that this version of the tiling problem has no solution. (b) The two red tiles are on squares of different colors, one black and one white. Describe a divide-and conquer algorithm in pseudocode to solve the tiling problem. Make sure you consider all cases that might arise.Explanation / Answer
1) when red colour is on the squares of same colour i.e either white or black there will be no solution in such case becuase since we have alternate black an white tile for tiling problem having there must be perfect bipartite matching between black and white squares. so in this case no perfect bipartite matching between black and white squares. so we will never have a solution.
2) Base Case: A 2 by 2 square can be tiled.
Induction:
1) Divide the square into 4,n/2 by n/2 square.
2) Place the tromino at the
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.