[Community Puzzle] Shikaku Solver

Puzzles
#1

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.

#2

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?

#3

@Regulus136 I fixed the stub, thanks.

1 Like
#4

Thanks @Niako

#5

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.)

#6

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
#7

@TBali I gave an alternative approach in PM to avoid spoiling here.

1 Like
#8

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
#9

Ok. This was ā€œHardā€. Was really intimidated too see this in medium.
But loved it . :smiley:

2 Likes
#10

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.

2 Likes
#11

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.

#12

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 :slight_smile:

#13

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.

#14

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.

#15

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ā€¦ :frowning:

#16

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
#17

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?

#18

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
#19

I told you what a valid rectangle is in my previous post :stuck_out_tongue:
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

#20

LOL, working solutions in 31 linesā€¦ Mine is a mere 622 :slight_smile:
But at least now I have a very generic class to help me cover exactly similar problems for the future (:slight_smile:). And also my matrix representation learned to dance. (:-))

2 Likes