https://www.codingame.com/training/medium/shikaku-solver
Send your feedback or ask for help here!
Created by @anon28400124,validated by @Niako,@Master_Zain and @JBM.
If you have any issues, feel free to ping them.
There is an issue with inputs for many languages (C#, Perl, Python, Scala, Swift, etc.). No problem with other languages (C++, java, kotlin, etc.).
Parameters W and H in validators should be split in 2 lines. Is it possible to change?
I have the āusualā problem here: I have a solution which passes the 10x10 test, but timeouts at larger grids. I donāt know if the puzzle creator thought of a much more clever algorithm, or it is just coding inefficiency. (I implemented backtracking.)
I looked at other posted solutions to see if anyone did something clever, but most are just copies of my original code. Kind of ironic, considering.
1 Like
What a pleasure it was to solve this puzzle! It was hard and time consuming but thatās definitely worth it.
Also Iāve learned a perfect algorithm for it! (Iām not sure if I its name is a spoiler here, I just say that it authorās name is Donald)
2 Likes
Ok. This was āHardā. Was really intimidated too see this in medium.
But loved it . 
2 Likes
Great puzzle, I enjoyed it, but itās yet another case of underestimated difficulty.
Unless you find a nice loophole, the puzzle requires you to identify all the options for each value, filter those options based on some criteria, combine them in valid scenarios with no overlap between each rectangle, sort those scenarios alphabetically then finally render the right one. And you better optimize your filters/scenarios because timeouts can easily be an issue.
ā> definitely NOT a medium puzzle, I would put it at the very least on hard. And the fact it only has a 30% success rate is a pretty big tell.
3 Likes
I was surprised by the difficulty ranking too because usually this kind of exact cover problem requires an implementation of Dancing Links to be efficient, which sounds more like very hard difficulty.
But actually a simple backtracking algorithm will work here (basically a DFS), as the grids are not that big.
So yeah, definitively not an average medium but not as hard at it could be.
A simple DFS will not work, thatās how I started but quickly changed path.
First reason is because you canāt conclude much if you get a collision of rectangles in your tests. Maybe the current rectangle is wrong and you should backtrack, but maybe the other one is wrong and yours is actually correct so you should not backtrack, or maybe both are wrong. Who knows.
Second reason is performance : the last test (30x30) produces 1.5e+54 possible scenarios if donāt trim them. Good luck with that 
Well I just reread my Python solution and itās really just a straightforward DFS.
47 lines total.
I made it public so itās easy to check.
I linearise the grid, which is usually a good idea for performance in this kind of pb, maybe the same solution doesnāt work without that.
I also do all tries in place and backtrack, if you create a new grid for each try it will also affect your performance.
1 Like
I see your solution in the list but itās greyed out, Iād have to provide my own solution in python first I think.
can anyone provide some direction how to think about the solution? I try to write some grids and numbers on the paper, if the question can be found the only answer, it will be easy, but the solutions may be multiple, it became harderā¦ and I totally have no idea how to handle these possibilitiesā¦ 
You can start by creating a list of all valid rectangles for each value separately. A valid rectangle for a value includes the value cell, has an area equal to the value and does not includes any other value cell.
The next step is to find the combinations that contain a valid rectangle for each value and donāt have any overlap, backtracking works for that (although you donāt want to test absolutely everything, you need to do some trimming).
1 Like
okayā¦ I will try it, but I have to ask about what is valid rectangleS?
for example, if there is a board like this(did not exam if correct):
0 0 0 4 0 0
0 6 0 0 0 0
0 0 0 0 0 0
0 0 0 0 9 0
step 1 is what it means valid is to check each value: 4,6,9, and find out each value can set which size of rectangle?
There is an interesting amount of variety in the solutions to this problem. Just looking at the published ones, the length of code is all over the place:
| Lines | |||
|---|---|---|---|
| Sols | Min | Ave | |
| Haskell | 2 | 31 | 32 |
| Python | 17 | 43 | 132 |
| PHP | 1 | 50 | |
| Ruby | 3 | 52 | 90 |
| JS | 5 | 59 | 120 |
| C++ | 6 | 101 | 137 |
| C# | 3 | 126 | 244 |
| C | 2 | 134 | 143 |
| Dart | 1 | 184 | |
| Go | 1 | 189 | |
| Kotlin | 1 | 229 | |
| Java | 3 | 236 | 308 |
| Rust | 1 | 402 |
2 Likes
I told you what a valid rectangle is in my previous post 
Taking the 4 from your example, you get the following options
0 0 0 4, 0 0 4 0 and 0 4 0 0 for the 1x4
0 4
0 0
and
4 0
0 0
for the 2x2
Edit: forgot the 4x1 option
4
0
0
0
LOL, working solutions in 31 linesā¦ Mine is a mere 622
But at least now I have a very generic class to help me cover exactly similar problems for the future (). And also my matrix representation learned to dance. (:-))
2 Likes