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	2009-5-9	ZIP File 5kB
	0_round_1.zip	2009-5-21	ZIP File 70kB
	0_round_2.zip	2009-6-19	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.

• 1. BetterThan10::SolveCheater1/2 have interchangeable results depending on which entry executes first. These will not be allowed in round 2 because they cache results to be reused by the other entry.
• 2. Brock::find_solution includes several headers and makes use of library functions.
• 3. SteveW::EvolveSolution was considered too slow to participate in the 100000 solution test.

Contestants

• Dan Rubalcaba: BetterThan10.
• Brad Smith: Brad, Example.
• Brock Heinz: Brock.
• Steve Weatherly: SteveW.

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.

• 1. Brock2::solve_stupid and Brock2::solve_less_stupid have been edited to comply with the rules (use of windows.h removed). These edits made no noticeable difference in performance.
• 2. BetterThan10::SolveMangled was the round 1 winner, included for comparison. BetterThan10::SolveSimple is included for comparison with Brad2::fire_climbers, which is similar.
• 3. Eno::bt_solver_track_used_restrict breaks the rules by using the restrict keyword. It is included only for comparison.
• 4. The timings for SteveW::TotallyOriginalISwear, YouCantTakeAwayMyRoundOneVictoryBrad::SolveMangled, and BetterThan10::SolveMangled were very close and in repeated tests had no consistent ranked order.

Contestants

• Brock Heinz: Brock2.
• Brad Smith: Brad2, Example.
• Dan Rubalcaba: YouCantTakeAwayMyRoundOneVictoryBrad, BetterThan10.
• Steve Weatherly: SteveW.
• eno: Eno.

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

brad rainwarrior.ca
2009-6-19