brainwagon

I’m a bit of a puzzle fan. My wife and I do a daily gauntlet of puzzles, including Wordle, Quordle, Octordle, Stepdle, Worldle, and the New York Times Crossword Puzzles, both the mini and the regular one. It amounts to about an hour a day, with maybe a bit more on Saturday and Sunday, but it’s nice and relaxing, and as I get older the fact that my times for these still appear to be coming down, it lends somewhat of an antidote to the notion that you can’t teach an old dog new tricks.

I’m also rather fond of Sudoku, and am a fairly regular watcher of the YouTube channel “Cracking the Cryptic”, which I probably got more into during the COVID pandemic. I have since become a Patreon for the channel, which means that I can take part in the monthly Patreon Challenge, which is a series of custom designed puzzles just for Patreon members. This month’s challenge has a Hobbit theme, done by the talented setter Blobz, and consists of 19 puzzles that you must solve in order. It doesn’t hurt that my friend Jeff is also a Patreon member, so occasionally we get together via video conference and collaborate in solving puzzles, the hardest of which still usually takes us a couple of hours, even with our combined effort. But it’s good fun.

The puzzles in this sequence are ranked from one to four spider webs, with four spider webs being the most difficult. Puzzle #10, titled “Laketown” is the only one which was ranked with difficulty four, so we decided to get together this morning and collaborate on its solution. It was enormously pleasurable, and we finished in slightly less than two hours.

But before I embarked upon it, I wondered if it would have been faster to just implement a brute force solver in Python. I had the basis of a very simple program that solved sudoku that I did as part of Project Euler, a programming challenge/competition website that has hundreds of puzzles, much like the Advent of Code challenge I completed in December. Puzzle 96 was to write a Sudoku solver, and I still had the code. I solved it with a pretty rudimentary brute force solver with backtracking written in Python, consisting of 100 lines of very straightfoward Python. It was not exactly fast, taking several minute to grind through the 50 test cases that the puzzle presented, but I think it took me less than an hour to write (now several years ago), and it was pretty obvious how it works.

While I was waiting for our scheduled start time this morning, I wondered how difficult it would be to add the additional features it would need to solve this Laketown puzzles. In addition to the normal Sudoku rules, this had several “German Whisper” clues, where adjacent cells along green lines had to differ by at least 5, and several inequality clues, where certain cells had to be greater than the adjacent cells in specified directions. I didn’t bother making a general “compiler” for those, but just generated a single “legal” calls, which could be used to check if a particular digit in would be legal according to these constraints. This logic was not written in an efficient manner, and expanded the program to 225 lines. I set it running on the puzzle in my office just as Jeff pinged me to start our human effort.

The question I had: was the time I spent solving it by hand going to be less than the (estimated) ninety minutes it took me to implement the solver in Python? What would the runtime be?

After Jeff and I finished the puzzle in ~110 minutes, I went back to my desk. It had indeed solved the puzzle, but it did take 54 minutes. It appears that it searched a significant fraction of the entire search space

markv@victus:~/laketown$ time python puzzle.py
Lake Town
XXXXXXXXX [... answer deleted to preserve the puzzle for others ... ]
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX

real    54m29.229s
user    54m29.157s
sys     0m0.010s

So, it appears that the time spent implementing the program was slightly longer than the time it took for me and my friend to collaborate the find the human solution.

I suspect that were I to dedicate an afternoon to improving the efficiency of the search algorithm, I could speed this program up by at least two orders of magnitude, and maybe more, probably using Knuth’s Dancing Links ideas. I could probably make it less error prone and quicker to implement additional constraints.

But in any case, a fun Sunday. Hope you all are having a good New Year.