Search code examples
prologclpfd

Solving Euler 4 with CLP

I've got this very slow solution to Project Euler 4,

:- use_module(library(clpfd)).

euler_004(P) :-
  A in 1..9,
  B in 0..9,
  C in 0..9,
  P #= A * 100001 + B * 10010 + C * 1100,
  D in 100..999,
  E in 100..999,
  E #>= D,
  P #= D * E,
  labeling([max(P)], [P]).

Is there a way to speed it up?

Solution

  • Your original model takes 32.8s on my machine using SWI-Prolog. This version, using ff,bisect as search strategies, takes 3.1s:

    euler4c(P) :-
  A in 1..9,
  B in 0..9,
  C in 0..9,
  D in 100..999,
  E in 100..999,
  E #>= D,
  P #= D * E,
  P #= A * 100001 + B * 10010 + C * 1100,  
  labeling([max(P),ff,bisect], [P]). % 3.1s

    Also, SWI Prolog's CLP solver is generally not the fastest CLP solver, so other Prolog's might be faster.

    Also, see my non-CLP SWI Prolog approaches to this problem: http://hakank.org/swi_prolog/euler4.pl (solving the problem in about 0.2s).