Slide (the 24-Puzzle)

Type
Game
Category
Sliding tile puzzle
Author
Mark Moore (program); article by Michael Ciraolo
Published in
Antic, July 1985 (Vol. 4, No. 3)
Year
1985
Language
Atari BASIC
Requirements
16K RAM, Atari BASIC, joystick in port 1; disk or cassette
Slide: a 5 by 5 grid of shuffled letters A to X with one blank square, drawn in GRAPHICS 0 line characters, with a YOU ARE ON box at the right

About the program

Sliding tile puzzles, 8 tiles in a 3×3 frame or 15 in a 4×4, have been around for well over a century. Slide uses a 5×5 frame with 24 lettered tiles. The game came from Mark Moore of Weatherford, Oklahoma (his first program in Antic), and associate editor Michael Ciraolo wrote the article that went with it in July 1985.

Ciraolo used the puzzle as a way into "intelligent" game design. He described a search tree grown from the starting position by a legal-move generator, an evaluation function that adds up how far every tile is from its home square, and "pruning" to drop branches that look unpromising, such as a move that simply undoes the previous one. He then challenged readers to turn Slide into a program that solves the puzzle, and promised to publish the shortest and most elegant solution.

Typing it in

Lines 80–180 draw the frame with ATASCII line-drawing characters, all in inverse video. {inv} … {/inv} means press the Atari (inverse) key before and after. {CTRL-Q}, {CTRL-R}, {CTRL-E} and so on mean hold CTRL and press the letter. The | characters in lines 90–170 are typed with SHIFT and =. Line 610 prints one inverse space. Antic printed TYPO II checksums beside each line of the magazine listing. They are not part of the program.

How to play

RUN it and wait while the 24 letters are shuffled into the frame. The empty square starts in the bottom right corner. Move the flashing cursor with the joystick, and press fire to slide the tile under the cursor into the empty square next to it. Diagonal moves aren't allowed, and an impossible move gets an ILLEGAL MOVE warning. The box on the right shows which letter you are on. Once you think the tiles read A to X, press SPACE. The program checks every square in turn. You either get your time in seconds or a SORRY.

A word of warning: lines 220–250 just deal the letters in a random order. On a 5×5 board only half of all possible arrangements can be solved, so some games are impossible. You can tell before you start: count the pairs of letters that are in the wrong order relative to each other, reading row by row. If that number is odd, the puzzle can't be done. Press BREAK and RUN again.

How it works

The board lives on the text screen itself. LOCATE reads the character at the cursor (line 430), and then lines 500–570 look up, down, left and right of it for the code of an inverse space (160), which marks the empty square. Locations 18–20 (the real-time clock) are zeroed when play starts and read back in line 720. That line multiplies location 18 by 256 instead of 65536, but this only matters if you take longer than about 18 minutes.

Variations to try

Make the shuffle start from the solved board and apply a few hundred random legal moves, so that every puzzle can be solved. Or take up Ciraolo's challenge and add a solver.

Listing

