Eight Puzzle

1. Introduction

Eight Puzzle is a classic 3×3 logic-based tile rearrangement game developed using Java Swing. The player is presented with 8 numbered tiles and one empty tile in a 3×3 grid. The goal is to slide the tiles into the correct order (1 to 8), using the empty space strategically. The player clicks on tiles adjacent to the empty space to swap their positions.

The game features randomized tile generation, manual board configuration, move tracking, sound effects, and an interactive GUI layout. It challenges the player’s spatial reasoning and memory through tile movements and logical decisions. An AI auto-solve mode using the A* algorithm is also included for demonstration and benchmarking.

2. Core Features

1. 3×3 Grid Layout: The board is implemented as a 3×3 grid with 9 JButton tiles.
2. Randomized or Custom Start: Tiles numbered 1–8 and one empty slot can be shuffled or user-defined.
3. Empty Tile: Represented using the number 0, which is made invisible to simulate the sliding effect.
4. Tile Movement: Only tiles directly adjacent (left, right, top, bottom) to the empty tile are eligible to move.
5. Sound Effects: Each valid move plays a wood-click audio to enhance interactivity.
6. Move Tracking: A live label updates the number of user moves.
7. AI Solver: Includes an automatic solver using the A* search algorithm with animated solution replay.
8. Solvability Check: Generated puzzles are always validated for solvability using inversion count logic before being accepted.
9. Manual Board Validation: User-configured boards are also checked in real-time to prevent unsolvable setups before the game starts.

3. How Tile Movement Logic Works

1. Empty Tile Index: The index of the invisible (empty) tile is tracked using indexOfCurrentEmptyTile.

2. Valid Moves: When a tile is clicked, the program checks if its index is one of the four adjacent positions to the empty tile:
    • Up: index - 3
    • Down: index + 3
    • Left: index - 1 (only if not on the left edge)
    • Right: index + 1 (only if not on the right edge)

3. Edge Cases:
    • Left swaps are blocked if the empty tile is at column 0.
    • Right swaps are blocked if the empty tile is at column 2.

4. Tile Swapping Mechanism

1. Swap Execution: If the clicked tile is adjacent, the swapButtons() method is called.
2. Swap Actions:
    • The text from the clicked tile is transferred to the empty tile.
    • The clicked tile is hidden (setVisible(false)).
    • The previously empty tile becomes visible again.
    • The index of the empty tile is updated accordingly.
3. Move Counter: After every successful move, the counter increments and updates the Moves: label.
4. Sound Feedback: A wood-click sound is played after every tile slide to enhance user experience.

5. Technical Structure Overview

1. Grid Setup: The 3×3 board is constructed using a JPanel with GridLayout(3, 3) and contains 9 JButton tiles.
2. Text & Icons: Each tile displays a number (1–8), while tile 0 is hidden and acts as the movable space.
3. Shuffling: A randomized or user-defined ArrayList of numbers is used to initialize the board.
4. Listeners: Action listeners are added to each tile to handle click events and trigger movement logic.
5. Menu System: Includes Options and Help menus with features for New Game, Exit, Rules, Contact, and About.
6. Auto-Solver: Clicking "Auto solve using AI" runs the A* algorithm and animates the solution step-by-step.

6. How the A* Algorithm Works

The A* algorithm is an informed search method that finds the shortest solution path from a given puzzle configuration to the goal state. Here's how it functions in this project:

• State Representation: The board is modeled as a 1D array of 9 integers (0–8), where 0 represents the empty tile.
• Goal Test: The target configuration is [1, 2, 3, 4, 5, 6, 7, 8, 0].
• Heuristic (h): Manhattan distance is calculated as the sum of vertical and horizontal distances between each tile's current and target position.

  The Manhattan distance for each tile is calculated as:
  
  Manhattan Distance = |currentRow - goalRow| + |currentCol - goalCol|
  
  For all tiles, the total heuristic h(n) is the sum of their individual distances from the goal positions, excluding the blank tile (0).

• Cost (g): The number of steps taken from the initial state to the current state.
• Total Cost (f = g + h): States are prioritized in a min-heap (PriorityQueue) using this total estimated cost.
• Neighbor Expansion: All valid moves from the current state are generated by swapping 0 with its adjacent tiles.
• Visited Tracking: States are hashed and stored to avoid cycles and redundant exploration.
• Path Reconstruction: Once the goal is found, a backward traversal using parent pointers reconstructs the solution path, which is then animated in the GUI.