世界中の全商品をたった「6桁の数字」で分類するHSコードと、15パズル（グラフ理論）で動く自動倉庫ロボットの数理とは？

#![forbid(unsafe_code)]

/// Verifies whether a 4x4 15-puzzle board configuration (0 = blank tile) is mathematically
/// solvable to the standard goal state `[1, 2, ..., 15, 0]` via Alternating Group A_15 parity.
#[inline]
pub fn is_solvable_15_puzzle(board: &[u8; 16]) -> bool {
    let mut inversions: u32 = 0;
    let mut blank_row_from_bottom: u32 = 1;

    for i in 0..16 {
        let tile_i = board[i];
        if tile_i == 0 {
            blank_row_from_bottom = 4 - (i as u32 / 4);
            continue;
        }
        for j in (i + 1)..16 {
            let tile_j = board[j];
            if tile_j != 0 && tile_i > tile_j {
                inversions += 1;
            }
        }
    }
    // For an even-width grid (W=4), solvable to goal iff (inversions + blank_row_from_bottom) is odd
    (inversions + blank_row_from_bottom) % 2 == 1
}

/// Computes the admissible Manhattan Distance + Linear Conflict heuristic for IDA* search.
#[inline]
pub fn manhattan_plus_linear_conflict(board: &[u8; 16]) -> u32 {
    let mut dist: u32 = 0;
    for (idx, &tile) in board.iter().enumerate() {
        if tile == 0 {
            continue;
        }
        let target_idx = (tile - 1) as usize;
        let (r, c) = (idx / 4, idx % 4);
        let (tr, tc) = (target_idx / 4, target_idx % 4);
        dist += r.abs_diff(tr) as u32 + c.abs_diff(tc) as u32;
    }
    // Add +2 moves for each row-wise linear conflict
    for row in 0..4 {
        for c1 in 0..4 {
            let t1 = board[row * 4 + c1];
            if t1 == 0 || ((t1 - 1) as usize / 4) != row {
                continue;
            }
            for c2 in (c1 + 1)..4 {
                let t2 = board[row * 4 + c2];
                if t2 != 0 && ((t2 - 1) as usize / 4) == row && t1 > t2 {
                    dist += 2;
                }
            }
        }
    }
    dist
}