News for hackers. Stuff that matters.
Re:An Intro to Integer Programming for Engineers: Simplified... by zmonx on Sunday May 21, 2017 @05:24PM (#14389329)
For example, here is a Prolog version that describes the task you mention via constraints on integers:

    solution(Ds) :-
            length(Ds, 9),
            Ds ins 0..9,
            foldl(segment_divisible(Ds), Ds, 1, _).

    segment_divisible(Ds, _, I0, I) :-
            I #= I0 + 1,
            length(Finals, I0),
            append(_, Finals, Ds),
            reverse(Finals, RFs),
            foldl(digits_number, RFs, 0-0, N-_),
            N #= I0*_.

    digits_number(D, I0-P0, I-P) :-
            I #= I0 + D*10^P0,
            P #= P0 + 1.

We can use it to generate solutions, for example:

    ?- solution(Ds), label(Ds).
    Ds = [0, 0, 0, 0, 0, 0, 0, 0, 0] ;
    Ds = [0, 0, 0, 0, 1, 2, 6, 0, 0] ;
    Ds = [0, 0, 0, 0, 1, 5, 1, 2, 0] ;
    Ds = [0, 0, 0, 0, 2, 7, 7, 2, 0] .

To exclude solutions where the leftmost digit is 0, we can simply impose an additional constraint on that digit. In addition, we are free to try different search strategies, completely decoupled from the constraints:

    ?- solution(Ds), Ds = [First|_], First #\= 0,
       reverse(Ds, Rs), label(Rs),
       portray_clause(Ds), false.
    [9, 0, 0, 0, 0, 0, 0, 0, 0].
    [8, 1, 0, 0, 0, 0, 0, 0, 0].
    [7, 2, 0, 0, 0, 0, 0, 0, 0].
    [6, 3, 0, 0, 0, 0, 0, 0, 0].
    [5, 4, 0, 0, 0, 0, 0, 0, 0].
    [4, 5, 0, 0, 0, 0, 0, 0, 0].
    etc.
Constraints allow us to easily describe and efficiently such tasks. Note that this is very different from naive exhaustive search: The constraint solver automatically prunes those branches of the search space that cannot lead to a solution.
Re:An Intro to Integer Programming for Engineers: Simplified... by JadeNB on Monday May 22, 2017 @08:26AM (#14392957)
Thanks! I forgot a constraint: we must use exactly the digits 1 through 9 (of course, each once). I assume that could easily be incorporated?
Re:An Intro to Integer Programming for Engineers: Simplified... by zmonx on Tuesday May 23, 2017 @07:24AM (#14400335)
Yes, this is easy to add, since there is a dedicated constraint called all_distinct/1 that we can use to express that a set of integers be pairwise distinct.

In this concrete case, we get this by simply adding all_distinct(Ds) to the query. For example:

    ?- solution(Ds),
       all_distinct(Ds),
       reverse(Ds, Rs),
       label(Rs).
This yields Ds = [6, 5, 4, 8, 7, 3, 1, 2, 0], in addition to other solutions. Now we only need to add that none of the integers must be 0. We can express this (for example) with the additional constraint Ds ins 1..9:

    ?- solution(Ds),
       Ds ins 1..9,
       all_distinct(Ds),
       reverse(Ds, Rs),
       label(Rs).
However, when you run this query, you get false in return. This means that there is no solution that satisfies all these constraints at the same time.

Therefore, the task you mentioned was probably about the prefices, i.e., the initial segments of the number. We can easily express this with small modifications to the program above:

    solution(Ds) :-
        length(Ds, 9),
        Ds ins 1..9,
        all_distinct(Ds),
        foldl(segment_divisible(Ds), Ds, 1, _).

    segment_divisible(Ds, _, I0, I) :-
        I #= I0 + 1,
        length(Prefix, I0),
        append(Prefix, _, Ds),
        reverse(Prefix, RPs),
        foldl(digits_number, RPs, 0-0, N-_),
        N #= I0*_.

    digits_number(D, I0-P0, I-P) :-
        I #= I0 + D*10^P0,
        P #= P0 + 1.

With this program, we get:

    ?- solution(Ds),
       label(Ds).
    Ds = [3, 8, 1, 6, 5, 4, 7, 2, 9] ;
    false.
This means that there is a solution, and it is in fact unique! This is determined very efficiently thanks to the pruning that is automatically applied by the constraint solver.
Re:An Intro to Integer Programming for Engineers: Simplified... by JadeNB on Friday May 26, 2017 @06:33AM (#14423083)
I'm sorry for the delay; I didn't realise that you'd responded. I couldn't find the O'Keefe book to look up the exact challenge, but I think you've correctly reverse-engineered and solved it. Thanks again!