Member Avatar for brendono978

Program 66: Tromino Tiling

An N x N (where N is a power of two) chessboard can be tiled with L-shaped tiles that cover three squares so that any given square and only that square is left uncovered. Assume that the rows of the board are numbered from one to N from the top down, and the columns of the board are numbered from one to N from left to right. The input will be three integers. N ( a power of two, will be no more than sixteen), the row number of the square that should not be covered, and the column number of the square that should not be covered. The output should be an N x N array with the square not covered indicated with a blank and three squares covered by each tile indicated by a distinct ASCII character starting with !, which is 33 in decimal, and continuing with successive ASCII characters.

Example: For input of 8 3 6, the output could( solution not unique) be:

# # $ $ ( ( ) ) 
# “ “ $ ( ‘ ‘ )
% “ & & *   ‘ +
% % & ! * * + +
- - . ! ! 2 3 3 
- , . . 2 2 1 2
/ , , 0 4 1 1 5
/ / 0 0 4 4 5 5

If may help to think about the blank cell as being “tiled with a blank character”.

I have absolutely no clue where to even start with this program. Can anyone please kick me in the brain stem?

Edited by brendono978 because: n/a
  • 4 Contributors
  • 3 Replies
  • 490 Views
  • 1 Year Discussion Span
  • Latest Post Latest Post by D_Unforgiven
Member Avatar for Ancient Dragon

Look at any ascii chart and you will see the decimal value of all characters 0-255.

>> and three squares covered by each tile indicated by a distinct ASCII character starting with !,
I have no idea what that means either.

Member Avatar for Adak

Your problem is an example of an "exact cover" problem. Google that and read up. Any references to "DLX" or "Dancing Links" or "Algorithm X" typically noting Knuth, you are wise to skip - that is a very complex algorithm.

Think of your L shaped "tiles". Nevermind the blank square for now. Turned in one way, two L tiles, form a very nice rectangle of 2 X 3 squares. Each such square has a length and a width, and your big square has a length and a width, and I'll bet money that if you find a configuration where the length and width of the small tiles, are integers that are factors of the big tiles length and width, that you'd have it solved.

Don't forget to "break a tile" to put the blank square into it. (like the 3 sqr in your example)

Member Avatar for D_Unforgiven

Haha, let me guess. Computing I with professor Canning. I had fun with this one.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.