10 REM SLIDE
20 REM BY MARK MOORE
30 REM (c) 1985, ANTIC PUBLISHING
40 DIM N(30)
50 GRAPHICS 0:SETCOLOR 2,7,0:SETCOLOR 4,0,2:POKE 752,1
60 POSITION 17,1:? "SLIDE":POSITION 13,2:? "by Mark Moore":POSITION 6,18:? "{inv} Please wait {/inv}"
70 POSITION 2,4:POKE 82,12:?
80 ? " {inv}{CTRL-Q}{CTRL-R}{CTRL-W}{CTRL-R}{CTRL-W}{CTRL-R}{CTRL-W}{CTRL-R}{CTRL-W}{CTRL-R}{CTRL-E}{/inv}"
90 ? " {inv}| | | | | |{/inv}"
100 ? " {inv}{CTRL-A}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-D}{/inv}"
110 ? " {inv}| | | | | |{/inv}"
120 ? " {inv}{CTRL-A}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-D}{/inv}            {inv}{CTRL-Q}{CTRL-R}{CTRL-E}{/inv}"
130 ? " {inv}| | | | | |{/inv} YOU ARE ON {inv}| |{/inv}"
140 ? " {inv}{CTRL-A}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-D}{/inv}            {inv}{CTRL-Z}{CTRL-R}{CTRL-C}{/inv}"
150 ? " {inv}| | | | | |{/inv}"
160 ? " {inv}{CTRL-A}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-S}{CTRL-R}{CTRL-D}{/inv}"
170 ? " {inv}| | | | | |{/inv}"
180 ? " {inv}{CTRL-Z}{CTRL-R}{CTRL-X}{CTRL-R}{CTRL-X}{CTRL-R}{CTRL-X}{CTRL-R}{CTRL-X}{CTRL-R}{CTRL-C}{/inv}"
190 POKE 82,2:? :C=1
200 FOR V=1 TO 5:HL=5:IF V=5 THEN HL=4
210 FOR H=1 TO HL
220 R=INT(RND(0)*24)+1
230 N(C)=R
240 FOR P=0 TO C-1:IF N(P)=R THEN 220
250 NEXT P:C=C+1
260 POSITION H*2+12,V*2+4:? CHR$(64+R)
270 NEXT H:NEXT V
280 ? :? :? :? " Arrange in alphabetical order (A-X)."
290 POSITION 3,7:? "YOU CAN "
300 ? "MOVE INTO"
310 ? "THE BLANK"
320 ? "  SPACE.":?
330 ? "   NO "
340 ? "DIAGONAL"
350 ? " MOVES."
360 H=22:V=14:POKE 20,0:POKE 19,0:POKE 18,0
370 S=STICK(0)
380 IF PEEK(764)=33 THEN 640
390 IF S=14 AND V>6 THEN V=V-2
400 IF S=13 AND V<14 THEN V=V+2
410 IF S=7 AND H<22 THEN H=H+2
420 IF S=11 AND H>14 THEN H=H-2
430 LOCATE H,V,C
440 POSITION H,V:? CHR$(C+128)
450 IF S=15 THEN FOR D=1 TO 10:NEXT D
460 IF S<>15 THEN FOR D=14 TO 0 STEP -0.5:SOUND 0,30,10,D:NEXT D:POKE 53279,0
470 POSITION H,V:? CHR$(C):POSITION 37,10:? CHR$(C)
480 IF STRIG(0)=0 THEN 500
490 GOTO 370
500 LOCATE H,V+2,K
510 IF K=160 THEN POSITION H,V+2:? CHR$(C):GOTO 610
520 LOCATE H,V-2,K
530 IF K=160 THEN POSITION H,V-2:? CHR$(C):GOTO 610
540 LOCATE H+2,V,K
550 IF K=160 THEN POSITION H+2,V:? CHR$(C):GOTO 610
560 LOCATE H-2,V,K
570 IF K=160 THEN POSITION H-2,V:? CHR$(C):GOTO 610
580 LOCATE 1,1,K
590 POSITION 12,21:? "{inv} ILLEGAL MOVE {/inv}":SOUND 0,70,12,6:FOR D=1 TO 30:NEXT D
600 SOUND 0,0,0,0:POSITION 12,21:? "-            -":GOTO 370
610 POSITION H,V:? "{inv} {/inv}"
620 FOR D=14 TO 0 STEP -1:SOUND 0,20,12,D:NEXT D:POKE 77,0
630 GOTO 370
640 T=0:POKE 764,255:FOR V1=1 TO 5:HL=5:IF V1=5 THEN HL=4
650 FOR H1=1 TO HL
660 T=T+1:LOCATE H1*2+12,V1*2+4,C
670 POSITION H1*2+12,V1*2+4:? "{inv}*{/inv}":FOR D=1 TO 10:NEXT D
680 POSITION H1*2+12,V1*2+4:? CHR$(C)
690 IF C-64<>T THEN 760
700 NEXT H1:NEXT V1
710 POSITION 4,20:? "{inv} YOU DID IT!!{/inv}":? "TIME: "
720 T=PEEK(20)+256*PEEK(19)+256*PEEK(18):T=T/60
730 ? :? "       ";T;" SECONDS"
740 ? :? :? :?
750 END
760 FOR T=1 TO 5:POSITION 3,21:? "{inv} SORRY {/inv}":SOUND 0,70,12,8
770 FOR D=1 TO 10:NEXT D:SOUND 0,0,0,0:POSITION 3,21:? "       "
780 FOR D=1 TO 10:NEXT D:NEXT T
790 LOCATE 1,1,K:GOTO 370

Download

The original program from the Antic disk, to LOAD or ENTER instead of typing it: SLIDE.BAS.

Credits