This post will about a fun challenge of the r/dailyprogrammer subreddit. For those of you that don’t know about »r/dailyprogrammer«, go check it out! The community of this subreddit is exceptionally friendly, and provides interesting challenges for programmers of all levels, on a regular basis.
Surely everyone knows the »Sudoku puzzle« from the evening newspapers or elsewhere. The second ingredient of the challenge is knowing about »Knight’s tours« (Talking about the chess knight). A Knight’s tour is a sequence of consecutive knight moves, such that the knight visits each position on the board exactly once. Such Knight’s tours provably exist if certain conditions on are met, and the Sudoku’s board indeed meets them.
The author of the »dailyprogrammer’s challenge #361« playfully combined the games of chess and Sudoku in the following challenge:
Among all valid (filled-in) Sudokus and all valid Knight’s tours , define the scoring function:
where is the 81-digit number whose -th digit is the number written on the Sudoku square that the Knight visited after the -th move in his tour.
Find that makes as high possible.
Over the course of a week, multiple competitors were improving on the best score found thus far in a communal effort (and sharing the score). No one however managed to find a provably optimal score, so the efforts went more into (At least, I was under this impression) writing programs that, given some score, would find a better score. I wrote exactly this kind of program, and with a nontrivial amount of sheer luck, I managed to be the last one to improve a score. This earned me my first gold medal flair and concluded an unexpectedly fun experience!
There are still unfinished ties and ends in the challenge. Can you find the optimal solution? If you can, or have any other thoughts, don’t hesitate to »contribute«.
My program for the challenge is below: