8-Puzzle Solver

Problem

An 8-puzzle is a game played on a 3 x 3 board of tiles, with the ninth tile missing. The remaining tiles are labeled 1 through 8 but shuffled randomly. Tiles may slide horizontally or vertically into an empty space, but may not be removed from the board.

Design a class to represent the board, and find a series of steps to bring the board to the state [[1, 2, 3], [4, 5, 6], [7, 8, None]].

Examples

Example 1

Input: [[1, 2, 3], [4, 5, 6], [7, None, 8]]
Output: [[[1, 2, 3], [4, 5, 6], [7, None, 8]], [[1, 2, 3], [4, 5, 6], [7, 8, None]]]
Explanation: Only one move needed - slide tile 8 right into the empty space.

Example 2

Input: [[1, 2, 3], [4, 5, 6], [None, 7, 8]]
Output: [
  [[1, 2, 3], [4, 5, 6], [None, 7, 8]],
  [[1, 2, 3], [4, 5, 6], [7, None, 8]],
  [[1, 2, 3], [4, 5, 6], [7, 8, None]]
]
Explanation: Two moves needed - slide 7 left, then slide 8 right.

Example 3

Input: [[1, 2, 3], [4, None, 5], [7, 8, 6]]
Output: [
  [[1, 2, 3], [4, None, 5], [7, 8, 6]],
  [[1, 2, 3], [4, 5, None], [7, 8, 6]],
  [[1, 2, 3], [4, 5, 6], [7, 8, None]]
]
Explanation: Two moves needed - slide 5 left, then slide 6 up.

Example 4

Input: [[2, 1, 3], [4, 5, 6], [7, 8, None]]
Output: [
  [[2, 1, 3], [4, 5, 6], [7, 8, None]],
  [[1, 2, 3], [4, 5, 6], [7, 8, None]]
]
Explanation: One move needed - slide 1 right to correct position.

Example 5

Input: [[8, 1, 2], [None, 4, 3], [7, 6, 5]]
Output: None (or empty list)
Explanation: This configuration is unsolvable - odd number of inversions.

Solution

Method 1 - BFS with State Representation

Intuition

The 8-puzzle is a classic state-space search problem. We can model each board configuration as a state and use BFS to find the shortest sequence of moves to reach the goal state. Since BFS explores states level by level, the first time we reach the goal state, we've found the optimal solution.

Approach

1. Create a board class to represent the puzzle state and handle operations
2. Convert board states to strings for easy comparison and storage in visited set
3. Use BFS to explore all possible moves from current state
4. For each state, find the empty position and generate all valid moves (up, down, left, right)
5. Track the path to reconstruct the solution sequence
6. Return the path when goal state is reached, or empty list if unsolvable

Code

C++

class PuzzleBoard {
private:
    vector<vector<int>> board;
    int emptyRow, emptyCol;
    
public:
    PuzzleBoard(vector<vector<int>>& initial) : board(initial) {
        findEmpty();
    }
    
    void findEmpty() {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == -1) {  // Using -1 for None
                    emptyRow = i;
                    emptyCol = j;
                    return;
                }
            }
        }
    }
    
    string toString() {
        string result = "";
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                result += to_string(board[i][j]) + ",";
            }
        }
        return result;
    }
    
    vector<PuzzleBoard> getNeighbors() {
        vector<PuzzleBoard> neighbors;
        vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (auto dir : dirs) {
            int newRow = emptyRow + dir.first;
            int newCol = emptyCol + dir.second;
            
            if (newRow >= 0 && newRow < 3 && newCol >= 0 && newCol < 3) {
                vector<vector<int>> newBoard = board;
                swap(newBoard[emptyRow][emptyCol], newBoard[newRow][newCol]);
                PuzzleBoard neighbor(newBoard);
                neighbors.push_back(neighbor);
            }
        }
        
        return neighbors;
    }
    
    bool isGoal() {
        vector<vector<int>> goal = {{1, 2, 3}, {4, 5, 6}, {7, 8, -1}};
        return board == goal;
    }
    
    vector<vector<int>> getBoard() {
        return board;
    }
};

