Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @darkhorse64,validated by @5DN1L,@serialgg and @Zeffar.
If you have any issues, feel free to ping them.
1 Like
I have just added a more difficult test case to Constrained Latin Squares: some brute force implementations may now time out.
1 Like
By brute force, you mean trying all the permutations or you mean simple backtracking without tricks?
trying all the permutations. My solution is an optimized backtracking
My Python simple backtracking fails in the two last tests.
1 Like
5DN1L made it with Python
Yeah, Algorithm X again 
Glad I got in early with the dumbest possible solution
I bet you dare not resubmit
2 Likes
The basic backtracking indeed timeouts in Python but it’s still doable without DLX.
I tried several optimization ideas and eventually one idea ended up saving a lot of time (hint: it’s something that is also a good idea when you try to solve a grid manually).
I saw another solution with a more straightforward backtracking but with very clean bitmasks and it was enough to pass the validators, so there’s also this option.
2 Likes
It took me a good chunk of time this weekend, but I finally understand Algorithm X and I found a good Python implementation I was able to work with and make my own. I am passing all test cases except the last one. I am finding about 38,000 solutions before timing out. I need to get to just over 44,000 to pass the test case.
My guess is that there is some situation where I can recognize all future paths are going to be failures and I can cut bait and move forward with paths that have a chance of success. I just can’t figure out what that situation is…
Do you think there is any chance my Algorithm X implementation is too slow? I am not doing any dancing links. I found an implementation that was much more straightforward using dictionaries to keep track of which rows and columns have 1s in them. I tried it on the Sudoku Solver puzzle and it worked amazingly well. It does wonderfully on the first 8 test cases.
Maybe you could just add an extra 500ms to the time limit and help a brother out?
Sorry, I do not have control on the time allocated to solve the task. From this thread, I know others had success with Python, so keep on trying !
Those harder grids made it a very cool problem, but also, it’s definitely not a “medium” problem anymore! 
I guess it’s not possible to make it belong to the “hard” category? Or maybe even the “very-hard” one? (this was way harder than the “resistance” problem 
)
Too bad it currently is a “noobs trap”.
Yes, maybe “medium” is an understatement for “hard”. Although it’s not the only way, I suggest that you pay a look to Knuth’s dancing links. Implementing his algorithm is a real achievement by itself
sure! Some interesting solutions (note that I already solved it, tho 
)
Thanks so much for this puzzle.
This was my first introduction to algorithm X (I’m an experienced coder but it hasn’t come up), took a good couple of hours to wrap my head around it properly, but I’ve now got a new tool in the toolbox.
Good puzzle.
I’m continuing @Timinator playground on AlgorithmX with my own Dart implementation and I’m sad 
The last test (9x9 hard) is timed out between 15000 and 16000 solutions, but if I run it locally with a compiled version it is resolved in 500 ms (exact same code, run in my IDE)
So I guess this is really an issue with the Dart SDK in CodinGame.
What times have you recorded for the other test cases, both on CG (after all inputs have been read) and in your local IDE?
In the IDE, it is really quick
In CG,
example 01: Taken 23 ms
example 02: Taken 117 ms
example 03: Taken 26 ms
example 04: Taken 52 ms
example 05: Taken 1683 ms
example 06: Taken 2380 ms
example 07: Taken 54 ms
example 08: Taken 1785 ms
example 09: Timeout
I compared the time taken by my Python code and your Dart code (on CG) and observed the following:
-
Python is consistently faster, often by a large margin.
-
For smaller test cases (1, 3, 4, 7), Dart takes 14x to 130x as long.
-
As the test cases grow larger, the performance gap narrows to around 2x to 3x.
Your Dart code appears to run on average 15x the time taken in the IDE. Based on that ratio, the estimated time for Test 9 (which currently times out on CG) would be around 8700 ms, which clearly exceeds the allowed limit.
It’s also worth noting that CG’s time limit for Dart (~4 seconds) is shorter than that for Python (~6 seconds), making it even more challenging for Dart to complete the task in time.
Validator 9 should take less time than Test 9, but it’ll still require about double the time needed for Test 6, so I guess your code might not pass that validator either.
If you haven’t already, consider adding some preprocessing to identify obvious values for some empty cells. This can help reduce unnecessary exploration and improve performance.
If needed, we can also compare the number of iterations taken by the Algorithm X solver. A mismatch may indicate an underlying issue worth investigating.