Click here to Skip to main content
15,936,903 members
Please Sign up or sign in to vote.
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
Comments
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?

1 solution

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
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900