# [Community Puzzle] tiling by squares

https://www.codingame.com/training/expert/tiling-by-squares

Created by @fantamar,validated by @LastRick,@CopperFr and @Meruem.
If you have any issues, feel free to ping them.

Hi there !
Iâ€™ve got a problem with this puzzle.
My algo passes all the tests but fails on validator 5.

I reply myself to my post : Iâ€™ve got now an algorithm which passes tests and validators and which is nevertheless still wrong.

The problem is much harder than I thought at the beginning.

Iâ€™ll fix my algorithm upâ€¦ someday ! Iâ€™ve got to rewrite it all.

Edit : here are some hard cases
11x12
15x16
16x17
17x19
18x19
23x25
25x27
â€¦

3 Likes

According to me it was easiest than I thought: no need for memoization, no Alphaâ€“beta pruning.
But it still difficult !
Just try to decompose the problem (if it is not already the case):
What if I have a square ? what if I Have a â€śsimpleâ€ť rectangle ? What shape do I obtain if Iâ€™ve
a rectangle and I cut a square in a corner ? Ho do I shrink this new shape, square by square ?
HTH

2 Likes

Hello, i donâ€™t even know how to beginâ€¦ Can someone give me an advice or just an idea please?

Well, i have done 72% and i donâ€™t know what goes wrong with external tests 6 & 7â€¦

2 Likes

Similar situation for me. All test cases passing, only validator 7 is failing. Not cool. How am I supposed to debug that?

Update: Iâ€™ve determined thru nefarious means that code times out. But that wasnâ€™t needed to confirm the test cases arenâ€™t set up very well for this puzzle.

Iâ€™ve used recursion + cache to speedup

Good thing that I didnâ€™t look at the puzzle difficulty when I started solving it.
If I knew itâ€™s Very Hard I would probably tried something too sophisticated and gave up.
But I assumed that itâ€™s Medium, so started with a simple greedy algorithm and then a bit improved it, so itâ€™s not greedy, but still runs fast enough: plain Python solution without numpy and lru_cache passes all tests.

This is very interesting. Iâ€™ve been looking for an applied mathematics approach for this problem instead of purely heuristics.
So far I am staring at OEIS A002962, Coming from squaring.netâ€™s Simple Imperfect Squared Squares (SISS).

Anyone here have some leads on how to translate it to code? This is my first time doing this kind of thing as everything Iâ€™ve done with puzzles are purely heuristics.

This is more hard than expert cause itâ€™s basically â€śgoro want chocolateâ€ť with more complicated cut but thatâ€™s it.
But anyway itâ€™s normal if you struggle on a hard puzzle.

Ideas that can help solving it:

• solve â€śgoro want chocolateâ€ť first, and practice recursion in general if youâ€™re not familiar with it
• instead of a function f(W, H) that gives the minimal number of squares to tile a rectangle `W*H`, write a function f(W, H, w, h) that solves it for the L-shaped polygon you get when you remove a `w*h` rectangle in a `W*H` rectangle. Then, youâ€™ll just call f(W, H, 0, 0) to solve the rectangle. It will allow easier recursive understanding of the problem.
6 Likes

This problem is not as simple as just being a dp. There seems to be more to it if you read online there are counterexamples to the dynamic programming solution.

Looking at the precomputed answers in the hard-coded solutions, the tests do not cover the most difficult cases over the problem domain (for which Iâ€™m sure my code would fail). At the same time, some of the more elegant solutions can cover a much wider range of inputs, presuming the assumptions made are correct. Does anyone know if itâ€™s true that there is always a minimum which deconstructs cleanly as L shapes?

For the validators of this puzzle you can assume a clean L shape deconstruction but it seems that it is not always true.
Your solution and tutubalinâ€™s starts diverging from the OEIS for h, w = 15, 23.
It returns 8 while itâ€™s supposed to return 9.
I couldnâ€™t compute all differences between your solution and OEIS for h in 1â€¦50 and w in hâ€¦50 cause itâ€™s a bit too slow, but I did for tutubalinâ€™s (sped up with cache) and it shows exactly 46 differences:

