The original board has a two-move witness and Manhattan lower bound two. The working JavaScript A* search finds Right, Right, then replays legal swaps to the goal. A one-expansion budget reports Unknown instead of no solution. Invalid duplicate or nonnumeric tiles are rejected without repair.
Work through the example
Solve the baseline to see g two and the Right, Right witness. Replay next twice to reach the goal. Set budget one and Solve again: the search stops before expanding the intermediate board and reports BudgetExceeded/Unknown. An already-goal input returns zero moves without consuming an expansion. Manhattan excludes the blank.
Replay the reconstructed witness independently and compare its final board and length with the reported goal cost. A budget cutoff reports unfinished search. The two-move baseline also has a lower bound of two, giving a small hand-checkable shortest-path argument. Changing the start or budget clears the previous witness; do not display an old solution as though it belongs to new input.
Validate the board and define move direction
Represent a 3 × 3 board as nine row-major values. Zero denotes the blank.
Original start:
[1,2,3,4,5,6,0,7,8]
Original goal:
[1,2,3,4,5,6,7,8,0]
For display, the start is:
1 2 3
4 5 6
_ 7 8
Validate exactly nine unique integers from 0 through 8. A duplicate tile, missing value, extra value, fraction, or numeric string is invalid input under this authored contract. Do not repair the board by guessing a missing tile.
Name moves by the direction of the blank. Blank Right swaps the blank with the tile immediately to its right. That tile travels left. State the convention so a replay record cannot confuse those directions.
Legal neighbors are horizontal or vertical adjacent cells inside the board. An adjacent array index is not always a legal neighbor: moving right from the end of a row must not wrap to the next row.
The historical University of Texas eight-puzzle assignment describes adjacent tile/blank swaps and reporting solution paths. This fixture uses its own goal, inputs, and ledger rather than copying the assignment's boards or Lisp code.
Exclude the blank from Manhattan distance
For tiles 1 through 8, sum the absolute row and column differences between each current position and its goal position. The blank contributes nothing.
In the original start, tiles 1 through 6 are already placed. Tile 7 is one column right of its goal, and tile 8 is one column right of its goal. The sum is therefore 2.
A legal swap moves one numbered tile by one grid step. Summing the numbered tiles' Manhattan distances supplies a lower bound for this unit-cost model; a tile cannot cover more than one such step in a single move. Counting the blank too would double-count part of that work.
The Illinois A* lecture discusses admissible lower bounds, tile Manhattan distance, and stopping when the goal is the best frontier option. Its course date is historical; it is not a current JavaScript API or performance result.
Keep the exact goal fixed while calculating the heuristic. A different goal requires a new goal-position map and new expectations.
Replay the original two-move witness
The hand-derived path is:
| Step | Blank move | Board | Path cost g | Manhattan h | f = g + h |
|---|---|---|---|---|---|
| 0 | None | [1,2,3,4,5,6,0,7,8] | 0 | 2 | 2 |
| 1 | Right | [1,2,3,4,5,6,7,0,8] | 1 | 1 | 2 |
| 2 | Right | [1,2,3,4,5,6,7,8,0] | 2 | 0 | 2 |
The first swap exchanges positions 6 and 7. The second exchanges positions 7 and 8. Both pairs are adjacent within the bottom row. Each board still contains the same nine values exactly once.
Recreate this example
Build one self-contained responsive HTML example titled “8-puzzle JavaScript: solve and replay a witness” for readers completing the stated task. Return the complete HTML with embedded CSS and JavaScript. Use no remote fonts, libraries, images, requests, account connections, or saved-state claims.
Implement A* for a 3 × 3 puzzle. Board JSON must contain nine unique integers 0–8; reject numeric strings. Zero is blank. Start [1,2,3,4,5,6,0,7,8]; goal [1,2,3,4,5,6,7,8,0]. Manhattan excludes blank. Prioritize f, h, lexical key, then sequence. Track best g and immutable parents, skip stale pops, and accept a current goal when popped. Budget is an integer 1–10000: baseline budget 1 yields Unknown; 100 solves in two Right moves. Reconstruct and check every legal swap. Replay next advances with a boundary guard. Board or budget edits clear witness and board display; validation failures show no previous board. Draw only validated current input. Display cost, initial Manhattan, expansions and status without universal speed claims.
Use a search workbench with a 3×3 board, Manhattan ledger and replayable legal blank moves design with a compact header. Keep the actual sample data, controls, and useful default result visible early on a 360px-wide screen. Use readable text at least 16px, generous paragraph spacing, strong contrast, semantic labels, visible keyboard focus, and wrapping source blocks. Stack records on narrow screens rather than forcing a wide table.
Wire each action to an explicit type=button click handler using element selectors; the host permits scripts but blocks form submission. Update the visible result when the described action occurs. Show specific error feedback for invalid or missing input and clear stale feedback after dependent inputs change. Use plain text when displaying user values.
The bounded local solver makes no universal performance guarantee; a cutoff means unfinished search, not unsolvability. Keep the source fixture and worked teacher or developer example distinct from actual user records. Include the domain-specific explanation and next check beside the result. Provide no fake download, send, deployment, approval, or persistence button. Everything operates locally for the current page session.
Review the prepared copy in NOS
Use the two-move case as a regression before trying harder starts and larger budgets. NOS can render the HTML search explanation, and eligible static replay instructions can be revised visually. Preserve the actual solver source and tested witnesses when extending the search.