How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Find minimum moves to solve the 15-puzzle | Microsoft Coding Question

Quick Overview

This question evaluates understanding of state-space search, heuristic reasoning, and solvability analysis for combinatorial sliding puzzles, testing algorithm design and optimization within the Coding & Algorithms domain at a practical application level with required conceptual understanding of search-space properties.

PracHub

Questions Premium Coaches Learning Guides Interview Prep

Quick Overview

hard
Microsoft
Coding & Algorithms
Software Engineer

Find minimum moves to solve the 15-puzzle

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

## Problem Given a 4×4 sliding puzzle (the classic **15-puzzle**), compute the **minimum number of moves** required to reach the solved state, or return `-1` if it is impossible. - The board contains numbers `1..15` and a blank represented by `0`. - A move consists of swapping `0` with one of its 4-directional neighbors (up/down/left/right). ### Input A 4×4 integer matrix `board`. ### Output An integer `minMoves`: - the minimum number of moves to reach the target state, or - `-1` if the target state is unreachable. ### Target state ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ``` ### Constraints/Notes - You must handle unsolvable configurations. - Aim for an approach that can finish in reasonable time for typical interview test cases (e.g., using an informed search such as A* rather than naive BFS over the full state space).

Quick Answer: This question evaluates understanding of state-space search, heuristic reasoning, and solvability analysis for combinatorial sliding puzzles, testing algorithm design and optimization within the Coding & Algorithms domain at a practical application level with required conceptual understanding of search-space properties.

Return the minimum moves from a 4x4 sliding puzzle board to the solved state, or -1 if unsolvable.

Constraints

board is a 4x4 permutation of 0..15

Examples

Input: ([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]],)

Expected Output: 0

Explanation: Already solved.

Input: ([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 0, 15]],)

Expected Output: 1

Explanation: One move away.

Input: ([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 15, 14, 0]],)

Expected Output: -1

Explanation: Unsolvable parity.

Hints

Use parity to reject impossible boards, then A* with Manhattan distance.

Last updated: Jun 27, 2026