Hey Brian, I really enjoyed reading your work on the Pips game! I found myself applying a similar backtracking algorithm to my Pythonic solution (https://github.com/ematth/pips). I focused on finding a single solution for each puzzle as opposed to all possible solutions. For hard puzzles with longer run times, I found that running multiple processes, each with the domino list shuffled, gets the solve time down to <15 seconds.
brianberns•2h ago
Thanks! I'm glad to see I'm not the only one who went down this rabbit hole. :)
I considered parallelizing my solution as well, but the problem is that it only gives a linear speedup, while the problem space increases exponentially. I decided to focus on pruning the search tree instead, and that seemed to work pretty well (after much thinking).
ematth•2h ago
brianberns•2h ago
I considered parallelizing my solution as well, but the problem is that it only gives a linear speedup, while the problem space increases exponentially. I decided to focus on pruning the search tree instead, and that seemed to work pretty well (after much thinking).