#include <bits/stdc++.h>

using namespace std;

char grid[12][12], buffer[12][12];
map<string, int> visited;
map<string, string> parents;

string grid_to_str(void) {
    char str[12];
    int k = 0;
    for(int i = 1; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j)
            str[k++] = buffer[i][j];
    str[k] = 0;
    return str;
}

void str_to_grid(string str) {
    memset(grid, -1, sizeof grid);
    for(int i = 1, k = 0; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j)
            grid[i][j] = str[k++];
}

vector<int> versor{-1, 1, 0};
void bfs(string source, string destiny) {
    queue<string> q;
    q.push(source);
    visited[source] = 1;
    parents[source] = source;
    bool result = false;
    while(q.empty() == 0) {
        string current = q.front();
        q.pop();
        str_to_grid(current);
        for(int i = 1; i <= 3; ++i) {
            for(int j = 1; j <= 3; ++j) {
                if(grid[i][j] == '0') {
                    for(int m : versor) {
                        for(int n = 1; n >= -1; --n) {
                            if(abs(m + n) == 1 && grid[i + m][j + n] != -1) {
                                memcpy(buffer, grid, sizeof grid);
                                buffer[i][j] = buffer[i + m][j + n];
                                buffer[i + m][j + n] = '0';
                                if(visited[grid_to_str()] == 0) {
                                    visited[grid_to_str()] = 1;
                                    parents[grid_to_str()] = current;
                                    if(grid_to_str() == destiny) {
                                        result = true;
                                        goto end_loop;
                                    }
                                    q.push(grid_to_str());
                                }
                            }
                        }
                    }
                }
            }
        }
    }
end_loop:;
    if(!result) {
        printf("Problema sem solucao\n");
        return;
    }

    stack<string> s;
    string str = grid_to_str();
    while(parents[str] != str) {
        s.push(str);
        str = parents[str];
    }

    printf("Quantidade minima de passos = %d\n", s.size());
    bool status = false;
    while(s.empty() == 0) {
        string v = s.top();
        s.pop();
        str_to_grid(v);
        if(status == false) { status = true; } else { printf("\n"); }
        for(int i = 1; i <= 3; ++i) {
            for(int j = 1; j <= 3; ++j) {
                printf("%c", grid[i][j]);
            }
            printf("\n");
        }
    }
}

int main(void) {
begin:;
    memset(buffer, -1, sizeof buffer);
    for(int i = 1; i <= 3; ++i) {
        for(int j = 1; j <= 3; ++j) {
            buffer[i][j] = getchar();
            if(buffer[i][j] == -1)
                goto end;
        }
        getchar();
    }

    bfs(grid_to_str(), "123456780");
    visited.clear();
    parents.clear();
    goto begin;
end:;

    return 0;
}