Sliding Puzzle

Hard
0/120
Average time to solve is 45m
profile
Contributed by
3 upvotes
Asked in companies
UberFacebookApple

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.
Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

2
1 2 0 
4 5 3
1 2 3 
5 4 0

Sample Output 1:

1
-1

Explanation of the Sample Input 1:

For the first test case:
The answer here would be 1 since we only need to swap 0 and 3, and we will have the required configuration.


For the second test case:
No number of moves will make the board solve.

Sample Input 2 :

2
2 1 3 
4 5 0
2 1 3
5 4 0

Sample Output 2 :

-1
14
Hint

Will BFS help?

Approaches (1)
USE BFS

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.
Time Complexity

O( 1 ). 

 

Since the board has 2 rows and 3 columns therefore at max we would be exploring all the permutations of 0,1,2,3,4,5,6. Therefore the net time complexity will be 6!, which is constant time. 

Space Complexity

O( 1 ). 

 

Since the board has 2 rows and 3 columns therefore at max we would be exploring and storing all the permutations of 0,1,2,3,4,5,6. Therefore the net space complexity will be 6!, which is constant space. 

Code Solution
(100% EXP penalty)
Sliding Puzzle
Full screen
Console