Challenge 0

Write a C++ program to solve a Sudoku puzzle. This contest will take place in two rounds so that entries for the first round may inspire entries for the second.

Challenge 0 is over. See the downloads and results below.

Rules

  1. The programs will be ranked by number of correct solutions, then by how much time the solutions took to produce. Generally you will want to submit a program that solves them with a 100% success rate.
  2. Your program will be submitted as a header file (.h) and a source file (.cpp) with matching names. The header file should declare a list of entry points to your submitted programs. All entry points should be enclosed within a single namespace that identitifies you (e.g. namespace Bob). This header file should only contain entry point declarations; do not include any class definitions, or declarations of helper functions. Round 2 submissions should use a different namespace than Round 1. If necessary for organization, you may submit a solution with multiple source files (but only one header), as long as they all begin with the same prefix.
  3. All program entry points will be functions of the form: void function( const char * problem, char * solution )
  4. You may submit as many programs as you like in your two source files, but please do not flood me with frivolous entries. If it's not interestingly different from another one of your entries, don't bother. Also, if an entry takes significantly longer to solve the problem set than the generator program took to generate it (i.e. more than 50x as long), please warn me ahead of time so that it doesn't stall the testing process. Extremely slow programs may be included out of interest, but should not be eligible for ranking.
  5. Please comment your code to explain what you did to optimize it, and why. Also, place an overall description of each entry in your header file, explaning its approach and what makes it unique from your other entries. Do not obfuscate your code. The entire submission will consist of one header and one source file. Do not submit commentary separately.
  6. The program should take the 81 character array (problem) and produce a solved 81 character array (solution). Do not attempt to read or write beyond the bounds of these arrays. The program must not cast away constness.
  7. The problem will contain values from 0 to 9. 0 indicates an empty space that must be filled by the solution. The numbers 1 to 9 indicate a fixed number that must be left unchanged in the solution. The solution array will be passed to your program filled with zeroes.
  8. The 81 character array is 9 consecutive rows of 9 numbers, forming a 9x9 grid. A correct solution will use each of the numbers 1 to 9 exactly once in every row, and in every column, and in each of 9 non-overlapping 3x3 blocks within the grid. Sudoku.
  9. A program very similar to the one that will be used for testing is provided below (0.zip). When tested, all given programs will be included and linked into this program (examine the source of main.cpp. The provided code includes a Visual Studio 2008 solution, but there is nothing unusual about the compilation process, should you wish to use a different compiler. Simply compile all included cpp files and link them together. On non-Windows platforms you will have to replace the use of windows.h's QueryPerformanceCounter with another suitable timer.
  10. The programs will be compiled and tested with the freely available Visual Studio 2008 Express. The compiler settings used will be the default ones. All programs will be compiled with the same settings. The testing will be done on a single-core Intel processor with 504MB of RAM.
    Gateway
    MX6214
    Intel(R) Celeron(R) M CPU
       420 @ 1.60GHz
    1.60GHz, 504 MB of RAM
    Physical Address Extension
  11. A program may not include any header other than its own, or the provided generator.h. No libraries (including the standard C++ libraries) are allowed. All code must be standard C++ and use no compiler-specific extensions (e.g. inline is allowed, but __forceinline is forbidden). C99 extensions like restrict are not allowed. Allowed keywords. In addition to this, the asm keyword is not allowed, nor are any other attempts to use machine code directly. The program must be plain, portable C++.
  12. Your program must free all memory it allocates. Static allocations are acceptable, but must be of reasonable size because this budget is shared by all entries. Do not attempt to read from or write to unusual memory locations, or do anything else that might result in different behaviour on different machines. Obviously, speed will vary between machines, but output should not.
  13. The program should not write to stdout, which will be needed exclusively by the testing apparatus.
  14. If you wish to break the rules within an #ifdef _DEBUG block so that these breaks are compiled out in the Release build, this is acceptable. This may be useful when debugging (e.g. if you wanted to use printf, or Generator::print).
  15. There are no prizes. All submitted source code will be published here after the contest is completed, along with the results. Submissions may be kept anonymous by request.
  16. Programs will be tested against a large number of randomly generated problems. Each problem is guaranteed to have a solution (which may not be unique), and will contain between 0 and 81 zeroes to be filled in the solution. The test will be run three times with a different ordering of the entries to be tested and different random seeds. Run times will be expected to vary based on the variation in problem set produced by different seeds. Full source for the test will be available with the results, which you can use to reproduce the test on your own machine. If you get significantly different results on your machine, please send me a report, and I will include it with the other results.
  17. Submissions for round 1 are due on or before May 19, 2009. Results, including all submitted source code, will be published May 21, 2009.
  18. Submissions for round 2 are due on or before June 16, 2009. Results, including all submitted source code, will be published June 18, 2009. Challengers who did not participate in round 1 may still participate in round 2.
  19. All submissions should be e-mailed directly to my e-mail address, provided at the bottom of this page.
  20. These rules may be incomplete, or incorrect. As long as we mutually understand the spirit of the challenge, this should not be a problem. However, because of this, rules are subject to change. I will notify all who have expressed interest if they do.
  21. I will review all submitted code for compliance with the rules. If there are any violations I will attempt to correct them myself, leaving a comment in the code, but I will also notify you. I will review code when it is submitted, so if you submit early and have violated the rules, you may have time to submit your own corrections.
  22. All submitted materials (except your name, if requested) will be made publically available here and are presumed to be entirely free of copyright. You will be free to take anything you learn here with you.
  23. Possible source of inspiration: Duff's Device
  24. Better source of inspiration: Paul Hsieh: Programming Optimization
  25. If submitting multiple solutions, these solutions may not cache or share any generated results.

Downloads

0.zip 5/09/2009 ZIP File 5kB
0_round_1.zip 5/21/2009 ZIP File 70kB
0_round_2.zip 6/19/2009 ZIP File 117kB

Examine main.cpp and the example.h/cpp to get the general idea of how the test application will be used. I recommend using a command line like "> result.txt" to redirect the console output to a text file.

Round 1

Submissions for round 1 were due on or before May 19, 2009. Results were generated May 21, 2009.

Entry100000 solutions30 solutions
solvedtime (seconds)solvedtime (seconds)
BetterThan10::SolveCheater11 100000 46.935150 30 0.000006
BetterThan10::SolveMangled 100000 49.968880 30 0.004151
BetterThan10::SolveCheater21 100000 50.410047 30 0.004097
BetterThan10::SolveOrdered 100000 64.846016 30 0.004999
BetterThan10::SolveSimple 100000 92.866624 30 0.010699
Brad::ice_climbers 100000 245.854292 30 0.067791
Brad::ice_drillers 100000 246.342760 30 0.068078
Brock::find_solution2 2215 70.427435 1 0.004141
Example::bad_answer 0 0.089961 0 0.000028
SteveW::EvolveSolution3 -- -- 0 54.226627

Contestants

If you were a participant and would like your name removed, a website or e-mail link added, or something else, let me know.

Round 2

Submissions for round 2 were due on 16, 2009. There were some delays, and the last submission was actually received on June 19, 2009. Results were generated June 19, 2009.

Entry100000 solutions
solvedtime (seconds)
Brock2::solve_less_stupid1 100000 15.620691
Brad2::fire_starters 100000 16.271799
SteveW::TotallyOriginalISwear 100000 30.7118324
YouCantTakeAwayMyRoundOneVictoryBrad::SolveMangled 100000 30.7276634
BetterThan10::SolveMangled2 100000 30.7312534
YouCantTakeAwayMyRoundOneVictoryBrad::SolveMonstrosity 100000 42.780226
YouCantTakeAwayMyRoundOneVictoryBrad::SolveAbberation 100000 49.816075
BetterThan10::SolveSimple2 100000 65.403870
Eno::bt_solver_track_used_int 100000 98.581301
Eno::bt_solver_track_used_restrict3 100000 99.168107
Eno::bt_solver_track_used 100000 100.077826
Brad2::fire_climbers 100000 135.708289
Brock2::solve_stupid1 100000 326.306110
Eno::naive_bt_solver 100000 460.729261
Example::bad_answer 0 0.089168

Contestants

If you were a participant and would like your name removed, a website or e-mail link added, or something else, let me know.


Return to my home page.
brad @ rainwarrior.ca
6/19/2009

Valid XHTML 1.0 Strict