Fifteen Puzzle

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