All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Crossing the board (Posted on 2005-09-30) Difficulty: 3 of 5
You are given a board 5x5 and 24 square pieces (1x1), one of them with a cross (+) and all the others 23 with a straight line on it (25 such pieces would cover the entire board).
                   (1)              (23) 
                +-------+         +-------+  
                |  _|_  |         | _____ |
                |   |   |         |       |
                +-------+         +-------+
Place the cross-piece in the upper left corner of the board.

Your task is to find "how to put the others 23 pieces," leaving the bottom right corner free, so that once this is made, by only sliding the pieces, you can bring the cross-piece from the upper left corner to the right bottom corner (that is "free" initially).

"How to put the other 23 pieces" means what must be the orientation of the line on each one, horizontal or vertical, since those placed with the line horizontal-oriented can only slide horizontally - to the right and to the left,- and those placed with the line vertical-oriented can only slide vertically - up and down. Obviously, sliding is limited by the edges of the board.

The cross-piece is the only one that can slide horizontally and vertically.

See The Solution Submitted by pcbouhid    
Rating: 3.8000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution -- computer assisted | Comment 2 of 10 |

The way I approaced it was to start with the + piece and the empty space in their proper positions, while leaving the other pieces indeterminate.  As each piece gets used, its orientation is determined from then on.

The following program does that, systematically trying each possible move from a given state.  When it reaches an impasse (or has traced 40 steps) it backtracks and continues with the next move from whatever level it can.  The indeterminate states are marked by a ?, vertical movers by a | and horizontal movers by a -.  An "impasse" means that any legal move from there results in a combination of + position and blank position that was arrived at before in the same solution chain.

DECLARE SUB move ()
CLEAR , , 10000
DIM SHARED board$(5, 5)
DIM SHARED rboard$(5, 5)
DIM SHARED origRow(5, 5)
DIM SHARED origCol(5, 5)
DIM SHARED hadState(625)
DIM SHARED blRow, blCol, plusRow, plusCol, lvl, h$


OPEN "crosbrd2.txt" FOR OUTPUT AS #2
FOR r = 1 TO 5
 FOR c = 1 TO 5
  board$(r, c) = "?"
  origRow(r, c) = r
  origCol(r, c) = c
 NEXT
NEXT

board$(1, 1) = "+"
board$(5, 5) = "O"

blRow = 5: blCol = 5
plusRow = 1: plusCol = 1

CLS
state = (5 - 1) * 125 + (5 - 1) * 25 + (1 - 1) * 5 + 1 - 1
hadState(state) = 1

move

SUB move
 lvl = lvl + 1
 FOR i = 1 TO 4
   a$ = MID$("udlr", i, 1)
   SELECT CASE LCASE$(a$)
     CASE "d"
      r = blRow - 1: c = blCol
     CASE "u"
      r = blRow + 1: c = blCol
     CASE "l"
      r = blRow: c = blCol + 1
     CASE "r"
      r = blRow: c = blCol - 1
   END SELECT
   IF r < 1 OR r > 5 OR c < 1 OR c > 5 THEN
    REM
   ELSEIF (a$ = "u" OR a$ = "d") AND board$(r, c) = "-" OR (a$ = "l" OR a$ = "r") AND board$(r, c) = "|" THEN
    REM
   ELSE
    pb$ = board$(r, c)
    IF pb$ = "+" THEN
     pr = blRow: pc = blCol
    ELSE
     pr = plusRow: pc = plusCol
    END IF
    newstate = (r - 1) * 125 + (c - 1) * 25 + (pr - 1) * 5 + pc - 1
    IF hadState(newstate) = 0 THEN
    '  PRINT lvl; newstate
      hadState(newstate) = 1
      IF board$(r, c) = "?" THEN
        IF a$ = "u" OR a$ = "d" THEN board$(r, c) = "|"
        IF a$ = "l" OR a$ = "r" THEN board$(r, c) = "-"
      END IF
      SWAP board$(r, c), board$(blRow, blCol)
      SWAP origRow(r, c), origRow(blRow, blCol)
      SWAP origCol(r, c), origCol(blRow, blCol)
      saveBlRow = blRow: saveBlCol = blCol
      blRow = r: blCol = c
      h$ = h$ + a$

      IF pb$ = "+" THEN plusRow = saveBlRow: plusCol = saveBlCol

      IF pb$ = "+" AND saveBlRow = 5 AND saveBlCol = 5 THEN
        FOR rw = 1 TO 5
         FOR cl = 1 TO 5
           ro = origRow(rw, cl)
           co = origCol(rw, cl)
           rboard$(ro, co) = board$(rw, cl)
         NEXT
        NEXT

        PRINT
        PRINT #2,
        FOR rw = 1 TO 5
         FOR cl = 1 TO 5
          PRINT rboard$(rw, cl);
          PRINT #2, rboard$(rw, cl);
         NEXT
         PRINT
         PRINT #2,
        NEXT
        PRINT h$
        PRINT #2, h$
      ELSE
       IF lvl < 40 THEN
        move
       END IF
      END IF


      h$ = LEFT$(h$, LEN(h$) - 1)
      blRow = saveBlRow: blCol = saveBlCol
      SWAP board$(r, c), board$(blRow, blCol)
      SWAP origRow(r, c), origRow(blRow, blCol)
      SWAP origCol(r, c), origCol(blRow, blCol)
      board$(r, c) = pb$
      IF pb$ = "+" THEN plusRow = r: plusCol = c
      hadState(newstate) = 0
    END IF
   END IF
 NEXT
 lvl = lvl - 1

