The Fifteen Puzzle

WilliamL. Colsher, 4328 Nutmeg Lane, Apt. Ill, Lisle, IL 60532.

The program that this article is based on does more than just generate a puzzle. One of the most important things it does is verify that the randomly generated puzzle is actually solvable. Clearly, this is a nice feature to have. The algorithm used in this section is given by D. D. Spencer Game Playing With Computers (Hayden Book Co., 1975). Fig. 2 illustrates this algorithm in verbal form.

1. Let N be a number in position A of the puzzle to be solved. Count how many num- bers smaller than N are in positions higherlettered than A. Count the blank as 16.
2. Do this for all 16 positions (A-P) and add up the count.
3. If the blank square is one of the following: B, D, E, G, J, L, M or O, add one to the sum.
4. There is a solution if the sum is even.
5. There is no solution if the sum is odd.

Fig. 2. Algorithm for 15 Puzzle solvability. *

* Adapted from Game Playing with Computers by D. D. Spencer.

The program checks for legal moves by examining the four (at most) locations that surround a given number (specified during the game by its coordinates). If any one of the locations contains the zero, then the move is legal. Otherwise, an error message is printed and play continues.

Playing the game is really quite simple. The computer will display the game board and then ask you for your move. You then just type in the number you wish to move and hit ENTER, after which the computer will re-draw the game board, making your move. In the event that your move results in a win (not very likely) the computer will congratulate you and ask if you want to play again.

Program Listing.

10        REM***THE FIFTEEN PUZZLE
20        REM***W. L. COLSHER
30        CLS:IN."DO YOU NEED INSTRUCTIONS (Y=1, N=2)";A:IF A=1 T.GOS.10000
40        CLS:M=0:P."GENERATING THE PUZZLE TAKES A WHILE. PLEASE WAIT."
50        F.I=1TO16:A(I)=0:N.I
60        F.I=1TO16
70        R=RND(16)
80        IFA(R)<>0T.70
90        A(R)=I
100       N.I
110       GOS.5000
120       IF F=1 T.50
130       GOS.6000
140       P." ":IN."YOUR MOVE";X
145       GOS.4000
150       GOS.7000
160       IF F<>0 T.180
170       P."ILLEGAL MOVE, RE-ENTER":F.I=1TO500:N.I:G.130
180       A(X+F)=A(X):A(X)=16
190       G.8000
200       M=M+1:G.130
999       END
4000      REM***C0NVERT NUMBER TO LOCATION IN ARRAY
4010      F.I=1TO16
4020           IFA(I)=X T.4040
4030      N.I
4040      X=I
4050      RET.
5000      REM***VERIFY SOLUTION POSSIBLE
5005      F=1
5010      S=0
5020      F.I=1to15
5030      F.J=I+1TO16
5040      IFA(I)>A(J)T.S=S+1
5050      N.J:N.I
5060      F.I=1TO8
5070      READ X
5080      IF A(X)=0 T. S=S+1
5090      N.I
5095      REST.
5100      A=INT(S/2)
5110      IFA*2=S T. F=0
5120      RET.
5130      DATA 2,4,5,7,10,12,13,15
6000      REM***DISPLAY GAME BOARD
6005      C.:L=339:P.A.217,"MOVE ";M
6010      F.I=1TO4
6015      P.A.L," ";

Listing continued.

6020      F.J=1TO4
6025      N=A((I-1)*4+J)
6028      IF N=16 T. N=0
6030      IF N<10 T.P." ";N;
6038      IF (N=10) * (N>16) T.P.N;
6040      N.J
6050      L=L+64
6060      N.I
6070      RET.
7000      REM***CHECK FOR LEGAL MOVE
7010      F=0
7015      IFX+1>16T.7025
7020      IFA(X+1)*16T.F=1
7025      IFX-1>=0T.7035
7030      IFA(X-1)=16T.F=-1
7035      IFX+4>16T.7045
7040      IFA(X+4)=16T.F=4
7045      IFX-4<=0T.7060
7050      IFA(X-4)=16T.F=-4
7060      RET.
8000      REM***CHECK FOR A WIN 
8010      F.I=1TO16
8020      IFA(I)<>I T.200
8030      N.I
8040      GOS.6000
8050      P." ":P." "
8060      P."CONGRATULATIONS!!! YOU DID IT IN ONLY ";M;" MOVES!!"
8070      P." ":IN."TO PLAY AGAIN, HIT ENTER. ";A$
8090      G.10
10000     REM***INSTRUCTIONS
10010     C.:P.A.18,"F I F T E E N   P U Z Z L E"
10020     P.A.128,"THE OBJECT OF THE 'FIFTEEN PUZZLE IS TO MOVE THE"
10030     P."NUMBERS AROUND SO THAT THEY ARE IN ORDER FROM 1 TO 15. A MOVE"
10040     P."IS MADE BY TYPING IN THE NUMBER (WHICH MUST BE ADJACENT TO"
10050     P."THE ZERO) YOU WISH TO MOVE. THAT NUMBER IS THEN EXCHANGED"
10060     P."WITH THE ZERO.  YOU WIN WHEN THE BOARD LOOKS LIKE THIS:"
10070     P." ":P." ":P." 1  2  3  4":P." 5  6  7  8":P." 9 10 11 12"
10080     P."13 14 15 0"
10090     P." ":IN."HIT ENTER TO PLAY";A$
10100     RET.

Programm Listing. [Das TRS-80 BASIC erlaubt für die Anweisungen Abkürzungen, z.B. GOS. für GOSUB, G. für GOTO, RET. für RETURN usw., die in der MBASIC Quelle erweitert sind]