cover chessboard with tromino using divide and conquer

Question

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 30-Mar-15 20:37pm

sara74

Updated 30-Mar-15 20:55pm

Mohibur Rashid

v2

Add a Solution

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

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Stefan_Lang · Answer 1 · 2015-04-08T03:43:00

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