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