15,936,903 members
1.00/5 (1 vote)
See more:
A tromino (more accurately, a right tromino) is an L-shaped
tile formed by three 1×1 squares. The problem is to cover any 2^n * 2^n
chessboard with a missing square with trominoes. Trominoes can be oriented in an
arbitrary way, but they should cover all the squares of the board except the
missing one exactly and with no overlaps .
I want to Design a divide-and-conquer algorithm for this problem. Can anyone help me?
Posted
Updated 30-Mar-15 20:55pm
v2
Mohibur Rashid 31-Mar-15 2:53am
What is the problem?
sara74 31-Mar-15 5:17am
i think but i don't know how i can do this. can you help me? do you have any idea or algorithm for do this? do you know what do i do?

Solution 1

Haven't heard of the problem before, but your idea to use divide and conquer, and the 2^n by 2^n size led me to a simple solution:

N=1:
1. place one tromino in any arbitrary orientation
-> you get a 2^1 by 2^1 board with exactly one free square in a corner
N=k+1:
1. split the board into four quadrants
2. solve the tromino placement problem for N=k
3. use that solution to fill each quadrant, and make sure the empty sqare is in the center of the board for three quadrants, and in the corner of the board for the fourth quadrant
4. place another tromino in the center
-> you get a 2^N by 2^N square filled with trominos excpet for one square in a corner