4 ms·
For example, here is a Prolog version that describes the task you mention via constraints on integers: solution(Ds) :- length(Ds, 9),
by zmonx 9y ago
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.
- JadeNB 9y agoThanks! I forgot a constraint: we must use exactly the digits 1 through 9 (of course, each once). I assume that could easily be incorporated?
- zmonx 9y agoYes, 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.
- JadeNB 9y agoI'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!