Template-Axiom-Query (TAQ)

CybeResearch Home » TAQ 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 TAQ 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.

The puzzle is solved for a 1, 2 and 3 disks in towers-of-hanoi.taq. As the solution depends entirely on recursion, the program contains a single flow called "tower_of_hanoi".

flow tower_of_hanoi
(
n, from_rod, to_rod, aux_rod,
?? (n == 1)
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),
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 flow 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 converse criterion 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, using Prolog, has the following query and solution

| ?- 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 depends on a library function which tests if all members of a particular grouping are all different.

The TAQ puzzle is set out as 16 numbers arranged in 4x4 matrix, with blank entries represented by zero:

0, 0, 2, 3,
0, 0, 0, 0,
0, 0, 0, 0,
3, 4, 0, 0

The solution is a printout of an actual 4x4 matrix:

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

sudoku.taq solves the puzzle entirely in TAQ. A 10-stage query chain provides a high-level summary of the steps taken

query sudoku(puzzle)(...)
-> (encode_puzzle)
-> (row.eliminate)
-> (col.eliminate)
-> (row.eliminate)
-> (col.eliminate)
-> (square.eliminate)
-> (square.eliminate)
-> (decode_puzzle)
-> (print_puzzle)

The puzzle numbers are encoded as bits (hex values): 0 = 0xF, 1 = 1, 2 = 2, 3 = 4 and 4 = 8. The cells containing zeros are initially assigned all numbers, and by a process of elimination, reduced to having only a single bit.

This strategy proceeds with groupings of 4 cells in one of 3 patterns: "row", "column" and "square". Each pattern is placed in a scope so the "eliminate" flow can navigate the puzzle using a context list.

When puzzle is solved, the cells are converted back to decimal numbers and printed out as a 4x4 table.

Next: Entities and Axioms ...