# [Community Puzzle] L-triominoes

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

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ā¦ā