--- title: "Fifteen Puzzle" id: 57510 type: "computer_media" slug: "fifteen-puzzle" url: "http://localhost/computer_media/fifteen-puzzle/" markdown_url: "http://localhost/computer_media/fifteen-puzzle.md" published_at: "2024-10-05T21:16:07+00:00" modified_at: "2026-03-30T21:17:36+00:00" author: "David Anderson" featured_image: url: "http://localhost/wp-content/uploads/2024/10/265_15P.png" excerpt: "Slide the tiles into order in this complete Fifteen Puzzle implementation, complete with a mathematical solvability check to ensure every random board can actually be solved." category: - name: "Archived Media" slug: "archived-media" taxonomy: "category" url: "http://localhost/category/archived-media/" post_tag: - name: "Downloadable" slug: "downloadable" taxonomy: "post_tag" url: "http://localhost/tag/downloadable/" - name: "TS 1000" slug: "ts1000" taxonomy: "post_tag" url: "http://localhost/tag/ts1000/" model: - name: "Timex/Sinclair 1000" slug: "ts-1000" taxonomy: "model" url: "http://localhost/model/ts-1000/" genre: - name: "Game" slug: "game" taxonomy: "genre" url: "http://localhost/type/game/" media_contents: - id: 56737 title: "Timex Sinclair Public Domain Library Tape 1006" type: "computer_media" url: "http://localhost/computer_media/timex-sinclair-public-domain-library-tape-1006/" media_type: "Program" mediadate: "198x" images: - url: "http://localhost/wp-content/uploads/2024/10/265_15P.png" media_type_tags: "Game, Software" --- This program implements the classic Fifteen Puzzle (sliding tile puzzle) in BASIC, where the player slides numbered tiles 1–15 on a 4×4 grid to arrange them in order, with the 16th position acting as the blank space. Array A(16) stores the board state and array B(8) holds the positions of tiles on even-numbered rows, used together to determine whether a randomly generated board configuration is solvable before play begins. The solvability check at line 500 counts inversions (pairs where a higher-numbered tile precedes a lower one) and adds corrections for blank-space row position, accepting the layout only if the total is even. The move validation routine at line 700 checks all four cardinal directions and returns an offset F (±1 or ±4) indicating which neighbouring cell holds the blank, rejecting moves that would cross the array boundary. The player enters tile numbers rather than directions, and the move counter M tracks the number of moves taken to reach the solved state. *** ## Program Analysis ### Program Structure The code is organised as a main loop with clearly separated subroutines. Execution flows from initialisation through the game loop to win detection, with subroutines handling distinct tasks: 1. Lines 3–5: Array declarations (`B(8)` for even-row sentinel positions, `A(16)` for the board). 2. Lines 10–110: Initialisation — populate `B`, shuffle the board randomly, and verify solvability (retrying if unsolvable). 3. Lines 120–230: Main game loop — display board, accept and validate player move, apply it. 4. Lines 240–250: Move counter increment and loop-back to display. 5. Lines 300–380: Subroutine to fill the even-row position lookup array `B`. 6. Lines 400–440: Subroutine to convert a tile number to its array index. 7. Lines 500–590: Solvability checker using inversion count. 8. Lines 600–670: Board display routine with 4×4 grid formatting. 9. Lines 700–760: Legal move validator returning direction offset `F`. 10. Lines 800–870: Win-detection loop and congratulations message. ### Board Representation The 4×4 grid is stored as a flat 16-element array `A()`, where `A(I)` holds the tile at position `I`. Tile 16 represents the blank space. Adjacency is expressed arithmetically: horizontal neighbours differ by 1, vertical neighbours by 4. No boundary wrapping is prevented for horizontal moves, however — see the Bugs section below. ### Solvability Check (Lines 500–590) This is the most mathematically sophisticated part of the program. It counts the number of inversions: for every pair `(i, j)` with `i < j`, if `A(I) > A(J)` then `S` is incremented. For a 4×4 puzzle with an even-width grid, solvability also depends on which row (counting from the bottom) the blank occupies. The array `B(8)` holds the eight array indices that correspond to even-numbered rows (positions 2, 4, 5, 7, 10, 12, 13, 15 — rows 3 and 4 from the top, i.e. rows 2 and 1 from the bottom), and if tile 16 (the blank) is found at one of those positions, `S` is further incremented. The configuration is solvable if and only if the resulting `S` is even, tested at line 585 with the standard `(S/2)*2=S` parity idiom. If unsolvable, `F=1` causes a fresh shuffle at line 110. ### Move Input and Validation The player enters the *number on the tile* they wish to move (not a direction). The subroutine at lines 400–440 scans the array to find which index `I` holds that tile value, then overwrites `X` with the index. The legality checker at lines 700–760 then inspects the four neighbouring cells. It returns `F = 0` if no neighbour is the blank (illegal), or `F ∈ {1, −1, 4, −4}` representing the direction offset to the blank. Line 210 applies the move as `A(X+F) = A(X)`, and line 220 places tile 16 in the vacated cell. ### Board Display (Lines 600–670) The display subroutine uses a single index variable `I` counting from 1 to 16. An inner `FOR Y=1 TO 4` loop prints each row of four tiles. Single-digit tiles are padded with a leading space (line 632). The blank (tile 16) prints two spaces instead of its number. After each group of four, the outer flow checks whether `I=17` to decide whether to return or loop back for the next row. ### Key BASIC Idioms - `(S/2)*2=S` — integer even/odd parity test without a MOD operator. - `IF NOT A(R)=0 THEN GOTO 60` — retry loop for rejection-sampling during shuffle. - `IF NOT F=0 THEN GOTO 210` — equivalent to `IF F<>0`. - `LET C=X` at line 152 saves the original user input before `X` is overwritten by the index-lookup subroutine, so the error message at line 190 can report the tile number the user entered. ### Bugs and Anomalies - **Horizontal wrap-around:** The move validator at line 710 only checks `X+1 > 16` and `X-1 <= 0` as array bounds, but does not detect that position 4 and position 5 are on different rows. A tile at position 4 (rightmost of row 1) would incorrectly consider position 5 (leftmost of row 2) a valid horizontal neighbour, and similarly across all row boundaries. - **Diagonal adjacency ignored:** Only offsets ±1 and ±4 are checked; diagonal positions are never a concern in a sliding puzzle, so this is correct by design. - **Lines 880–900 unreachable:**`STOP` at line 870 halts execution before lines 880 (`CLEAR`) and 890 (`SAVE "1026%5"`) can run. These appear to be vestigial development/save lines left in the listing. - **`GOTO 60` without bounds check:** The shuffle loop at line 60–70 will spin indefinitely if a bug caused all slots to be filled, but in normal operation this terminates correctly since all 16 positions are assigned exactly once. ### Data Summary | Array | Size | Purpose | | --- | --- | --- | | `A()` | 16 | Current board state; value = tile number, index = position | | `B()` | 8 | Indices of even-row positions for solvability check | ## Source Code ``` 3 DIM B(8) 5 DIM A(16) 10 GOSUB 300 15 LET M=0 20 FOR I=1 TO 16 30 LET A(I)=0 40 NEXT I 50 FOR I=1 TO 16 60 LET R=INT (RND*16)+1 70 IF NOT A(R)=0 THEN GOTO 60 80 LET A(R)=I 90 NEXT I 100 GOSUB 500 110 IF F=1 THEN GOTO 20 120 GOSUB 600 130 PRINT 140 PRINT "YOUR MOVE" 150 INPUT X 152 LET C=X 155 IF X=0 THEN STOP 160 GOSUB 400 170 GOSUB 700 180 IF NOT F=0 THEN GOTO 210 185 PRINT 190 PRINT C;" IS AN ILLEGAL MOVE,RE-ENTER" 200 GOTO 150 210 LET A(X+F)=A(X) 220 LET A(X)=16 230 GOTO 800 240 LET M=M+1 250 GOTO 120 300 LET B(1)=2 310 LET B(2)=4 320 LET B(3)=5 330 LET B(4)=7 340 LET B(5)=10 350 LET B(6)=12 360 LET B(7)=13 370 LET B(8)=15 380 RETURN 390 REM CONVERT NO.TO LOCATION IN ARRAY 400 FOR I=1 TO 16 410 IF A(I)=X THEN GOTO 430 420 NEXT I 430 LET X=I 440 RETURN 450 REM VERIFY SOLUTION POSSIBLE 500 LET F=1 510 LET S=0 520 FOR I=1 TO 15 530 FOR J=I+1 TO 16 540 IF A(I)>A(J) THEN LET S=S+1 550 NEXT J 560 NEXT I 565 FOR I=1 TO 8 570 IF A(B(I))=16 THEN LET S=S+1 575 NEXT I 585 IF (S/2)*2=S THEN LET F=0 590 RETURN 595 REM DISPLAY GAME BOARD 600 CLS 610 PRINT ,"FIFTEEN PUZZLE" 615 PRINT 620 LET I=1 625 PRINT , 630 FOR Y=1 TO 4 632 IF A(I)<10 THEN PRINT " "; 635 IF A(I)=16 THEN PRINT " "; 640 IF NOT A(I)=16 THEN PRINT A(I); 645 PRINT " "; 650 LET I=I+1 655 NEXT Y 660 PRINT 662 PRINT 665 IF I=17 THEN RETURN 670 GOTO 625 680 REM CHECK FOR LEGAL MOVE 700 LET F=0 710 IF X+1>16 THEN GOTO 725 720 IF A(X+1)=16 THEN LET F=1 725 IF X-1<0 OR X-1=0 THEN GOTO 735 730 IF A(X-1)=16 THEN LET F=-1 735 IF X+4>16 THEN GOTO 745 740 IF A(X+4)=16 THEN LET F=4 745 IF X-4<0 OR X-4=0 THEN GOTO 760 750 IF A(X-4)=16 THEN LET F=-4 760 RETURN 770 REM CHECK FOR WIN 800 FOR I=1 TO 16 810 IF NOT A(I)=I THEN GOTO 240 820 NEXT I 830 GOSUB 600 840 PRINT 850 PRINT 860 PRINT "YOU WON IN ONLY";M;"MOVES" 870 STOP 880 CLEAR 890 SAVE "1026%5" 900 RUN ```