Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @Timinator,validated by @Dr_Meyss,@Yudzhin and @5DN1L.
If you have any issues, feel free to ping them.
LOL, some search space pruning is still due on my part:
ide test #6 took 498 sec locally in php, with 467M total iterations in backtracking…
That would be still over 10sec if I rewrote the same in c++.
Time for another DLX???
My solution is in Python, so I’m hoping language choice isn’t a roadblock too often.
It seems as if nothing in life is ever truly free. I’m constantly trying to teach my daughter what my brother taught his kids so effectively: “Don’t buy what you don’t need.”
I am finally out of ideas for my Python solution. For anybody interested, my slowest time on any test is less than 2400 ms (inside the CG IDE). I’d love to hear what you are able to accomplish with other languages. Good luck!
1 Like
I think I’ve spend too much time on that one, really needed a lot of optimization compared to the original puzzle.
I am using PHP, my slowest time is for the test “40 Puzzles” which is logic (being the one with the more grid to find), inside the CG IDE I get something in the range 700-750 ms
If anyone is interested, for that test my code has to make 50.317 guesses when placing digits.
To reply to @TBali I am not using DLX
2 Likes
After sleeping on it and making a few changes I am now at ~ 300ms for the 40 Puzzles in CG IDE.
The numbers of guesses that have to be made have dropped to 17,038
Making just 17k guesses instead of my 467M seems like a clever approach 
But there is room for improvement even for you: it can be solved in 1 guess - if this guess is the right one…
2 Likes
Even if it was picking the right digit each times it has to make a guess it would still be making a lot more than 1 guess to solve the 40 puzzles 
1 Like
This might be sharing too much, but I make zero guesses in my super slow Python solution. I had hoped to make a puzzle where guessing would never be sufficient, but alas, today’s programming languages are just too fast!
1 Like
Improvements have been made.
It took me a while but I finally managed to solve everything without having to make a single guess, after @Timinator said it was possible I had to give it a try 
I ended at ~ 150 ms for the 40 Puzzles in CG IDE.
2 Likes
Hi,
I am trying really hard to make a DLX c# solution work. The only puzzle not fast enough is the 40 puzzles which needs to complete inside 2 seconds ? Can it be increased to 3 seconds or maybe someone can point me to a hint of how to make the DLX faster for Killer Sudoku.
Does this help?
Killer Sudoku Extreme Challenge
Bottom line - if you are timing out, you probably need more logic and less backtracking.
I finally got something working by using a constraint propagation phase before building and solving the exact cover model. This pre-processing step can deduce which numbers are possible for each cell, significantly reducing the number of potential actions (cage fillings) the main DLX solver needs to consider.
This made the breakthrough I needed.
1 Like