The MATLAB Sudoku Contest has come to an end. We hope you enjoyed it as much as we did. Thanks to all the participants and spectators who have helped make the contest a success, and congratulations to all our winners!
Tim is a second time Grand Prize winner having also won this title in the Ants Contest earlier this year. In the Sudoku contest, Tim has outdone himself again by picking up the Past the Post Record Prize as well. You can find out more about Tim from the Ants Winners Page. He is pictured here with his son, cyclist junior. :)
Unlike the Ants Contest, in which I was able to keep up with all the algorithmic developments, I lost touch with the Sudoku development relatively soon after Twilight was over. (My own feeble Darkness and Twilight entries were pathetic compared to the simulated annealing code that was developed by others.)
My winning the Past the Post prize was quite lucky, I think. At the time the prize was announced I was already exploring the impact of the various tweakable parameters that peppered the code. I knew that we were close enough to the "post" that trimming just a few repetitions or nudging to a slightly better local minimum of results would win it, so I just tweaked away.
Later in the contest, it was clear that we had a "magical" sequence of random numbers, as Niilo Sirola called it, so I focused on time optimizations. This is sometimes trickier in the era of JIT. I was constantly annoyed that the definition of the constant array:
>> col_selection = [[4 5 6 7 8 9];[7 8 9 7 8 9]];
appearing inside a loop, but moving it outside had virtually no impact on timing.
One of the improvements I found was that one of the random number calls could be vectorized, leading to the same sequence but just a little faster. I liked this one, because (unlike so much other tweaking) it was an example of something I would have done to speed up "real" code. The same was true of some of the slightly fluffy code inside "improver4". My third innovation in the CT series was to unroll the nested loops that optimized blocks without changing the rows, a tweak I would never do in real life.
Per is another veteran contestant, having the Golf Contest Grand Prize under his belt. Per is from Sweden and is enrolled as a Ph.D. student in the Control and Automation Laboratory at Chalmers University of Technology. You can read more about Per from his past winner's page profile.
Per promised to send us a photo of himself in his MATLAB jacket, however, we haven't received the photo yet. We'll have to make do with his old photo for now.
My strategy in MATLAB contests has always been to develop my own code rather than tweaking that of others. This means that I like to focus on the "darkness" and "twilight" phases.
As it happened, this year the contest started while I was working on a three-day take-home exam for a Ph.D. level course in linear algebra. While this reduced the time that I had available for coding, it was also quite helpful in making me realize that if the 1-norm is replaced by the 2-norm in the objective function, then the problem could be rewritten as a least squares problem, and Dark Magic employed to reduce the 27x81 "A" matrix to only 20x81.
Unfortunately I missed a transpose in the MATLAB SVD function, so the initial results were very bad. Finally I discarded all the Dark Magic, set MATLAB to "warning off", managed to get the least squares code somewhat operational, and won the Darkness phase probably more by luck than skill.
And I had a lot of fun while doing it!
-- Per Rutquist
Marko is our End of Twilight prize winner. He lives in Aachenm, Germany where he's currently a computer science student. He's recently finished his thesis at the Helmholtz-Institut in biomechanics with a focus on kinematic modeling of the upper extremities. Marko's other interests are classical piano and card games.
Marko was a focused player. Knowing that he had the best shot at winning a prize before the code was revealed, he implemented an optimization and annealing algorithm, since it had fewer parameters for tweaking. This strategy proved ideal.
Since I didn't want to spend too much time and effort on the contest (well, it still kept me occupied for almost two days), my first approach was implementing an optimization algorithm, since they are in their general form very easy to code and can get acceptable results. Since speed and quality were important issues, I chose a simulated annealing algorithm besides being easy to implement it has a few parameters for tweaking to get a good time-quality balance. I knew that when people started to understand the contest problem and put some intelligence into their algorithms, my approach would be beaten. So my goal was to win the twilight contest, which I did by a landslide.
After that I tried to combine a modification of Per Rutquist's algorithm and simulated annealing. I think his problem was that his solution produced lots of warnings (singular matrices), which, when displayed, used up a lot of time if warnings are not turned off (I believe the Mathworks server hasn't turned them off - correct me if I'm wrong). Despite handling those errors, his solution was actually very promising. After Twilight I had similar scores with the first place, but couldn't get a real breakthrough.
The rest of the time I had for the contest I actually spend reading those crazy things that Brian Welch and 'sudokist' were trying to do to hack the contest - I learned a lot, so be aware in the next contest! :-)
-- Marko Stefanovic
"I went with the alias of Guy Incognito only because I'm still not sure how to spell Joey JoJo Shabadoo."
It turns out that Tom is the mysterious Guy Incognito. Some of you might also remember him from our Furniture Moving Contest where he won the Day Break prize. Tom is from Cedar Rapids, IA.
My contribution to this contest was fairly small. I couldn't come up with a better algorithm but I did contribute by making the number of loops a function of the list size. I'm proud to see my single line stay in the code to the end. The collaborative coding this group produces amazes me. I couldn't compete with any of them if the contest never left Twilight. Any time I can improve the leading submission with original code rather than just tweaking, I either feel like I really accomplished something grand or I must have gotten away with something when no one was looking.
-- Tom Lemke
Niilo seems to have a knack for winning the Big Sunday Push prizes. You will reconize him from the Ants Contest and Furniture Moving contests. You can read more about him on his past contest winner's page. Niilo hails from Finland and is completing his Ph.D. in Applied Mathematics at the Tempere University of Technology.
Congratulations Niilo on winning again!
After daylight began, the leading entry quickly got to the shape where quick one-line tweaks didn't do the trick anymore, so it was time to try something major. It seemed like a good idea to try improving the result as well as time, so instead of the current leader I picked the entry with the best result so far, and slimmed it down to run in a minute instead of three (a Saturday well spent). The Big Sunday Push was announced about the time I finished coding, so I had to sit on the code until midnight (which was 7 A.M. local time). A swarm of entries with well-chosen parameter values swept the table clean.
As for the rest of the contest, it was a tweak there, a nip'n'tuck here, and I was quickly running out of even remotely humorous entry names. From the start it looked like there was potential for a fresh "large-scale" approach to the problem instead of the usual "small-scale" swapping and juggling (and those nice little finishing touches like replacing divisions by 9 with multiplications by 0.111111111111). Unfortunately, the collective effort advanced the leading algorithm much faster than I could advance my vectorized solver. Overall, another great competition, although I missed the visuality of the previous contests. (The hours I spent watching those ants go for it) ... :)
-- Niilo Sirola
Claus is from Finland and currently works for Telllabs, a telecommunication company. Though he does not use MATLAB at work, he uses it in his research on mixed integer nonlinear programming algorithms which he does in his spare time.
Thanks to Claus for contacting us with his contest story. We're glad to finally hear from him.
I personally liked to darkness and twilight phases the best and I am glad that they have been introduced in the contest. In the contest I was focusing on working on my own deterministic algorithm and occasionally tweaked around with the existing code to get a feel of where the code was going. I never got my own algorithm fast or efficient enough, but for the leap prize phase of the contest I noticed that SolverC did not correctly calculate the score changes when swapping two numbers. I changed the code to calculate the score correctly and that was enough to win the leap prize.
-- Claus Still