8-Puzzle Solver
Updated
Problem statement
The 8-puzzle is a 3 x 3 board with eight numbered tiles, 1 to 8, and one empty square. You are given the board as board, where 0 marks the empty square.
In one move, you slide a tile that is directly above, below, left or right of the empty square into it. The tile's old square becomes the new empty square.
The puzzle is solved when the board is [[1,2,3],[4,5,6],[7,8,0]]: the tiles are in order row by row, and the empty square is in the bottom-right corner.
Return the fewest moves needed to solve the puzzle. If it cannot be solved, return -1.
Function
slidingPuzzle(board: int[][]) → intExamples
Example 1
board = [[1,2,3],[4,5,6],[0,7,8]]return = 2The empty square is in the bottom-left corner. Slide tile 7 left into it, then slide tile 8 left. The bottom row becomes 7, 8 and the empty square, which is the goal.
Example 2
board = [[1,2,3],[5,0,6],[4,7,8]]return = 4Slide tile 5 right into the empty center, then tile 4 up, tile 7 left and tile 8 left. Each move takes the empty square one step: left, down, right and right again, ending in the bottom-right corner with every tile in place. Each of the four moves is needed, because tiles 4, 5, 7 and 8 each start one square away from their goal square, and a move shifts only one tile.
Example 3
board = [[1,2,3],[4,5,6],[8,7,0]]return = -1Only tiles 7 and 8 are out of place, and they are swapped. Read the tiles row by row and count the pairs that are in the wrong order: here only the pair 8, 7 is, so the count is 1. A sideways move does not change the reading order, and an up or down move jumps one tile over two others, which changes the count by 0 or 2. So the count stays odd forever, while the goal has a count of 0. The goal cannot be reached.
Constraints
board.length == 3board[i].length == 30 <= board[i][j] <= 8- Each value from
0to8appears inboardexactly once.
More Airbnb Phone Screen questions
- Read Across Sound TracksPHONE SCREEN · Seen Nov 2026
- Text JustificationPHONE SCREEN · Seen Nov 2026
- Decode and Store StringsPHONE SCREEN · Seen Oct 2026
- Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Detonate Bombs with Chain ReactionsPHONE SCREEN · Seen Aug 2026
- Smallest Common RegionPHONE SCREEN · Seen Aug 2026
- Longest Chain BookingPHONE SCREEN · Seen Aug 2026
- Nested List Iterator with RemovePHONE SCREEN · Seen Jul 2026
- Parse Query StringPHONE SCREEN · Seen May 2026
- Pacific Atlantic Water FlowPHONE SCREEN · Seen May 2023
Similar questions at other companies
- Find the Safest Path in a GridAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Shortest Distance from All BuildingsWaymo · PHONE SCREENWaymo interview questions
- Trapping Rain Water IIBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Max Area of Island Without Changing the GridFlexport · PHONE SCREENFlexport interview questions
- Process Minesweeper Game OperationsAmperity · PHONE SCREENAmperity interview questions
- Count Islands in a Binary GridApple · PHONE SCREENApple interview questions
- Find and Reconstruct a Binary-Matrix PathMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Pacific Atlantic Water FlowAnduril · PHONE SCREENAnduril interview questions
- House Bounds in a Ragged GridRippling · OA · PHONE SCREENRippling interview questions
- Nearest Reachable Grid CornerSplunk · PHONE SCREENSplunk interview questions
Interview reports that mention this question
Airbnb interview experiences
- Airbnb SWE OA: Four-Level Banking System: 1 Experience
- Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
- Airbnb Intern Phone Interviews: 21 Experiences (Part 7 of 7)
- Airbnb Intern OA and Phone Screens: 17 Experiences (Part 6 of 7)
- Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)