Last Updated: 23 Mar, 2021

Sliding Puzzle

Hard
Asked in companies
AppleFacebookUber

Problem statement

On a 2 x 3 ‘BOARD,’ there are five tiles represented by the integers 1 through 5 and an empty square represented by 0. A move consists of choosing 0 and a 4-directionally adjacent number and swapping it. The state of the board is solved if and only if the ‘BOARD’ is [[1,2,3],[4,5,0]].

Given a puzzle board, return the least number of ‘moves’ required to solve the state of the board. If it is impossible for the state of the board to be solved, return -1.

Note:

Board will be a 2 x 3 array as described above.

BOARD[i][j] will be a permutation of [0, 1, 2, 3, 4, 5].

For example:

Given ‘BOARD’ = [[1,2,0],[4,5,3]]
The answer here would be one since we only need to swap 0 and 3, and we will have the required configuration.

Input format:

The first line of input contains an integer T denoting the number of test cases.

The following 2*T lines of each test case contain the ‘BOARD’, where each line has exactly three space-separated integers.

Output format :

For each test case, print a single line containing a single integer denoting the minimum number of swaps for the given board. 

The output of each test case will be printed in a separate line.

Note :

You don't have to print anything. It has been already taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
0 <= BOARD[i][j] <= 5 

Where ‘T’ is the total number of test cases, and ‘BOARD’ matrix and ‘BOARD’[i][j] is the value of pairs (i,j).

Time limit: 1 sec.

Approaches

01 Approach

The main idea is to do all the possible swaps we can do, and if we find the required configuration, we return the number of moves we made to get to this state.If we ever encounter a state we have already encountered, we can skip that state.

  • Make a queue(que) which, for each state, stores the number of moves we have made till now and also the current state of the board.

 

  • Maintain a hashmap(mp) that stores all the states that we have previously encountered.

 

  • If we come to a state we have not encountered before, we make the swap and then push it in the que.

 

  • If at any point we get the required board, we return the number of moves we have made till now.

 

  • If we never encounter the required board, we return -1.