Here are two problems from Project Euler which I thought can be solved elegantly in Oz using constraint programming. Instead of naively iterating over numbers, Oz lets us define a finite domain in which a solution exists, set some constraints and then propagates and distributes those constraints to arrive at the solution.

Project Euler Problem 9

The problem definition is as follows: A Pythagorean triplet is a set of three natural numbers, [latex]a b c[/latex], for which, [latex]a^2 + b^2 = c^2[/latex] For example, [latex]3^2 + 4^2 = 9 + 16 = 25 = 5^2[/latex]. There exists exactly one Pythagorean triplet for which [latex]a + b + c = 1000[/latex]. Find the product [latex]abc[/latex].

Solution

%% ============================================================
%% Find X, Y, Z such that X^2 + Y^2 = Z^2 and X + Y + Z == 1000
%% ============================================================
local
   proc {Py Numbers}
      X Y Z
   in
      Numbers = sol(x:X y:Y z:Z)
      Numbers ::: 1#1000

      {FD.distinct Numbers}
      {FD.sum [X Y Z] '=:' 1000}
      {FD.times X X} + {FD.times Y Y} =: {FD.times Z Z}
      {FD.distribute ff Numbers}
   end
in
   {ExploreOne Py}
end
Here's the search tree for this implementation. We evaluated just 200 combinations of X, Y and Z before arriving at the solution. Finally the triplet that solves the given constraints: The three numbers that solve the constraints are 200, 375, 425. Obviously, 200 + 375 + 425 = 1000. So, their product is 31875000 which is the answer to the problem.

Project Euler Problem 30

Problem 30 is only slightly harder: Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits: [latex] 1634 = 1^4 + 6^4 + 3^4 + 4^4 8208 = 8^4 + 2^4 + 0^4 + 8^4 9474 = 9^4 + 4^4 + 7^4 + 4^4 [/latex] As [latex]1 = 1^4[/latex] is not a sum it is not included. The sum of these numbers is [latex]1634 + 8208 + 9474 = 19316[/latex]. Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Solution

local
   proc {FifthPowers Numbers}
      A B C D E F
   in
      Numbers = sol(a:A b:B c:C d:D e:E f:F)
      Numbers ::: 0#9

      A + B + C + D + E + F >: 1
      A*100000 + B*10000 + C*1000 + D*100 + E*10 + F =:
      {FD.power A 5} + {FD.power B 5} + {FD.power C 5} + {FD.power D 5} + {FD.power E 5} + {FD.power F 5}

      {FD.distribute ff Numbers}
   end
in
   % {ExploreAll FifthPowers}
   {Browse {SearchAll FifthPowers}}
end
Oz Explorer shows all possible numbers matching the requirements. The numbers which can be represented as the sum of fifth powers of their digits are 4150, 4151, 54748, 92727, 93084 and 194979. Their sum is 443839.