# 773. Sliding Puzzle

![](/files/bFswF5kLAhUDjbjJXgdh)

![](/files/2pMgIwqY7IlNZQSOcilw)

![](/files/k3CyffyC1DCr5Yzj19sb)

## BFS - grid data convert to String format

```
/*
grid convert to String format:
ex: 

[[1,2,3],[4,5,0]]. => 123450

[[1,2,3],[4,0,5]]. => 123405

use bfs, find  least number of moves 
=> change 4 direction, 

[[1,2,3],
[4,0,5]]. => when 5 swap with 0 => achieve 123450


if can achieve 123450 => return steps

*/
```

2\*3 = 6, 6! permutation of the 6 numbers, 

T: O(mn + mn\*(mn!)), 

S:O(mn + mn!)

```java
class Solution {
    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    public int slidingPuzzle(int[][] board) {
        String s = "";
        for (int i = 0 ; i < board.length; i++) { // transform to String format, inorder to check result easier
            for (int j = 0; j < board[0].length; j++) {
                s += board[i][j];
            }
        }
        if ("123450".equals(s)) { //find ans
            return 0;
        }
        
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new ArrayDeque<>();
        queue.offer(s);
        visited.add(s);
        
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();
                
                if ("123450".equals(curr)) { //find ans
                    return steps;
                }
                
                int index = curr.indexOf('0'); // find '0' index , easier!
                
                int x = index/3; // String index to x, y index
                int y = index%3;
                for (int dir[] : dirs) {
                    int newX = x + dir[0];
                    int newY = y + dir[1];
                    
                    if (!inArea(board, newX, newY)) {
                        continue;
                    }
                    int newIndex = newX*3 + newY; // new String index
                    String newString = swap(curr, index, newIndex); // get new String
                    if (visited.contains(newString)) {
                        continue;
                    }
                    queue.offer(newString);
                    visited.add(newString);
                }
            }
            steps++;
        }
        
        return -1;
    }
    private boolean inArea(int[][] board, int i, int j) {
        return (i >= 0 && i < board.length && j >= 0 && j < board[0].length);
    }
    
    private String swap(String s, int i, int j) {
        char[] charArray = s.toCharArray();
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }
    // or direct change
    // private String swap(String s, int index, int newIndex) {
    //     char[] charArray = s.toCharArray();
    //     charArray[index] = charArray[newIndex];
    //     charArray[newIndex] = '0';
    //     return String.valueOf(charArray);
    // }
}

//  6! permutation of the 6 numbers, 2*3 = 6
// T: O(mn + mn*(mn!)), S:O(mn + mn!)
// do dfs

// encode board to String

// 123450

// bfs from 0
// so find 0's index, 
    
// bfs from 0 for 4 directions, visited<String> to store visited

// if (string == '123450') return steps
```

### pre calculate the swap position && new style BFS

key:

1. how to define the final state? in\[]\[] to String
2. how to define the move?

visited use Set\<String>, for certain String pattern, we have visited...

````java
```java
class Solution {
    class Step {
        String state;
        int emptyIndex;
        int count;
        Step(String state, int emptyIndex, int count) {
            this.state = state;
            this.emptyIndex = emptyIndex;
            this.count = count;
        }
    }
    public int slidingPuzzle(int[][] board) {
        // empty place's neightbor, we can use to swap later
        int[][] swap = {{1,3},{0,4,2},{1,5},{0,4},{1,3,5},{2,4}};
        StringBuilder state = new StringBuilder();
        int k = 0;
        int emptyIndex = -1;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 0) {
                    emptyIndex = k;
                }
                state.append(board[i][j]);
                k++;
            }
        }
        Set<String> visited = new HashSet<>();
        Queue<Step> queue = new LinkedList<>();
        queue.offer(new Step(state.toString(), emptyIndex, 0));

        while (!queue.isEmpty()) {
            Step cur = queue.poll();

            if (visited.contains(cur.state)) {
                continue;
            }
            if ("123450".equals(cur.state)) {
                return cur.count;
            }
            visited.add(cur.state);
            for (int position : swap[cur.emptyIndex]) {
                String nextStr = swap(cur.state, position, cur.emptyIndex);
                queue.offer(new Step(nextStr, position, cur.count+1));
            }
        }
        return -1;
    }
    private String swap(String s, int i, int j) {
        char[] c = s.toCharArray();
        char temp = c[i];
        c[i] = c[j];
        c[j] = temp;
        return String.valueOf(c);
    }
}
/*

0 1 2
3 4 5 -> 0 1 2 3 4 5

{1,3}
{0,4,2}
{1,5}
{0,4}
{1,3,5}
{2,4}




*/
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/773.-sliding-puzzle.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.