NeFut Logo NeFut
中 Admin Login

Efficient Solving of the N-Puzzle Problem with IDA* Algorithm Analysis and Implementation

Published at: 2026-05-27 09:17 Last updated: 2026-06-06 13:04
#C++ #Tutorial

Core Logic and Mathematical Principles

The essence of the Eight Puzzle and Fifteen Puzzle (N-Puzzle problem) lies in the reachability of permutation groups and the shortest path problem in graph theory. The state space of a $3 \times 3$ board is $9! = 362,880$, which can be handled by ordinary BFS or DFS; however, the state space of a $4 \times 4$ board (Fifteen Puzzle) explodes to $16! \approx 2.09 \times 10^{13}$, causing any blind search algorithm to crash instantly (MLE/TLE).

The IDA (Iterative Deepening A) algorithm serves as an industrial-grade tool to tackle such challenging problems. Its core mathematical principle is based on the triangular inequality scaling of Manhattan distance. For any tile $i$, let its current coordinates be $(cx_i, cy_i)$ and its target coordinates be $(tx_i, ty_i)$. Since each legal directed move (swapping the blank space with its adjacent tiles) can at most bring a tile $1$ unit closer to its target position, the actual number of moves $f_i^*$ required for that tile to reach its target must satisfy:

$$f_i^* \ge |cx_i - tx_i| + |cy_i - ty_i|$$

By summing the scaled distances of all tiles except the blank space, we obtain the global evaluation function $h(x)$:

$$h(x) = \sum_{i=1}^{N^2-1} \left( |cx_i - tx_i| + |cy_i - ty_i| \right)$$

This function strictly satisfies the admissibility condition ($h(x) \le h^*(x)$). In each level of DFS, once it is determined that $dep + h(x) > max\_dep$, the entire exponentially expanding subtree can be instantly pruned.

Additionally, there exists a mathematical theorem regarding parity pruning (inversion count determination):

State Design and Algorithm Derivation

1. Incremental Maintenance of Manhattan Distance ($\Delta h$ Optimization)

If we naively compute $h(x)$ by brute force traversing the matrix at each step during DFS, the complexity per step is $O(N^2)$. A more efficient approach is to observe the local changes before and after the move. When the blank space swaps with the tile $V$ at position $(nx, ny)$:

Thus, the complexity of state transition is successfully reduced to $O(1)$.

2. Duplicate State and Backtracking Deduplication

To prevent the blank space from oscillating between two squares (deadlock), it is necessary to record the last operation direction pre_dir in the parameters passed to DFS. If the current move direction is opposite to pre_dir, it should be intercepted directly.

C++ Standard Source Code

Below is the IDA* high-performance solver implemented for the standard Fifteen Puzzle problem (Luogu variant or classic input).

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

int board[4][4];
int max_dep;
bool success;

// Target coordinate mapping for the Fifteen Puzzle: target_pos[V] = {target_x, target_y}
// Target state: 1 2 3 4 / 5 6 7 8 / 9 10 11 12 / 13 14 15 0
int target_x[16] = {3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3};
int target_y[16] = {3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2};

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

// Calculate the initial Manhattan distance globally
int get_init_heuristic() {
    int h = 0;
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            int val = board[i][j];
            if (val != 0) {
                h += std::abs(i - target_x[val]) + std::abs(j - target_y[val]);
            }
        }
    }
    return h;
}

// Get the count of inversions to determine the reachability of the solution
int get_inversions() {
    int arr[16], cnt = 0;
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            if (board[i][j] != 0) arr[cnt++] = board[i][j];
        }
    }
    int inv = 0;
    for (int i = 0; i < cnt; ++i) {
        for (int j = i + 1; j < cnt; ++j) {
            if (arr[i] > arr[j]) inv++;
        }
    }
    return inv;
}

// dep: current step count, h: current evaluation, cx/cy: current coordinates of the blank space, pre_op: last operation
void idastar_dfs(int dep, int h, int cx, int cy, int pre_op) {
    if (h == 0) {
        success = true;
        return;
    }
    // Critical pitfall: strict use of '+' operation for heuristic absolute limit pruning, avoid logical branches here
    if (dep + h > max_dep) return;

    for (int i = 0; i < 4; ++i) {
        if ((i ^ 1) == pre_op && dep > 0) continue; // XOR operation precisely filters reverse moves

        int nx = cx + dx[i];
        int ny = cy + dy[i];

        if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;

        int val = board[nx][ny];

        // Delta incremental method O(1) update of Manhattan distance
        int old_d = std::abs(nx - target_x[val]) + std::abs(ny - target_y[val]);
        int new_d = std::abs(cx - target_x[val]) + std::abs(cy - target_y[val]);
        int next_h = h - old_d + new_d;

        // State transition
        std::swap(board[cx][cy], board[nx][ny]);

        idastar_dfs(dep + 1, next_h, nx, ny, i);
        if (success) return; // Break recursion, refusing unnecessary backtracking restoration operations

        // State recovery
        std::swap(board[cx][cy], board[nx][ny]);
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int empty_x = 0, empty_y = 0;
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            std::cin >> board[i][j];
            if (board[i][j] == 0) {
                empty_x = i;
                empty_y = j;
            }
        }
    }

    // Preemptively determine unsolvable cases
    int inv = get_inversions();
    // Fifteen Puzzle theorem: the parity of the inversion count + the row number of the blank space (must be unified from bottom to top or top to bottom) must be consistent with the target state
    // Target state: inversion count is 0, the blank space is on the 3rd row (0-indexed), total is 3 (odd)
    if (((inv + empty_x) % 2) != (3 % 2)) {
        std::cout << "-1\n";
        return 0;
    }

    int init_h = get_init_heuristic();
    max_dep = init_h; // Start iterating from the initial heuristic value
    success = false;

    // The problem generally limits the maximum number of steps, such as 45 or 50 steps
    while (!success && max_dep <= 50) {
        idastar_dfs(0, init_h, empty_x, empty_y, -1);
        if (success) break;
        max_dep += 2; // Key optimization: each move in the puzzle changes the parity of the step count, limits can be incremented in pairs
    }

    if (success) std::cout << max_dep << "\n";
    else std::cout << "-1\n";

    return 0;
}

NOIP Practical Pitfall Guide

  1. Blindly incrementing max_dep++ leads to redundant iterations In the puzzle problem, every tile in the grid changes its Manhattan distance by $+1$ or $-1$ with each move. That is to say, every legal move will change the overall parity of the total Manhattan distance of the entire board. Therefore, if the shortest path from the initial state to the target state is an odd number of steps, it is absolutely impossible to have an even-numbered limit in between. When increasing the limit in iterative deepening, it should be max_dep += 2. If written as max_dep++, it will cause the algorithm to perform a complete DFS search on step levels that are completely impossible to yield a solution, doubling the time complexity and leading to TLE.
  2. Including the blank space $0$ in the cost during incremental $h(x)$ updates This is a typical low-level error that many seasoned competitors have learned the hard way. When performing the Delta update next_h = h - old_d + new_d, the variable val must not take the value of the blank space (0). Because in modeling, since the movement of the blank space is accompanied by the movement of other tiles, we only care about the true positioning distance of the non-$0$ valued tiles. If the movement of 0 is also counted in the Manhattan distance, the entire evaluation function will no longer satisfy admissibility (it will exceed the actual shortest cost), thus causing IDA* to miss the optimal solution or fail to produce the correct answer.

Classic NOIP/Luogu Problems

1. Luogu P1379 Eight Puzzle Problem

2. Luogu P2325 [SCOI2005] Knight's Spirit

Original Source: local://4.4
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS