Home More Samples
```
///////////////////////////////////////////////////////////////////////////////
// Paving the way
///////////////////////////////////////////////////////////////////////////////
// Enigma 1468 Bob Walker, New Scientist magazine, November 10, 2007.
///////////////////////////////////////////////////////////////////////////////
//
// This is the view of the 36 flagstones of Joe's patio.
// +---+---+---+---+---+---+
// |   |   |   |   |   |   |
// +---+---+---+---+---+---+
// |   |   | ^ |   | 1 |   |
// +---+---+---+---+---+---+
// |   |   |   | v |   |   |
// +---+---+---+---+---+---+
// | E | N | I | G | M | A |
// +---+---+---+---+---+---+
// |   |   | v |   |   | < |
// +---+---+---+---+---+---+
// |   |   |   |   |   |   |
// +---+---+---+---+---+---+
//
// Joe has numbered them, so that starting on flagstone 1 (shown in the image)
// and stepping from one flagstone (not diagonally) to an adjacent one in
// order, one will finish back on flagstone 1 after stepping on all the other 35.
// The arrows [^=up, v=down, <=left] indicate in which direction to step from
// certain flagstones .
//
// What are the numbers of the flagstones E, N, I, G, M and A?
//
///////////////////////////////////////////////////////////////////////////////
//
// Given the source code below, find all solutions by running the query:
//
//      all PavingTheWay()
//
///////////////////////////////////////////////////////////////////////////////
//
// Result:
//
// 15 20 21 24 33 34
// ___ Solution: 1 ___ [00:00:00] __ [Backtracks: 552521] ____
//
// Number of solutions: 1   Number of backtracks: 2072979
// Elapsed time: 00:00:00
//
///////////////////////////////////////////////////////////////////////////////

local Patio = [0..5]->[0..5]->I  // 6x6 array of integers

pred PavingTheWay() iff
// Keep track of the tile in double array "pos". Array element
// value 0 means the tile has not been stepped upon yet, otherwise
// the tile value corresponds to the step number.
//
// Intialize all array "pos" elements as 0 (not stepped on yet)
pos:.Patio & Dupl(6,Dupl(6,0),pos) &

// Start at the first place, step 1
pos (1,4) := 1 &

//Calculate the rest of the steps...
PavePatio(pos,1,4,1) &

// The last step taken (step 36) must be next to the first one...
// (There are four possible last steps)
(pos(0,4) = 36 | pos(1,3) = 36 | pos(1,5) = 36 | pos(2,4) = 36) &

// Print the solution (the row containing E N I G M A)
PrintOneRow(pos(3),0)

///////////////////////////////////////////////////////////////////////////////
// Starting at the current position, make (recursively) the next step, until
// we made all 36 steps neccessary to cover 36 tiles.
pred PavePatio(pos:.Patio,current_row:<I,current_col:<I,current_step:<I)  iff
if current_step < 36 then          // there are 36 steps possible
NextStep(current_row,current_col,newrow,newcol) &
// If the position is not visited yet, we'll assign the step number to it.
// (Otherwise the test for position = 0 fails and forces a backtrack)
// If the newcol, newrow are outside of the patio, we'll get a backtrack as well.
pos(newrow,newcol) = 0 &
// If we got here, then the newcol,newrow are on the patio and were never visited.
// So we mark the place as visited, the new place becomes the current place
// and continue recursively with the next step
pos(newrow,newcol) := current_step+1 &
PavePatio(pos,newrow,newcol,current_step+1)
end

///////////////////////////////////////////////////////////////////////////////
//  Given a tile at position row,col, generate the next possible step
local pred NextStep(row:<I,col:<I,newrow:>I,newcol:>I) iff
// Check if the current position is one the four compulsory steps position.
// If it is, move accordingly
if row = 1 & col = 2 then
newrow = row-1 & newcol = col   // move "up"
elsif (row = 2 & col = 3) | (row = 4 & col = 2) then
newrow = row+1 & newcol = col   // move "down"
elsif row = 4 & col = 5 then
newrow = row & newcol = col-1   // move "left"
else

//  Not one of the four compulsory steps position. In this case,
//  the next step can be into one of the four different places.
//  (X marks the current position at row, col)
//
//  +---+---+---+---+---+---+
//  |   |   |   |   |   |   |
//  +---+---+---+---+---+---+
//  |   | 1 |   |   |   |   |
//  +---+---+---+---+---+---+
//  | 4 | X | 2 |   |   |   |
//  +---+---+---+---+---+---+
//  |   | 3 |   |   |   |   |
//  +---+---+---+---+---+---+
//  |   |   |   |   |   |   |
//  +---+---+---+---+---+---+
//  |   |   |   |   |   |   |
//  +---+---+---+---+---+---+

newcol =  col     & newrow = row - 1 |   // 1
newcol =  col + 1 & newrow = row |       // 2
newcol =  col     & newrow = row + 1 |   // 3
newcol =  col - 1 & newrow = row         // 4
end

local proc PrintOneRow(r:<[0..]->I,col:<I) iff
if col < Len(r) then
Print(r(col),' ') & PrintOneRow(r,col+1)
end

```