class Solution {
public:
    vector<vector<vector<int>>> solve8Puzzle(vector<vector<int>>& initial) {
        PuzzleBoard start(initial);
        string goal = "1,2,3,4,5,6,7,8,-1,";
        
        queue<PuzzleBoard> q;
        unordered_set<string> visited;
        unordered_map<string, string> parent;
        
        q.push(start);
        visited.insert(start.toString());
        parent[start.toString()] = "";
        
        while (!q.isEmpty()) {
            PuzzleBoard current = q.front();
            q.pop();
            
            if (current.isGoal()) {
                return reconstructPath(current.toString(), parent);
            }
            
            for (PuzzleBoard neighbor : current.getNeighbors()) {
                string neighborStr = neighbor.toString();
                if (visited.find(neighborStr) == visited.end()) {
                    visited.insert(neighborStr);
                    parent[neighborStr] = current.toString();
                    q.push(neighbor);
                }
            }
        }
        
        return {}; // No solution found
    }
    
private:
    vector<vector<vector<int>>> reconstructPath(string goalState, unordered_map<string, string>& parent) {
        vector<vector<vector<int>>> path;
        string current = goalState;
        
        while (current != "") {
            path.push_back(stringToBoard(current));
            current = parent[current];
        }
        
        reverse(path.begin(), path.end());
        return path;
    }
    
    vector<vector<int>> stringToBoard(string boardStr) {
        vector<vector<int>> board(3, vector<int>(3));
        int idx = 0;
        
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                size_t pos = boardStr.find(',', idx);
                board[i][j] = stoi(boardStr.substr(idx, pos - idx));
                idx = pos + 1;
            }
        }
        
        return board;
    }
};

Go

type PuzzleBoard struct {
    board    [][]int
    emptyRow int
    emptyCol int
}

func NewPuzzleBoard(initial [][]int) *PuzzleBoard {
    board := make([][]int, 3)
    for i := range board {
        board[i] = make([]int, 3)
        copy(board[i], initial[i])
    }
    
    pb := &PuzzleBoard{board: board}
    pb.findEmpty()
    return pb
}

func (pb *PuzzleBoard) findEmpty() {
    for i := 0; i < 3; i++ {
        for j := 0; j < 3; j++ {
            if pb.board[i][j] == -1 { // Using -1 for None
                pb.emptyRow = i
                pb.emptyCol = j
                return
            }
        }
    }
}

func (pb *PuzzleBoard) toString() string {
    var result strings.Builder
    for i := 0; i < 3; i++ {
        for j := 0; j < 3; j++ {
            result.WriteString(strconv.Itoa(pb.board[i][j]))
            result.WriteString(",")
        }
    }
    return result.String()
}

func (pb *PuzzleBoard) getNeighbors() []*PuzzleBoard {
    var neighbors []*PuzzleBoard
    dirs := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    
    for _, dir := range dirs {
        newRow := pb.emptyRow + dir[0]
        newCol := pb.emptyCol + dir[1]
        
        if newRow >= 0 && newRow < 3 && newCol >= 0 && newCol < 3 {
            newBoard := make([][]int, 3)
            for i := range newBoard {
                newBoard[i] = make([]int, 3)
                copy(newBoard[i], pb.board[i])
            }
            
            newBoard[pb.emptyRow][pb.emptyCol], newBoard[newRow][newCol] = 
                newBoard[newRow][newCol], newBoard[pb.emptyRow][pb.emptyCol]
            
            neighbors = append(neighbors, NewPuzzleBoard(newBoard))
        }
    }
    
    return neighbors
}

func (pb *PuzzleBoard) isGoal() bool {
    goal := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, -1}}
    for i := 0; i < 3; i++ {
        for j := 0; j < 3; j++ {
            if pb.board[i][j] != goal[i][j] {
                return false
            }
        }
    }
    return true
}

