BOJ 17492

#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 10
typedef pair<int,int> P;

int map[MAXN][MAXN];
int N;
P coord[MAXN];
int dx[] = {-1,-1,-1,0,0,1,1,1};
int dy[] = {-1,0,1,-1,1,-1,0,1};
int idx;
bool ans;
bool is_range(int x, int y){
    return (x>=0 && y >= 0 && x < N && y < N);
}
void simulate(int cnt){
    if (ans) return;
    if (cnt == idx-1){
        ans = true;
        return;
    }
    for (int i = 1; i <= idx; i++){
        // 바둑알이 제거된 것은 좌표를 -1로 두어 표시하였습니다.
        if (coord[i].first == -1) continue;
        int x = coord[i].first;
        int y = coord[i].second;
        for (int j = 0; j < 8; j++){
            int nx = x + dx[j];
            int ny = y + dy[j];
            if (!is_range(nx,ny)) continue;
            int nx1 = nx + dx[j];
            int ny1 = ny + dy[j];
            if (map[nx][ny]>0 && is_range(nx1,ny1)&& map[nx1][ny1]==0){
                P tmp_coord = coord[map[nx][ny]];
                coord[map[x][y]] = {nx1,ny1};
                coord[map[nx][ny]] = {-1,-1};
                int next_num = map[nx][ny];
                int cur_num = map[x][y];
                map[nx1][ny1] = map[x][y];
                map[nx][ny] = 0;
                map[x][y] = 0;
                simulate(cnt+1);
                map[nx1][ny1] = 0;
                map[x][y] = cur_num;
                map[nx][ny] = next_num;
                coord[cur_num] = {x,y};
                coord[next_num] = tmp_coord;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i= 0; i<N; i++){
        for (int j = 0;j<N; j++){
            cin >> map[i][j];
            if (map[i][j]==1) map[i][j] = -1;
            else if (map[i][j] ==2) {
                map[i][j] = ++idx;
                coord[idx] = {i,j};
            }
        }
    }
    simulate(0);
    cout << ((ans==true)? "Possible":"Impossible") <<"\n";
    return 0;
}