Python now has also a 31 lines solution 
1 Like
irrelevant, off-topic fun-fact: this puzzle helped āto make the World a better place!ā 
ā¦ 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).
3 Likes
First, thanks for making the world a better place 
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 ?
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.
Whatās that?
An excellent source to understand it:
https://garethrees.org/2007/06/10/zendoku-generation/#section-4
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.
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)?
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
Thank you pardouin. Always getting good advice from you!
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 
Interesting but not medium level
can anyone provide the algorithm?
provide Shikaku Algorithm please?
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
No.
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
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.
1 Like