func solve8Puzzle(initial [][]int) [][][]int {
    start := NewPuzzleBoard(initial)
    
    queue := []*PuzzleBoard{start}
    visited := make(map[string]bool)
    parent := make(map[string]string)
    
    visited[start.toString()] = true
    parent[start.toString()] = ""
    
    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        
        if current.isGoal() {
            return reconstructPath(current.toString(), parent)
        }
        
        for _, neighbor := range current.getNeighbors() {
            neighborStr := neighbor.toString()
            if !visited[neighborStr] {
                visited[neighborStr] = true
                parent[neighborStr] = current.toString()
                queue = append(queue, neighbor)
            }
        }
    }
    
    return nil // No solution found
}

func reconstructPath(goalState string, parent map[string]string) [][][]int {
    var path [][][]int
    current := goalState
    
    for current != "" {
        path = append(path, stringToBoard(current))
        current = parent[current]
    }
    
    // Reverse path
    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
        path[i], path[j] = path[j], path[i]
    }
    
    return path
}

func stringToBoard(boardStr string) [][]int {
    board := make([][]int, 3)
    for i := range board {
        board[i] = make([]int, 3)
    }
    
    parts := strings.Split(boardStr, ",")
    idx := 0
    
    for i := 0; i < 3; i++ {
        for j := 0; j < 3; j++ {
            if idx < len(parts) && parts[idx] != "" {
                board[i][j], _ = strconv.Atoi(parts[idx])
            }
            idx++
        }
    }
    
    return board
}

Java

class PuzzleBoard {
    private int[][] board;
    private int emptyRow, emptyCol;
    
    public PuzzleBoard(int[][] initial) {
        this.board = new int[3][3];
        for (int i = 0; i < 3; i++) {
            System.arraycopy(initial[i], 0, this.board[i], 0, 3);
        }
        findEmpty();
    }
    
    private void findEmpty() {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == -1) { // Using -1 for None
                    emptyRow = i;
                    emptyCol = j;
                    return;
                }
            }
        }
    }
    
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                sb.append(board[i][j]).append(",");
            }
        }
        return sb.toString();
    }
    
    public List<PuzzleBoard> getNeighbors() {
        List<PuzzleBoard> neighbors = new ArrayList<>();
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (int[] dir : dirs) {
            int newRow = emptyRow + dir[0];
            int newCol = emptyCol + dir[1];
            
            if (newRow >= 0 && newRow < 3 && newCol >= 0 && newCol < 3) {
                int[][] newBoard = new int[3][3];
                for (int i = 0; i < 3; i++) {
                    System.arraycopy(board[i], 0, newBoard[i], 0, 3);
                }
                
                // Swap empty with adjacent tile
                newBoard[emptyRow][emptyCol] = newBoard[newRow][newCol];
                newBoard[newRow][newCol] = -1;
                
                neighbors.add(new PuzzleBoard(newBoard));
            }
        }
        
        return neighbors;
    }
    
    public boolean isGoal() {
        int[][] goal = {{1, 2, 3}, {4, 5, 6}, {7, 8, -1}};
        return Arrays.deepEquals(board, goal);
    }
    
    public int[][] getBoard() {
        int[][] copy = new int[3][3];
        for (int i = 0; i < 3; i++) {
            System.arraycopy(board[i], 0, copy[i], 0, 3);
        }
        return copy;
    }
}

class Solution {
    public List<int[][]> solve8Puzzle(int[][] initial) {
        PuzzleBoard start = new PuzzleBoard(initial);
        
        Queue<PuzzleBoard> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        Map<String, String> parent = new HashMap<>();
        
        queue.offer(start);
        visited.add(start.toString());
        parent.put(start.toString(), "");
        
        while (!queue.isEmpty()) {
            PuzzleBoard current = queue.poll();
            
            if (current.isGoal()) {
                return reconstructPath(current.toString(), parent);
            }
            
            for (PuzzleBoard neighbor : current.getNeighbors()) {
                String neighborStr = neighbor.toString();
                if (!visited.contains(neighborStr)) {
                    visited.add(neighborStr);
                    parent.put(neighborStr, current.toString());
                    queue.offer(neighbor);
                }
            }
        }
        
        return new ArrayList<>(); // No solution found
    }
    
    private List<int[][]> reconstructPath(String goalState, Map<String, String> parent) {
        List<int[][]> path = new ArrayList<>();
        String current = goalState;
        
        while (!current.equals("")) {
            path.add(stringToBoard(current));
            current = parent.get(current);
        }
        
        Collections.reverse(path);
        return path;
    }
    
    private int[][] stringToBoard(String boardStr) {
        int[][] board = new int[3][3];
        String[] parts = boardStr.split(",");
        int idx = 0;
        
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (idx < parts.length && !parts[idx].isEmpty()) {
                    board[i][j] = Integer.parseInt(parts[idx]);
                }
                idx++;
            }
        }
        
        return board;
    }
}

Python

from collections import deque
from typing import List, Optional, Tuple

class PuzzleBoard:
    def __init__(self, initial: List[List[Optional[int]]]):
        self.board = [row[:] for row in initial]  # Deep copy
        self.empty_row, self.empty_col = self._find_empty()
    
    def _find_empty(self) -> Tuple[int, int]:
        for i in range(3):
            for j in range(3):
                if self.board[i][j] is None:
                    return i, j
        return -1, -1
    
    def __str__(self) -> str:
        return ','.join(str(self.board[i][j]) for i in range(3) for j in range(3))
    
    def get_neighbors(self) -> List['PuzzleBoard']:
        neighbors = []
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        for dr, dc in directions:
            new_row = self.empty_row + dr
            new_col = self.empty_col + dc
            
            if 0 <= new_row < 3 and 0 <= new_col < 3:
                new_board = [row[:] for row in self.board]
                new_board[self.empty_row][self.empty_col] = new_board[new_row][new_col]
                new_board[new_row][new_col] = None
                neighbors.append(PuzzleBoard(new_board))
        
        return neighbors
    
    def is_goal(self) -> bool:
        goal = [[1, 2, 3], [4, 5, 6], [7, 8, None]]
        return self.board == goal
    
    def get_board(self) -> List[List[Optional[int]]]:
        return [row[:] for row in self.board]

class Solution:
    def solve_8_puzzle(self, initial: List[List[Optional[int]]]) -> List[List[List[Optional[int]]]]:
        start = PuzzleBoard(initial)
        
        queue = deque([start])
        visited = {str(start)}
        parent = {str(start): ""}
        
        while queue:
            current = queue.popleft()
            
            if current.is_goal():
                return self._reconstruct_path(str(current), parent)
            
            for neighbor in current.get_neighbors():
                neighbor_str = str(neighbor)
                if neighbor_str not in visited:
                    visited.add(neighbor_str)
                    parent[neighbor_str] = str(current)
                    queue.append(neighbor)
        
        return []  # No solution found
    
    def _reconstruct_path(self, goal_state: str, parent: dict) -> List[List[List[Optional[int]]]]:
        path = []
        current = goal_state
        
        while current != "":
            path.append(self._string_to_board(current))
            current = parent[current]
        
        path.reverse()
        return path
    
    def _string_to_board(self, board_str: str) -> List[List[Optional[int]]]:
        parts = board_str.split(',')
        board = []
        
        for i in range(3):
            row = []
            for j in range(3):
                idx = i * 3 + j
                if idx < len(parts):
                    val = parts[idx]
                    row.append(None if val == 'None' else int(val))
                else:
                    row.append(None)
            board.append(row)
        
        return board

Complexity

• ⏰ Time complexity: O(9!), where 9! represents all possible permutations of the 9 positions. In practice, this is much less due to pruning from the visited set
• 🧺 Space complexity: O(9!), for storing all possible states in the queue and visited set

Method 2 - A* Search with Manhattan Distance Heuristic

Intuition

While BFS guarantees the optimal solution, A* search can find the solution more efficiently by using a heuristic function. The Manhattan distance heuristic estimates how far each tile is from its goal position, providing guidance towards the goal state.

Approach

1. Use Manhattan distance as heuristic: sum of distances each tile is from its target position
2. Implement priority queue with f(n) = g(n) + h(n) where g(n) is moves so far and h(n) is heuristic
3. Always expand the most promising state first
4. Continue until goal state is reached
5. Reconstruct path from goal to start using parent pointers

Code

Python

import heapq
from typing import List, Optional, Tuple

