See some of the other benchmark datasets in the Tdoku project for puzzles that are actually hard.Īlso note that while Tdoku is the fastest solver I'm aware of for hard puzzles, it's not the fastest for 17 clue puzzles. Actually they're among the easiest, with the majority requiring no backtracking at all. But note, contrary to the problem statement, that 17 clue puzzles are far from the hardest Sudoku. Tdoku has been optimized for hard Sudoku instances. ~/tdoku$ # adjust output format and sha256sum: ~/tdoku$ clang -o solve example/solve.c build/libtdoku.a Model name: Intel(R) Core(TM) i7-4930K CPU 3.40GHz Using Tdoku ( code design benchmarks) gives these results: If you have any questions, feel free to ask, and I'll try to clarify any misunderstandings. If you want another test set to check your solution, here are 10000 easier Sudokus. This does not apply to installed libraries and packages, which are allowed. You are not allowed to use any external resources or web requests during the runtime of your program. This rule is to ensure that measurements are more precise, and have less variance. You are allowed to use a random number generator, but the seed of the generator should be fixed. You are not allowed to have a non-deterministic program. However, it is entirely fine if your solution is slow for easier puzzles. Your algorithm should be applicable on any set of Sudoku puzzles, both easy and harder Sudokus. You are in no way allowed to hard-code solutions. However, the file will also be manually inspected, so don't try to get a hash collision. Your script should be able to generate a file containing all puzzles and their solutions. Your solution will be verified by a MD5/SHA256 checksum. However, this will not be an official scoring, and is just for fun. If time is available, I'll try to benchmark the solutions presented here against the harder puzzle set, and add the score to each submission. For an optimized solver, this should not be an issue.ĮDIT: It was brought to my attention that while difficult, the problem set at hand is not the most difficult there is. In those cases, you are responsible for reporting the machine on which it ran, and your score. If your solution takes longer than an hour to run, it will not be officially scored. If the average scores differ by less than 2%, I will consider it a draw. If two solutions have similar scores for individual runs, I will run multiple benchmarks, and the average time will be the final score. Any thoughts on the scoring system are appreciated. This doesn't interfere with any existing solution, and doesn't change the rankings as they stand now. Your program should produce the output file with the correct hash even during official scoring. Timing / scoringįrom discussions in the comments, and some reflection, the scoring criteria has been changed to be the time of your entire program. Please include an instruction for how your program takes input. Your program should be able to take the filename as an argument, or have the file input from STDIN, to facilitate manual checking of your solution. The unknown cells are 0, and the known cells are 1-9. The first line of the file is the number of puzzles, and every line after that is 81 characters long and represents a puzzle. Here's the uname output, for anyone interested. The benchmark will be run on a Dell XPS 9560, 2.8GHz Intel Core i7-7700HQ (3.8GHz boost) 4 cores, 8 threads, 16GB RAM. If I don't have a compiler installed for your language, you should be able to provide a set of command line instructions needed to install an environment where your script can be run on Linux. However, you won't just be solving any old Sudoku, you'll be solving the very hardest Sudoku puzzles in existence, the 17-clue Sudokus. The goal of this challenge is simple, you should solve a set of Sudoku puzzles as fast as possible. A very important aspect of a Sudoku puzzle is that there should only be one valid solution. The goal of a game of Sudoku is to fill the board with the numbers 1-9, one in each cell, in such a way that each row, column and box only contains each number once. For anyone still working on their solvers, I'll still benchmark new submissions when I have time. It seems as if we have a winner! Unless anyone plans on contesting the world's current fastest Sudoku solver, user 53x15 wins with the staggeringly fast solver Tdoku.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |