Expression Pattern Language (eXPL)

Introduction » eXPL Reference » Puzzles
Puzzles

Solving puzzles is a challenge developers tend to enjoy and provides points of comparison between different programming languages. Two puzzles are presented here to show eXPL dealing with challenges well known to the computing community: "Towers of Hanoi" and Sudoku.

Towers of Hanoi

Towers of Hanoi is often used as an example of recursion where a function calls itself one or more times to progress to a result. The puzzle consists of three rods and a number of disks of different sizes, which can slide onto any rod. The initial configuration is a stack of disks on one rod and the aim is to move the stack to the adjacent rod while keeping to the rules governing the placement of the disks:

  1. For each move, take the disk from the top of one of the stacks and place it on top of another stack.
  2. No disk may be placed on top of a smaller disk.

As the solution depends entirely on recursion, the eXPL program contains a single calculator called "tower_of_hanoi". This can be viewed in application TowersOfHanoi of tutorial15:

calc tower_of_hanoi
(
n, from_rod, to_rod, aux_rod,
? n == 1
{
system.print("Move disk 1 from rod ", from_rod,
  " to rod ", to_rod)
},
: n == 1,
<- tower_of_hanoi(disk=n - 1,
from=from_rod,
to=aux_rod, aux=to_rod),
system.print("Move disk ", n,
" from rod ", from_rod,
" to rod ", to_rod),
<- tower_of_hanoi(disk=n - 1,
from=aux_rod,
to=to_rod, aux=from_rod)
)(from_rod="A", to_rod="C", aux_rod="B");

Two aspects of interest with recursion are how to set initial parameters to start it off and and how to exit from the recursion. The first aspect is taken care of by using parameters. Three template parameters set the names of the rods:

(from_rod="A", to_rod="C", aux_rod="B")

The disk number is supplied as a query parameter so that there can be queries for a specific number of disks:

query towers_of_hanoi1(tower_of_hanoi)(n=1);
query towers_of_hanoi2(tower_of_hanoi)(n=2);
query towers_of_hanoi3(tower_of_hanoi)(n=3);

The initial parameters are paired to calculator variables by name, but this is not possible for the recursion parameters, so they are paired by position. For example, the first parameter, the disk number "n", is set in the recursion call to disk=n - 1, which works because it is the first parameter.

The second aspect of interest is the exit from the recursion and this is handled by a short cut expression which fires when the disk number gets to 1:

: n == 1

Sudoku

The next program is inspired by a Prolog Sudoku puzzle from Yevgeniy Brikman in his Six programming paradigms that will change how you think about coding". His sudoku solver uses the Prolog syntax to describe the puzzle and what constitutes a solution. He explains how to run the solver and the expected solution as follows:

| ?- sudoku([_, _, 2, 3,
_, _, _, _,
_, _, _, _,
3, 4, _, _],
Solution).

S = [4,1,2,3,2,3,4,1,1,2,3,4,3,4,1,2]

The program is concise but delegates the actual work of solving the puzzle to a "Fixed Domain" library, which includes a function to test if all members of a particular grouping are all different.

It would have been possible to come up with a similar library function for an eXPL sudoku solver, but it not appear to be the best approach given the procedural capabilities of the language. Instead, the eXPL solver implements an eXPL-only solution except for a print function. The solver is implemented in application Sudoku of tutorial15. This is the eXPL query and solution:

query sudoku(puzzle)
 (0, 0, 2, 3,
0, 0, 0, 0,
0, 0, 0, 0,
3, 4, 0, 0)
-> (encode_puzzle)
-> (row.eliminate)
-> (col.eliminate)
-> (row.eliminate)
-> (col.eliminate)
-> (square.eliminate)
-> (square.eliminate)
-> (decode_puzzle)
-> (print_puzzle);

4, 1, 2, 3,
2, 3, 4, 1,
1, 2, 3, 4,
3, 4, 1, 2

The query takes a set of 16 parameters as input. They are entered as literals here for convenience but other means to input the puzzle are possible. The query chain here is longer than seen in any other program, but it does succinctly indicate the strategy chosen to solve the puzzle. Numbers are encoded as bits (hex values): 0 = xF, 1 = x1, 2 = x2, 3 = x4 and 4 =x8. Thus the cells containing zeros are initially assigned all numbers and the aim is to use a process of elimination to reduce the number of bits in these cells to 1.

The elimination strategy requires working with groupings of 4 cells in one 3 patterns: "row", "column" and "square". When puzzle is solved, the cells are converted back to decimal numbers and printed out as a 4x4 table. The program is too long to present here, so this piece will conclude with some points of interest on the eXPL design.

Puzzle Matrix

The puzzle turned out easier to work with as a 4x4 matrix rather than a list of 16 integers. The matrix is implemented as an axiom list with 4 items each containing 4 terms. Here is the code which creates the matrix dynamically:

matrix += axiom { s11, s12, s13, s14 },
matrix += axiom { s21, s22, s23, s24 },
matrix += axiom { s31, s32, s33, s34 },
matrix += axiom { s41, s42, s43, s44 }

Note that this dynamically created axiom collection has a unique name for each term. This would not be allowed for a literal axiom collection.

Matrix Coordinates

The groupings are arranged as sets of matrix coordinates ie. each coordinate is a row, column pair. Here is the row groupings:

axiom path (row, col)
{ 0,0 }{ 0,1 }{ 0,2 }{ 0,3 }
{ 1,0 }{ 1,1 }{ 1,2 }{ 1,3 }
{ 2,0 }{ 2,1 }{ 2,2 }{ 2,3 }
{ 3,0 }{ 3,1 }{ 3,2 }{ 3,3 };
Context Cursor

Cursors are used to navigate the matrix and grouping lists row by row. The grouping cursor selects one of 3 lists by reference to the scope which is defined by the query chain eg. -> (row.eliminate):

calc eliminate
+ cursor group(path@scope);
Next: Resources ...