/////////////////////////////////////////////////////////////////////////////// // 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