``````(h, w, expected, returned)
15 23 9 8
15 28 9 8
15 38 10 9
15 43 10 9
16 17 9 8
16 33 10 9
16 49 11 10
17 19 10 9
17 33 10 9
17 36 11 10
17 50 11 10
19 36 11 10
20 39 10 9
22 37 9 8
23 31 10 8
24 43 10 9
25 29 11 10
28 31 8 10
29 33 9 10
29 37 9 8
29 40 9 8
30 31 8 9
30 46 9 8
31 35 9 8
31 36 11 10
32 34 9 8
32 37 10 8
32 41 10 9
33 50 11 10
34 38 10 9
35 47 10 9
37 40 11 9
37 41 9 11
37 49 9 10
40 43 9 11
41 43 9 11
41 49 11 12
43 45 9 10
43 47 13 11
43 50 10 9
45 46 10 9
45 49 9 10
46 47 9 10
46 49 10 9
47 50 10 9
48 49 10 9
``````

The fact that most returned solution are smaller than expected is a bit weird, probably a bug somewhere.

So, in conclusion, yes the real problem seems much more complicated and is probably only reachable with some bruteforce (probably O(N^6) or something like that), but a good L-shape based DP will work here.
46 errors out of 1275 is not too bad but itâ€™s still a bit disappointing when you see that itâ€™s not a big improvement over the â€śgoro want chocolateâ€ť solution (which gives 94 errors out of 1275).

The OEIS definition confuses me a bit, or maybe Iâ€™m looking at the wrong one. My submitted solution deliberately caps at 8 in most cases as a dirty trick to avoid timeout, but removing this limitation does reveal that 15 x 23 and 15 x 28 are possible with just 8 squares.

1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 4 4 4 4 4
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 4 4 4 4 4
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 4 4 4 4 4
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 4 4 4 4 4
5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 4 4 4 4 4
5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8
5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8
5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8
5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8
5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8

1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6
7 7 7 7 7 8 8 8 8 8 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6
7 7 7 7 7 8 8 8 8 8 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6
7 7 7 7 7 8 8 8 8 8 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6
7 7 7 7 7 8 8 8 8 8 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6
7 7 7 7 7 8 8 8 8 8 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6

Yeah itâ€™s pretty weird, Iâ€™ll investigate further.
My own solution also returns 8 for those so maybe weâ€™re actually right after all ^^

But about the clean L deconstruction, Iâ€™m affraid there are a few cases where it doesnâ€™t work. It must be those were the returned output is higher than the expected one, like 28 31 for example (8 expected, 10 found).
Iâ€™ll try to find it by hand (or bruteforce) if I have time, the 8-tiling, if it does exist, has probably has a weird shape.

Edit:

Ok it looks like the hardcode from awnion that I used for comparison is NOT related to OEIS. So no surprises if there are differences. The hardcode from UncleV seems to give the same results as OEIS and compared to it, tutubalinâ€™s solution has only 16 differences:

``````(h, w, expected, returned)
25 27 10 11
27 31 10 11
28 31 8 10
29 33 9 10
30 31 8 9
33 50 9 10
34 35 8 9
37 41 9 11
37 49 9 10
40 43 9 11
41 43 9 11
41 48 9 11
41 49 9 12
43 45 9 10
45 49 9 10
46 47 9 10
``````

The expected solution is always lower than the returned one, which makes more sense.
I found a cool link to check OEIS solutions here and they are valid : http://int-e.eu/~bf3/squares/view.html#27,25

At first I thought that those would be impossible with L-shape deconstruction but after rethinking it I can find a good L shape deconstruction for all of them.

So final conclusion : L-shape method could possibly returns good result for ALL 1 <= w, h <= 50.

Iâ€™ll try to make it work and share my solution if it works.

1 Like

Ok I could manage to get it work with L-shaped polygons only by adding all kind of cuts I could think of.
It matches the OEIS for all 0 <= w, h <= 50.
It doesnâ€™t mean that there are no cases where L-shapes donâ€™t work for bigger integers but still itâ€™s pretty cool.
I shared the solution in Python if youâ€™re interested.

And to think I felt guilty about having to hack my code since it didnâ€™t run in time. At least it provided the right answers, sheesh! Too bad such an interesting problem wasnâ€™t more carefully researched.

Iâ€™m lowkey considering making a lookup table for this. Itâ€™ll be labor intensive, but at least itâ€™ll get past validator 7, which is the only thing my current solution fails on, and I suspect itâ€™s because of a timeout issue based on what Iâ€™m seeing other people here saying.

i have issu with test2 33x33

when i do => if (w == h) WriteLine("");