New to prolog, jumped in the deep end trying to solve this weird version of sudoku

#1

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 ff/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.

3 Likes
#2

Just wanted to say welcome. Nice job on getting your first Prolog program with constraints working on your own. That is not easy. :+1:

I would give you some feedback on this but constraints in Prolog are not a topic I have much experience.

2 Likes
#3

Could you explain again what the numbers outside the puzzle represent? If it’s a sudoku, then all the rows and columns will sum up to 45, so I can’t fathom what they represent.

1 Like
#4

Great job on this. Welcome to our little corner of computing!

my tutorial on constraints - might be useful.
http://www.pathwayslms.com/swipltuts/clpfd/clpfd.html

Yes- downside of clp(fd), guessing the option list can be a black art.

1 Like
#6

They represent the sum of all the numbers “physically” between 1 and 9 in the given row/column, rather than between 1 and 9 in value. So 123456789 = 35, 129345678 = 2, 123945678 = 5, etc.

I’ve explained the puzzle a few times now but still haven’t found an elegant way to express that, caught me out the first time I saw it too.

#7

Thanks Anne! I looked at that tutorial very early on in the process but I think it was a bit beyond me then, (this was before I’d even figured out what constraints really were but was trying to build them from scratch not knowing I was.) I might spend the day working through it today!

Also your twitter thread about approaches to learning prolog was where I started out and guided a lot of the reading I did in the month before I dived into this, so thanks for that too!

1 Like
#8

Welcome Tim, great work !

I tried myself to solve the puzzle, but I’m sorry I cannot help with your doubts :frowning:. I cannot say I really understand the technique you used in your solution…

:- module(sum_sudoku,
          [sum_sudoku/1
          ,puzzle_sample/2
          ,line_constraint_sum/2 % debugging...
          ]).

:- use_module(library(clpfd)).

puzzle_sample(1,
      [[ _, _, _, _, _, _, _, _, _, 4]
      ,[ _, _, _, _, _, _, _, _, _,33]
      ,[ _, _, 1, _, _, _, _, _, _,20]
      ,[ _, _, _, _, _, _, _, _, _,17]
      ,[ _, _, _, _, 5, _, _, _, _,26]
      ,[ _, _, _, _, _, _, _, _, _,10]
      ,[ _, _, _, _, _, _, 9, _, _,16]
      ,[ _, _, _, _, _, _, _, _, _,24]
      ,[ _, _, _, _, _, _, _, _, _, 0]
      ,[ 8, 4,17,35,14,13, 3,10,25   ]]).

puzzle_sample(solved_1,
      [[ 2, 3, 6, 9, 4, 1, 8, 7, 5,  4],
       [ 9, 5, 4, 3, 7, 8, 6, 1, 2, 33],
       [ 8, 7, 1, 6, 2, 5, 4, 3, 9, 20],
       [ 1, 8, 2, 4, 3, 9, 7, 5, 6, 17],
       [ 3, 9, 7, 8, 5, 6, 1, 2, 4, 26],
       [ 6, _, _, _, _, 7, 3, 9, 8, 10],
       [ 4, 1, 3, 5, 6, 2, 9, 8, 7, 16],
       [ 5, 6, 9, 7, _, 3, 2, 4, 1, 24],
       [ 7, 2, 8, 1, _, 4, 5, 6, 3,  0],
       [ 8, 4,17,35,14,13, 3,10,25    ]]).

sum_sudoku(Puzzle) :-
    separate_last(Puzzle, Rows, SCols),
    maplist(separate_last, Rows, Clean, SRows),

    AD = all_different, %all_distinct, 13 times (107/8.2) slower. Why ?
    maplist([Vs] >> (Vs ins 1..9), Clean),
    maplist(AD, Clean),

    blocks(Clean, Blocks),
    maplist(AD, Blocks),

    transpose(Clean, Transposed),
    maplist(AD, Transposed),

    maplist(line_constraint_sum, Clean, SRows),
    maplist(line_constraint_sum, Transposed, SCols).

separate_last([A,B,C,D,E,F,G,H,I,J], [A,B,C,D,E,F,G,H,I], J).

% verbatim from clpfd sample
blocks([A,B,C,D,E,F,G,H,I], Blocks) :-
    blocks(A,B,C,Block1), blocks(D,E,F,Block2), blocks(G,H,I,Block3),
    append([Block1, Block2, Block3], Blocks).

blocks([], [], [], []).
blocks([A,B,C|Bs1],[D,E,F|Bs2],[G,H,I|Bs3], [Block|Blocks]) :-
    Block = [A,B,C,D,E,F,G,H,I],
    blocks(Bs1, Bs2, Bs3, Blocks).

line_constraint_sum(L, S) :-
    seek_both(L, S).

seek_both([1|L], S) :-
    seek_v(9, L, 0, S).
seek_both([9|L], S) :-
    seek_v(1, L, 0, S).
seek_both([N|L], S) :-
    N #\= 1,
    N #\= 9,
    seek_both(L, S).

seek_v(V, [V|R], S, S) :-
    seek_end(R).
seek_v(V, [N|Ns], C, S) :-
    N #\= V,
    D #= N+C,
    seek_v(V, Ns, D, S).

seek_end([N|Ns]) :-
    N #\= 1,
    N #\= 9,
    seek_end(Ns).
seek_end([]).

Note the problem itself doesn’t require labeling, and the dead simple ‘automaton’ relating positions of 1 and 9 with the sum of elements between is straightforward…

Ciao, Carlo

1 Like
#9

Wow thanks for putting in that much effort Carlo! Your separate_last predicate is so simple, definitely better than my mess.

Also your handling of the sum constraint is way more elegant than my automaton monstrosity! I tried something similar early on but did it with append rather than recursively which led to pre-emptive grounding and a bunch of backtracking. (I didn’t understand grounding at the time, still only now figuring out the mechanics of how it’s handles working through Anne’s constraint tutorial.)

Yours also looks like it’ll work with nonground sums which I’ve been trying to do with mine since I posted this (sum/2 doesn’t like nonground sums so mine still won’t generate a puzzle from empty.) I’m going to play around with your solution for a few things I’ve wanted to try with mine!

Again thanks so much from this, I’ve learnt a fair bit just reading your solution. I really like how elegant prolog can be and I’m looking forward to understanding it well enough to write those elegant solutions myself rather than Frankensteining the first tools I come across to meet my ends haha.

#10

I am ashamed of almost any code I have written more than 6 months ago. I tell myself this means I am learning, but who knows. Carlo is a coding athlete if I have ever seen one, great that your problem managed to grab his attention.

1 Like
#11

You’re welcome !

Your code is indeed interesting and efficient. clp(fd) is not an easy beginner topic, again, great work !

As I commented in my snippet, clpfd:all_different instead of clpfd:all_distinct was the ‘trick’ - found by sweat, pain and debugging :slight_smile: - that allowed my code to be faster than yours.

Seems a bug in library(clpfd)…

Ciao

#12

Wow Boris, thanks.
I tought I never had meet a coding athlete.
Now i’ll see one when doing my morning duties :slight_smile:

1 Like