Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @yoch,validated by @cedricdd,@Timinator and @Lanfeust.
If you have any issues, feel free to ping them.
Is this even solvable in c? i feel like execution delays are insanely restrictive is it just on that particular language? iāve tryed a lot optimizing tricks bit masking linkchaining and list checking paired with row/column/block counters to auto out singles and nothing seems to works, im runing out of ideas? all other ideas i have litteraly take to me to c# or c++ā¦
C is one of the fatest languages, and I can see that some people made it in python, so you definitively can make it in C. I didnāt make it so I canāt help you about ideas.
I solved it in Python with the mixed integer linear programming module from Scipy, so itās technically Cython not pure Python, but solved the worst case in less than 500ms. You can certainly do better in C. The other Python solutions here are using a very popular algorithm. If you search for sudoku solving algorithms youāll find it.
ātechnically Cā in Python means a benefit in time of about 10x versus really in C, since time limit for C in puzzles is about ten times lower than for Python, right?
1 Like
From my experiments, itās more like 20x, but the MILP approach is terribly inefficient. I used it because Iām practicing it, not to avoid the time limit. The pure Python solutions using better algorithms still finish well below the time limit.
Anyway, itās certainly possible to solve this in C because thereās one published solution here. Itās not easy, itās a Very Hard puzzle after all, but itās definitely possible.
1 Like
I am trying to pass this puzzle using Timinator and 5DN1Lās playground (in C++), and I am getting some timeouts.
After benchmarking a bit, the code is consistently slower on codingame by a factor of 3:
- Test1: ~60ms on computer vs ~180ms on ide. ā 626 cycles.
- Test2: ~80ms on computer vs ~240ms on ide. ā 1393 cycles.
- Test3: ~350ms on computer vs TIMEOUT on ide. ā 13899 cycles.
- Test4: ~380ms on computer vs TIMEOUT on ide. ā 18660 cycles.
- Test5: ~550ms on computer vs TIMEOUT on ide. ā 30315 cycles.
Timeouts make sense since from test 3 onwards multiplying by 3 gets me over the 1s barrier.
I compiled without flags (g++ file.cpp).
I donāt have any insight into these timing differences. Just to clarify, I have a couple of Algorithm X questions:
-
Have you already done the easier Sudoku puzzles with your C++ translation?
-
Are you breaking out of the search after Algorithm X finds the first solution.
I have a general comment that might help anybody trying to solve this puzzle. If you are running into timing issues, the least painful path might be to do some logical, problem-space reduction before doing any search with backtracking.
Algorithm X Playground Pg 60: Sudoku Challenge
Using the problem-space reduction techniques discussed on the website that I reference in the playground, I am able to reduce the size of the problem for Algorithm X and my slowest times are less than 30% of the Python time limit.
To solve this puzzle in Python without any problem-space reduction was painful for me. I had to play around with the DLX column ordering until I matched the authorās setup which I measured by the number of calls to solve(). This might not be a problem for a Python person because my solver now defaults to this order. In hindsight, I should have made a bigger deal out of this when I was reviewing the puzzle, but I didnāt. So, the bottom line is that column order can make a big difference on this puzzle for us Python folk and it might for you too if you are using Algorithm X.
3 Likes
C++ on CG is compiled in debug mode (= slow). Add #pragma gcc optimize ā-O3ā at the very top of yor code for release mode. I am unsure whether speed is really your issue. I have solved this one with Python without any of the optimisations suggested by Timinator
4 Likes
Thanks for your answers.
I solved the 16x16 version with an average solve time of 50ms.
Yes, as there is no yield equivalent in C++ (as far as I know), I return the first valid solution found.
Makes sense. I didnāt realize there were many more info regarding solving the sudokus on the playground, I will look into it. ^^
Do you know if they use some -fsanitize level of debug ?
Indeed using #pragma GCC optimize(āO3ā) speeds everything up, I only timeout on test5 with it. My goal will be to pass without it as it feels like a cheat code.
Currently I am leaking all over the place, I guess it doesnāt help my case.
1 Like
I managed to pass it in debug mode, with test 5 taking 225ms.
I doubt this will surprise anyone, but it was indeed a me problem.
For anyone following the AlgorithmX playground and coming in this thread, here are some steps I took to achieve this (still C++), going from ~550ms to ~100ms on my computer on test case 5:
- I put every attribute of the DLXCell class as public. At first I wanted to have a ācleanā class with private attributes, getters, and setters to handle them. But welp, going public brought me down to ~475 ms.
- I moved every DLXCell instances from the HEAP to the STACK. To be honest, I thought this was gonna be gamechanger but it was quite a let down with no big gain in execution time. At least I donāt have memory leaks anymoreā¦ I use a macro toggle to switch from heap to stack allocation and Iād say stack goes ~10ms faster.
- I got rid of the O set (list of optional requirements). I originally kept it in the code because I guess Iāll have to implement it anyway later in the playground. Turns out checking if an element is in a set hundreds of thousands of times takes time, even if the set is empty (who would have guessed). This got me to my current ~100ms.
There is still a lot of room for optimization, for now I see mainly:
- Storing the actions and requirements as ints/longs instead of tuples. For now I store them as a string, ie āplace value 0 0 4ā instead of {āplace valueā, row, col, value}, which does the same but with a lot less memory usage and slightly more parsing to do on the solution. I figure using 4(or 8) bytes with the 1st byte being a key to differentiate between several requirements and the rest adjusted to our needs will greatly reduce memory consumption.
- Using the problem-space reduction techniques discussed by Timinator above. I managed to mess it up when I implementing them, so for now I donāt use them. I get the same amount of reduction with āLone singlesā but with āHidden singlesā I somehow only deduce 5-10 more cellsā¦
2 Likes
I donāt see any Java solutions. Is it do-able in the time allotted for Java? Iām not interested in programming this whole solution only to find that even a very efficient algorithm doesnāt cut it because of the language speed and timeout.
cedricdd managed to solve it in PHP which language is definitely slower than Javaā¦
There are also many Python solutions. (Although in many cases python solutions get their speed by relying on using some fast 3rd party libraries written in C/C++.)
I donāt see many Python solutions or many python solutions relying on fast 3rd party librariesā¦?
Iād be shocked if CodinGame has a language that cannot solve 25x25 Sudoku within the time limit and without any use of 3rd party libraries. There are still more ways to fill in the grid logically that I havenāt yet explored which could make my times even faster. I say make it happen with Java!
My comment was not specific to this puzzle, I have no idea how the python solutions of this puzzle look like. The āfast 3rd party librariesā I was refering to are numpy, pandas and scipy, these are available in CG and can simplify or speed up the solution for some puzzles in CG.
1 Like
Just managed to solve it in Python without third party libraries like Numpy - but with help from @Timinator\s playground. Oops, at the 16x16 Sudoku discussion I promised I would not make another post referring to this, but I could not help myself. It is so cool to be able to solve puzzles that were earlier out of my reach.
1 Like
I couldnāt find any viable alternative that could handle the 25x25 Sudoku within time limits, so I went with the Dancing Links (DLX) algorithm and it worked smoothly in C#.
It builds the exact cover matrix with 4x625 constraints and explores valid placements using a recursive search with efficient cover/uncover operations.Execution time is super fast, even for the hardest grids.
1 Like
I just did it in Dart with DlxSolver inspired by @Timinator playground.
But the IDE 3rd test was not passing. I put it in a local env to have no time limit, and it seems it needs 17 seconds to complete while other are less than 2 seconds ! And I counted the number of backtracking, 3rd test need 337413 while 5th one only needs 26285.
So for other people, if you found only this 3rd test is not passing, try submitting anyway, chances are youāll have a 100% result 