# [Community Puzzle] L-triominoes

Coding Games and Programming Challenges to Code Better

Created by @VilBoub,validated by @jujurocking,@EricMoret and @Cr3aHal0.
If you have any issues, feel free to ping them.

Nice puzzle!
I think the statement is a bit too revealing - only the technical implementation remained as task.
I am not sure I would have found that such simple D&C method exists, probably would have tried a much more complicated and slower backtracking approach first…

1 Like

if the algorithm choice was left to the user it wouldn’t have a unique solution as there are other ways to successfully layout the tiles.

5 Likes

I’m thinking about something, it’s not about the puzzle … but the puzzle shows that (2^n)²-1 is always multiple of 3.

EDIT

a²-b²=(a+b)(a-b) => (2^n)²-1 = (2^n+1)(2^n-1)
2^n can’t be a multiple of 3, so 2^n = 3k+1 or 3k+2
If 2^n is 3k+1, 2^n-1 is 3k => multiple of 3
If 2^n is 3k+2, 2^n+1 is 3k+3 => multiple of 3
So (2^n+1)(2^n-1) is multiple of 3.
Ok that’s not obvious a priori, but it is true.

3 Likes

(2^n)^2−1=4^n−1. Modulo 3, it’s just 1^n−1=0.

Ok thanks, i didn’t know that (a^n)%b = (a%b)^n.
I’m not very familiar with modulo.

4 Likes

Modular arithmetic behaves just like regular arithmetic except for division and exponentiation.

For division, the problem is that there are way more zeros than in usual arithmetic (because `k * n = 0 (mod n)` for all integers `n, k`). But it’s not too complicated, actually. There are two basic ideas:

1. If we have a congruence `a * b = a * c (mod n)`, then we can deduce that `b = c (mod n/gcd(a, n))`. This can be proven using the definitions of congruence mod n and GCD.
2. If `gcd(a, n) = 1`, then there exists an integer `b` such that `a * b = 1 (mod n)`. This `b` is just `1/a`, i.e., you can divide by any number `a` that shares no prime factors with `n`, simply by multiplying with its inverse `b`.

For exponentiation, one direction is pretty intuitive: if `a = b (mod n)`, then `a^k = b^k (mod n)`. But you should keep in mind that the exponents are NOT to be taken `(mod n)`, e.g. `2 = 10 (mod 8)`, but `2^2 = 4 =/= 0 = 2^8 (mod 8)`. For dealing with exponents, you’ll need to consult Fermat & Euler’s theorems (they aren’t complicated; they really just make your life easier).

how exactly do you check for other solutions? there doesn’t necessarily have to be a single solution.

the following is a solution for test 4…but you seem to want a different solution. You might want the connections to be mirrored, but there’s no point in accepting a version just because your algorithm pulls it out first

``````+--+--+--+--+--+--+--+--+
|     |     |     |     |
+--+  +--+  +--+  +  +--+
|  |  |  |  |  |  |  |  |
+  +--+  +--+  +--+--+  +
|     |     |     |     |
+--+--+--+--+--+--+--+--+
|     |     |     |     |
+--+  +--+  +--+  +  +--+
|  |  |  |  |  |  |  |  |
+  +--+  +--+  +--+--+  +
|     |     |     |     |
+--+--+--+--+--+--+--+--+
|##|  |     |  |     |  |
+--+  +  +--+  +  +--+  +
|     |  |     |  |     |
+--+--+--+--+--+--+--+--+
``````

I would like to post a picture, but I can’t seem to do it

The statement explains why there is only 1 solution, after “Solve puzzle using divide and conquer method.”
There also is an example below.

a little weak this excuse. if a very specific procedure is required, the code can simply be in the description. if there are several solutions, these should always be allowed.

When you create an “in/out puzzle”, you can do only one solution for each test. When there are several solutions, the puzzle’s creator has to define how to choose between these solutions.

With this puzzle, it is well described.

therefore the puzzle has to be adjusted. just saying “solve it exactly like this” is pretty bad for a puzzle. it is simply a guide and has nothing to do with a puzzle.
either you make general statements and ask about the number of all possibilities, or you narrow down the space more.

updated statement :

“The goal of the puzzle is to apply the “divide and conquer” method in order to fill a square…”