END SUB

The shortest solution it finds is:

+-???
||-??
-||-?
?-|-|
??-|O
drurdrdrddluruldluruldluruldlur

where some pieces have never moved and so are still indeterminate--they could be oriented either way.  The moves to solve this are marked below it, representing down, right, up and left.  These are the motions of the piece being moved, not of the empty square.

Here's this solution worked out, with the 0 representing the empty spot (read left to right then go to the next row):

 +-???  +-???  +-???  +-???
 ||-??  ||-??  ||-??  ||-??
 -||-?  -||-?  -||-?  -||-?
 ?-|-|  ?-|-O  ?-|O-  ?-||-
 ??-|O  ??-||  ??-||  ??-O|
 +-???  +-???  +-???  +-???
 ||-??  ||-??  ||-??  ||-??
 -||-?  -||-?  -||-?  -O|-?
 ?-||-  ?-O|-  ?O-|-  ?|-|-
 ??O-|  ??|-|  ??|-|  ??|-|
 +-???  +-???  O-???  -O???
 ||-??  O|-??  +|-??  +|-??
 O-|-?  |-|-?  |-|-?  |-|-?
 ?|-|-  ?|-|-  ?|-|-  ?|-|-
 ??|-|  ??|-|  ??|-|  ??|-|
 -|???  -|???  -|???  -|???
 +O-??  O+-??  |+-??  |+-??
 |-|-?  |-|-?  O-|-?  -O|-?
 ?|-|-  ?|-|-  ?|-|-  ?|-|-
 ??|-|  ??|-|  ??|-|  ??|-|
 -|???  -|???  -|???  -|???
 |O-??  |-O??  |-|??  |-|??
 -+|-?  -+|-?  -+O-?  -O+-?
 ?|-|-  ?|-|-  ?|-|-  ?|-|-
 ??|-|  ??|-|  ??|-|  ??|-|
 -|???  -|???  -|???  -|???
 |-|??  |-|??  |-|??  |-|??
 -|+-?  -|+-?  -|O-?  -|-O?
 ?O-|-  ?-O|-  ?-+|-  ?-+|-
 ??|-|  ??|-|  ??|-|  ??|-|
 -|???  -|???  -|???  -|???
 |-|??  |-|??  |-|??  |-|??
 -|-|?  -|-|?  -|-|?  -|-|?
 ?-+O-  ?-O+-  ?-|+-  ?-|+-
 ??|-|  ??|-|  ??O-|  ??-O|
 -|???  -|???  -|???  -|???
 |-|??  |-|??  |-|??  |-|??
 -|-|?  -|-|?  -|-|?  -|-|?
 ?-|O-  ?-|-O  ?-|-|  ?-|-|
 ??-+|  ??-+|  ??-+O  ??-O+

The program found 1707 basic solutions (this one plus 1706 others). Each of course has variations, as each of the ?'s can be replaced by either a vertical or horizontal line.  Also, I chose only those solutions starting with a d move.  Each such has a reflection that starts with an r move.  Also, the program limited its search to paths of 40 or fewer moves.  All the solutions have at least one spot which does not move and therefore is indeterminate.

A different solution, chosen in the middle of the file at random:

+-|--
||-?|
-||-|
?||-|
?--|O
drurrddrddluruldluruulddddlluururuldlur

 


  Posted by Charlie on 2005-09-30 21:08:44
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information