HomeHome More SamplesMore 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
    






This page was created by F1toHTML