class PuzzleBoardAStar:
    def __init__(self, board: List[List[Optional[int]]], moves: int = 0, parent_state: str = ""):
        self.board = board
        self.moves = moves
        self.parent_state = parent_state
        self.heuristic = self._calculate_manhattan_distance()
        self.empty_row, self.empty_col = self._find_empty()
    
    def _find_empty(self) -> Tuple[int, int]:
        for i in range(3):
            for j in range(3):
                if self.board[i][j] is None:
                    return i, j
        return -1, -1
    
    def _calculate_manhattan_distance(self) -> int:
        distance = 0
        goal_positions = {
            1: (0, 0), 2: (0, 1), 3: (0, 2),
            4: (1, 0), 5: (1, 1), 6: (1, 2),
            7: (2, 0), 8: (2, 1)
        }
        
        for i in range(3):
            for j in range(3):
                if self.board[i][j] is not None and self.board[i][j] != 0:
                    target_row, target_col = goal_positions[self.board[i][j]]
                    distance += abs(i - target_row) + abs(j - target_col)
        
        return distance
    
    def __str__(self) -> str:
        return ','.join(str(self.board[i][j]) for i in range(3) for j in range(3))
    
    def __lt__(self, other):
        return (self.moves + self.heuristic) < (other.moves + other.heuristic)
    
    def get_neighbors(self) -> List['PuzzleBoardAStar']:
        neighbors = []
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        for dr, dc in directions:
            new_row = self.empty_row + dr
            new_col = self.empty_col + dc
            
            if 0 <= new_row < 3 and 0 <= new_col < 3:
                new_board = [row[:] for row in self.board]
                new_board[self.empty_row][self.empty_col] = new_board[new_row][new_col]
                new_board[new_row][new_col] = None
                neighbors.append(PuzzleBoardAStar(new_board, self.moves + 1, str(self)))
        
        return neighbors
    
    def is_goal(self) -> bool:
        goal = [[1, 2, 3], [4, 5, 6], [7, 8, None]]
        return self.board == goal

class Solution:
    def solve_8_puzzle_astar(self, initial: List[List[Optional[int]]]) -> List[List[List[Optional[int]]]]:
        start = PuzzleBoardAStar(initial)
        
        heap = [start]
        visited = {str(start)}
        parent = {str(start): ""}
        
        while heap:
            current = heapq.heappop(heap)
            
            if current.is_goal():
                return self._reconstruct_path(str(current), parent)
            
            for neighbor in current.get_neighbors():
                neighbor_str = str(neighbor)
                if neighbor_str not in visited:
                    visited.add(neighbor_str)
                    parent[neighbor_str] = current.parent_state if current.parent_state else str(start)
                    heapq.heappush(heap, neighbor)
        
        return []  # No solution found
    
    def _reconstruct_path(self, goal_state: str, parent: dict) -> List[List[List[Optional[int]]]]:
        path = []
        current = goal_state
        
        while current != "":
            path.append(self._string_to_board(current))
            current = parent[current]
        
        path.reverse()
        return path
    
    def _string_to_board(self, board_str: str) -> List[List[Optional[int]]]:
        parts = board_str.split(',')
        board = []
        
        for i in range(3):
            row = []
            for j in range(3):
                idx = i * 3 + j
                if idx < len(parts):
                    val = parts[idx]
                    row.append(None if val == 'None' else int(val))
                else:
                    row.append(None)
            board.append(row)
        
        return board

Complexity

• ⏰ Time complexity: O(b^d), where b is branching factor and d is solution depth. Manhattan distance heuristic significantly reduces search space compared to BFS
• 🧺 Space complexity: O(b^d), for storing states in priority queue and visited set

Notes

• This problem is a classic example of the sliding puzzle family, similar to the [Sliding Puzzle](sliding-puzzle) (Leetcode 773) but with a larger 3x3 board
• Not all initial configurations are solvable - the puzzle is solvable if and only if the number of inversions is even
• BFS guarantees the shortest solution, while A* with Manhattan distance heuristic is often faster in practice
• The state space is finite (9! = 362,880 possible states) making exhaustive search feasible