7.5.3八数コードの問題

bfs図の場合は判定に注意する必要があります.
八数コード状態数9!=362880、9次元のvisを使うと、9^9=387420489と、かなり無駄になります.
スペースの無駄を解決するには、次の3つの方法があります.
1、符号化復号
ここではcantorで符号化

typedef int State[9];
const int MAXSTATE = 1000000;
State st[MAXSTATE], goal;
int dist[MAXSTATE];

int vis[362880], fact[9];
void init_lookup_table() {
  fact[0] = 1;
  for(int i = 1; i < 9; i++) fact[i] = fact[i-1] * i;
}
int try_to_insert(int s) {
  int code = 0;
  for(int i = 0; i < 9; i++) {
    int cnt = 0;
    for(int j = i+1; j < 9; j++) if(st[s][j] < st[s][i]) cnt++;
    code += fact[8-i] * cnt;
  }
  if(vis[code]) return 0;
  return vis[code] = 1;
}

2、hash
3、STLのset
setは<演算子を定義する必要があります