[Community Puzzle] Shikaku Solver

Puzzles
#21

Python now has also a 31 lines solution :innocent:

2 Likes
#22

irrelevant, off-topic fun-fact: this puzzle helped ā€œto make the World a better place!ā€ :wink:
ā€¦ what I mean: while solving this, I found a tiny bug in php 8 jit. Core team fixed this almost instantly and the bugfix now appeared in the latest php release (ref. bug #80861).

4 Likes
#23

First, thanks for making the world a better place :slight_smile:

I noticed that you use dlx, it feels a bit overkill to me here.
I know the principle of algorithm X but never had to implement it, everytime a backtracking timeouts for a puzzle and I start thinking ā€œthis is it, letā€™s dlx itā€, I always find another option at the last moment ^^

Do you have an example of puzzle where dlx is really mandatory ?

#24

So far, this was the first and only puzzle where I used DLX.
First I tried this also with backtracking but timeouted, no matter how I tried to improve the reject() part.
Probably wouldnā€™t have needed it, if I havenā€™t used the slowest language available.
But in the end I was happy to implement this algorithm and the underlying data structure for the learning aspect, even if it was an overkill.

#25

Whatā€™s that?

#26

image

or this one?
:slight_smile:

#27

An excellent source to understand it:

https://garethrees.org/2007/06/10/zendoku-generation/#section-4

#28

I tried to make this one require DLX with test cases up to 60x60, but at that time the input size was limited to 1000 characters IIRC.

#29

A couple of comments mention that the puzzle can be solved in 31 lines of code. I was wondering how to count lines of code. For instance, the default C# code stripped of blank and comment lines has 25 lines. I assume that no one has solved the puzzle in C# with just 6 additional lines of code (unless one juxtaposes multiple statements next to each other on the same line).
So, what exactly counts as a line of code?
For instance, does a stand-alone opening brace count as a line of code?
Though I realize that the way to count is dependent on the programming language, with some being more verbose than others. Python doesnā€™t have opening and closing braces, or ENDIFs, etc., so it saves quite a bit right there.
Maybe we want to count the number of statements or expressions so to level the playing field somewhat (though functional languages might still easily win, all other things held equal)?

#30

Donā€™t pay much attention to this ā€œlines of codeā€ thing, especially with C#.
But yeah if you want to have an idea of your line count, basically ignore lines with only curly brackets, and donā€™t stack instructions with semicolons.
If thereā€™s only one instruction in a block, itā€™s ok to not line break (typically in an if block).

1 Like
#31

Thank you pardouin. Always getting good advice from you!

#32

I do not have the basics of algorithms and I am a beginner in python I struggled to do this puzzle.
I had to make an algorithm out of my head :stuck_out_tongue:
Interesting but not medium level

#33

can anyone provide the algorithm?

#34

provide Shikaku Algorithm please?

#35

Thatā€™s not how this website works at all, youā€™re supposed to find the solution by yourself.
If you cannot do it, maybe try an easier one, the sudoku for example.
Both can be done with a backtracking algorithm, which require a good understanding of recursion.
So basically the learning path:

  • learn recursion,
  • use recursion to write a bruteforce algorithm, for example an algorithm that generates all words of length n with a given alphabet,
  • learn what backtracking is, if you did the previous algorithm itā€™ll be easier to understand,
  • try to solve sudoku with backtracking,
  • write a shikaku solver that at least works on you IDE (even if itā€™s too slow for CG),
  • optimize your algorithm to make it faster.
    Good luck!
2 Likes
#36

No. :stuck_out_tongue:

#37

Hi,

My solution is working for all the test cases but is failing for the validator 05 (30x30)
I managed to get the time of the last test case which is also a 30x30 grid from ~2s to ~0.04s (in PHP) so Iā€™m assuming the validator is not failing because of a timeout.
Iā€™ve double/triple checked my code and canā€™t find where the issue could be coming from, is there any way to get access (in PM) to the inputs/result of the last validator, I donā€™t know how to debug it otherwise.

Thanks

1 Like
#38

Was able to fix thanks to Westicles :grinning:

#39

Loved this puzzle.
I went from brute force taking minutes to solve the final test case, to benching ~2ms to find all solutions to it, and Iā€™m pretty sure I could still optimise it further.
Thank you for making this one.

2 Likes