N×N Sliding Puzzle Solver

Project Overview

This project provides two distinct implementations of a sliding puzzle solver, each optimized for different use cases. Both implementations leverage the A* search algorithm to find optimal solutions for n×n sliding puzzles, with unique approaches to state management and solution finding.

Twin-Board Implementation

Uses a twin board technique for efficient solvability detection and comprehensive puzzle management.

Guaranteed solvability detection
Multiple heuristic options
Comprehensive testing framework

Pure A* Implementation

Focuses on memory efficiency and includes segment-based solving capabilities.

Memory-efficient state management
Segment-based solving capability
Streamlined state exploration

Technical Implementation

Core Components

The project demonstrates advanced Java programming concepts and algorithm implementation:

Data Structures

Priority Queues for A* frontier management
HashSets for efficient explored state tracking
2D arrays for board representation
LinkedLists for solution path reconstruction

Algorithms

A* Search algorithm implementation
Manhattan distance heuristic calculation
Hamming distance computation
State space exploration techniques

Technical Skills Demonstrated

Java Features

Object-Oriented Design with inheritance and encapsulation
Interface implementation (Comparable, Iterable)
Generic Collections Framework usage
Stream API for efficient state processing
Custom comparators for state prioritization

Software Engineering

Clean code principles and documentation
Memory optimization techniques
Performance profiling and optimization
Unit testing and edge case handling
Version control with Git

Key Classes

Board.java & PuzzleState.java

Immutable state representation
Deep copying for state management
Efficient neighbor generation
Custom equality and hash code implementation
Board validation and goal state checking

Solver.java & AStarSolver.java

A* search implementation with optimizations
Twin board technique for solvability
Solution path reconstruction
Memory-efficient state exploration
Performance monitoring capabilities

Example Usage

// Create initial board
int[][] initialTiles = {
    {5, 1, 2, 3},
    {0, 6, 7, 4},
    {9, 10, 11, 8},
    {13, 14, 15, 12}
};

Board initial = new Board(initialTiles);
Solver solver = new Solver(initial);

if (solver.isSolvable()) {
    System.out.println("Minimum moves = " + solver.moves());
    for (Board board : solver.solution()) {
        System.out.println(board);
    }
}

Performance Considerations

Time Complexity

The A* algorithm's performance depends on the puzzle size and configuration. Performance has been optimized through:

Efficient heuristic calculations
Optimized state management
Smart duplicate detection

Space Complexity

Memory usage varies between implementations:

Twin-Board: O(bd) where b is branching factor
Pure A*: Optimized memory usage
Efficient state storage

Understanding Sliding Puzzles

What is a Sliding Puzzle?

A sliding puzzle is a combination puzzle that challenges a player to slide pieces along certain routes to establish a certain end configuration. The most common type is the n×n sliding puzzle that consists of n² − 1 numbered tiles and one blank space.

Classic 15-puzzle is a 4×4 version
Only one tile can be moved at a time
Tiles can only slide into the blank space
Goal is to arrange tiles in numerical order

Computational Challenge

Solving sliding puzzles presents significant computational challenges:

NP-hard for general n×n configurations
State space grows factorially with size
Not all configurations are solvable
Optimal solutions require sophisticated algorithms

Mathematical Properties

Solvability

Depends on the parity of permutations
Related to blank tile's position
Can be determined without solving
Twin board technique proves unsolvability

Search Space

3×3 puzzle: 362,880 possible states
4×4 puzzle: Over 10 trillion states
Each state has 2-4 possible moves
Branching factor affects search complexity