Hey guys! Brand new to prolog. I’ve been reading about it for months and finally came across a good problem to put it to the test. I’m a linguistics student and don’t run in many programming circles particularly not logic programming circles so I’d love to talk about what I learned maybe get some feedback. It’s my first bit of practical prolog.
I’d read most of the sudoku examples in my past few months of reading and research then came across this weird sudoku puzzle (I can’t find or remember the origin, I’ve tried). It basically gives you the sum of all the numbers that occur between 1 and 9 in any given column or row, and only 3 number clues to start with, this is the puzzle grid:
[ [_,_,_,_,_,_,_,_,_,4] , [_,_,_,_,_,_,_,_,_,33] , [_,_,1,_,_,_,_,_,_,20] , [_,_,_,_,_,_,_,_,_,17] , [_,_,_,_,5,_,_,_,_,26] , [_,_,_,_,_,_,_,_,_,10] , [_,_,_,_,_,_,9,_,_,16] , [_,_,_,_,_,_,_,_,_,24] , [_,_,_,_,_,_,_,_,_,0] , [8,4,17,35,14,13,3,10,25,0] ],
The last row/column is the sum. (The last entry in the last row is useless, it’s only there because it was easier with a square.)
I’m working on a blog post explaining my journey over the past few weeks from not knowing anything at all, not even how constraints worked (I didn’t even know about
dif/2.) To building a solver that used automatons to handle every permutation of the sums at once without backtracking to try different constraints like early solutions attempted to (I think they were logically sound but they blew out the stack every time.) So hopefully that’ll be up soon, (I’ve got to make a blog first, I started writing as a way of rubber duckying because I don’t like talking out loud.) In the mean time (and maybe to learn more before I post) I wanted to talk to actual humans about it a bit.
Anyway, here’s the solution I wound up with, I’d love some feedback. It’s pretty simple in the scheme of things, especially with how crazy it seems you can get with automatons using
automaton/8. But I’m pretty proud of it and wanted to share it somewhere people would know what I was talking about. It runs way better than I ever expected it would when I spent the first week blowing out the stack. All in all I think I started about 3 weeks ago knowing next to nothing and have spent maybe 8-10 hours coding and digging tracing with SWISH to learn how everything actually works. Plus hours of reading tutorials and the manual on the tram and at lunch when I finally grok something and need to read more.
Here’s what I came up with. The naming of the agar predicates is a little weird, the metaphor helped me grok what I was trying to do. determining what’s between 1 and 9 is sort of like a 1 dimensional cell on an agar plate where 1 and 9 are the membranes. The “tissue” has to sum to the sum and everything else has to be outside in the “substrate”. It was generalisable and to avoid over-stacking constraints I kept it as general as possible. (It could be more-so still.) hyper_plate… just helps take and flatten every possible permutation of numbers that sum to sum and their matching out-set for a given row/column into one big graph that can be pattern matched in a single automaton.
Shout out to the folks over at StackOverflow who helped me when I didn’t even know how to extract a sublist, I didn’t wind up using that because it led to lots of backtracking because splitting at defined numbers ruins constraints. (I think I could probably successfully achieve my original tactic now with recursion and clp(fd) reflection predicates and being more explicit with the logic of constraint application, which I’m going to try in the future because I feel like there’s a performance gain to be had.)
Speaking of performance here’s how it runs on my laptop:
?- Puzzle = [ [_,_,_,_,_,_,_,_,_,4] , [_,_,_,_,_,_,_,_,_,33] , [_,_,1,_,_,_,_,_,_,20] , [_,_,_,_,_,_,_,_,_,17] , [_,_,_,_,5,_,_,_,_,26] , [_,_,_,_,_,_,_,_,_,10] , [_,_,_,_,_,_,9,_,_,16] , [_,_,_,_,_,_,_,_,_,24] , [_,_,_,_,_,_,_,_,_,0] , [8,4,17,35,14,13,3,10,25,0] ], flatten(Puzzle, Cells), time(sum_sudoku(Puzzle)), time(labeling([ffc], Cells)). % 4,266,509 inferences, 0.397 CPU in 0.400 seconds (99% CPU, 10759259 Lips) % 93,028,521 inferences, 8.100 CPU in 8.143 seconds (99% CPU, 11484898 Lips) Puzzle = [[2, 3, 6, 9, 4, 1, 8, 7|...], [9, 5, 4, 3, 7, 8, 6|...], [8, 7, 1, 6, 2, 5|...], [1, 8, 2, 4, 3|...], [3, 9, 7, 8|...], [6, 4, 5|...], [4, 1|...], [5|...], [...|...]|...], Cells = [2, 3, 6, 9, 4, 1, 8, 7, 5|...]
I’m almost certain there’s better ways to do a lot of what I’ve done (the mess at the start of
sum_sudoku to crop the sums from the sudoku and the reverse in
sum_between_1_and_9 (I should have just moved the sums to the opposite sides,
[Head|Rest] just seems to play nice with constraints in ways
append doesn’t.) And that there’s probably built ins somewhere for other stuff ( like
not_ins, for some reason
#\ Item in Dom works but
#\ Items ins Dom doesn’t?) If anyone can shed some light on any of that I’d greatly appreciate it! Also I wonder why most sudoku examples use
label(Cells) rather than
labeling([ffc], Cells), the performance improvement from
ffc is pretty significant even for regular sudoku, and it’s much closer to how a human solves them.
TL;DR: Sorry for the really really long post, I’ve been working on this alone for 3 or 4 weeks now and I’ve had a lot of thoughts and gotten really excited about prolog but had no one to talk to.