#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int N;

struct square{
    char box[20][20];
};

struct puzzle{
    square state;
    int steps;
    vector<square> route;
    int xk,yk; //sintetagmenes tou kenou
};

bool is_done(square x){
    int num=1;
    bool ok=1;
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            if ((i==N-1)&&(j==N-1)){
                num=0;
            }
            if (x.box[i][j]!=num+'0'){
                ok=0;
            }
            num++;
        }
    }
    return ok;
}

void print(square x){
    cout << endl;
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            cout << x.box[i][j];
        }
        cout << endl;
    }
}


int main()
{
    cout << "Dose mou to mikos mias pleuras tou puzzle"<<endl;
    cin >> N;
    cout << "Dose mou to puzzle (sti 8esi tou kenou dose 0)"<< endl;

    square a;
    int x,y;
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            cin >> a.box[i][j];
            if (a.box[i][j]=='0'){
                x=i;
                y=j;
            }
        }
    }

    puzzle init;
    init.state=a;
    init.steps=0;
    init.route.push_back(a);
    init.xk=x;
    init.yk=y;

    queue<puzzle> q;
    q.push(init);
    bool ok=0;
    puzzle temp1,temp2;
    int moves=0;

    while ((!q.empty())&&(ok==0)){
        temp1=q.front();
        q.pop();
        if ((temp1.xk==N-1)&&(temp1.yk==N-1)){ //elegxw an to puzzle lithike
            if (is_done(temp1.state)){
                ok=1;
                cout<< endl <<"H lisi vre8ike se: "<< temp1.steps<<" vimata" << endl;
                for (int i=0;i<temp1.route.size();i++){
                    print(temp1.route[i]);
                }
            }
        }

        if (ok==0){ //an dn li8ike prepei na proxwrisw se epomeni katastasi
            if (temp1.xk<N-1){ //mporw na metakinisw ena tetragwnaki pros ta panw
                temp2.state=temp1.state;
                temp2.state.box[temp1.xk][temp1.yk]=temp2.state.box[temp1.xk+1][temp1.yk]; //metakinw to koutaki
                temp2.state.box[temp1.xk+1][temp1.yk]='0';
                temp2.steps=temp1.steps+1;
                temp2.route=temp1.route;
                temp2.route.push_back(temp2.state);
                temp2.xk=temp1.xk+1;
                temp2.yk=temp1.yk;
                q.push(temp2);
            }
            if (temp1.xk>0){ //mporw na metakinisw ena tetragwnaki pros ta katw
                temp2.state=temp1.state;
                temp2.state.box[temp1.xk][temp1.yk]=temp2.state.box[temp1.xk-1][temp1.yk]; //metakinw to koutaki
                temp2.state.box[temp1.xk-1][temp1.yk]='0';
                temp2.steps=temp1.steps+1;
                temp2.route=temp1.route;
                temp2.route.push_back(temp2.state);
                temp2.xk=temp1.xk-1;
                temp2.yk=temp1.yk;
                q.push(temp2);
            }
            if (temp1.yk<N-1){ //mporw na metakinisw ena tetragwnaki pros ta aristera
                temp2.state=temp1.state;
                temp2.state.box[temp1.xk][temp1.yk]=temp2.state.box[temp1.xk][temp1.yk+1]; //metakinw to koutaki
                temp2.state.box[temp1.xk][temp1.yk+1]='0';
                temp2.steps=temp1.steps+1;
                temp2.route=temp1.route;
                temp2.route.push_back(temp2.state);
                temp2.xk=temp1.xk;
                temp2.yk=temp1.yk+1;
                q.push(temp2);
            }
            if (temp1.yk>0){ //mporw na metakinisw ena tetragwnaki pros ta deksia
                temp2.state=temp1.state;
                temp2.state.box[temp1.xk][temp1.yk]=temp2.state.box[temp1.xk][temp1.yk-1]; //metakinw to koutaki
                temp2.state.box[temp1.xk][temp1.yk-1]='0';
                temp2.steps=temp1.steps+1;
                temp2.route=temp1.route;
                temp2.route.push_back(temp2.state);
                temp2.xk=temp1.xk;
                temp2.yk=temp1.yk-1;
                q.push(temp2);
            }
        }
    }

    return 0;
}