P1379 八數碼難題

八數碼難題首先要進行有解性判定，避免無解情況下盲目搜索浪費時間。

有解性判定

P10454 奇數碼問題

題意簡述

在一個 $n\times n$ 的網格中進行，其中 $n$ 為奇數，$1$ 個空格和 $[1,n^2?1]$ 這 $n^2?1$ 個數不重不漏地分布在網格中。空格可與上下左右的數字交換位置。現給定兩個奇數碼游戲的局面，判定是否存在一種移動空格的方式使得互相可達。

實際上，八數碼問題就是一個 $n=3$ 的奇數碼游戲。

思路

將網格圖轉為長為 $n^2?1$ 的一維序列，例如：

5 2 8
1 3 _
4 6 7

可記為 $5,2,8,1,3,4,6,7$ ，忽略空格。可以發現：若左右移動空格，該序列不變；若上下移動空格，例如：

5 2 _
1 3 8
4 6 7

序列變為 $5,2,1,3,8,4,6,7$ ，相當于把 $8$ 往前移動了 $n?1=2$ 位，有兩個數字到了 $8$ 的后面，那么這兩個數字中，原來與 $8$ 形成逆序對的變成了非逆序對，原來與 $8$ 形成非逆序對的變成了逆序對。

進一步思考：

1.若在位置發生變動的數中原有奇數個逆序對，由于 $n?1$ 是偶數，那么原來也有奇數個非逆序對，因此交換后逆序對的個數仍為奇數；

2.若在位置發生變動的數中原有偶數個逆序對，由于 $n?1$ 是偶數，那么原來也有偶數個非逆序對，因此交換后逆序對的個數仍為偶數。

綜上所述，無論怎么交換，逆序對個數的奇偶性不變，因此可以比較初狀態和末狀態的逆序對（用樹狀數組統計）奇偶性是否相同，方可判定是否有解。

代碼實現

注意 $0$ 不參與統計，忘了這一點會 WA。

#include <bits/stdc++.h>using namespace std;int n;int lowbit(int p){return p & (-p);}void insert(int p,int x,vector <int>& c){for(;p <= n;p += lowbit(p))c[p] += x;
} int query(int p,vector <int>& c){int sum = 0;for(;p;p -= lowbit(p)) sum += c[p];return sum;
}int main(){ios::sync_with_stdio(0);cin.tie(0);while(cin >> n){n = n * n; vector <int> c(n + 1,0);int x,ans1,ans2,cnt1,cnt2;cnt1 = cnt2 = ans1 = ans2 = 0;for(int i = 1;i <= n;i++){cin >> x;if(!x) continue;cnt1++;insert(x,1,c);ans1 += cnt1 - query(x,c);}for(int i = 0;i <= n;i++) c[i] = 0;for(int i = 1;i <= n;i++){cin >> x;if(!x) continue;cnt2++; insert(x,1,c);ans2 += cnt2 - query(x,c);}	if(ans1 % 2){if(ans2 % 2) cout << "TAK" << endl;else cout << "NIE" << endl;}else{if(ans2 % 2) cout << "NIE" << endl;else cout << "TAK" << endl;}}return 0;
}

A-star

其實本題不需要可行性判定，但學一下也無妨。

設計估價函數 $h(state)$ 表示當前狀態所有數字與其目標位置的曼哈頓距離和，即：
$$h(state)=\sum _{i=1}^8\left|x_i?x_{target}\right|+\left|y_i?y_{target}\right|$$
顯然實際操作數 $g(state)\ge h(state)$ ，因為 $h$ 表示每個數字去目標點都走最短路，而實際至少得走這么遠，$h$ 函數可采納且較接近真實值（相比之下“錯位數”，即不在目標位置的數字個數，這一估價函數雖可采納但大多數時候遠小于真實值，求解效率低），最終入隊的總代價即為 $f=g+h$ 。

代碼實現

#include <bits/stdc++.h>using namespace std;const string TARGET = "123804765";
const int dx[] = {0,0,-1,1};
const int dy[] = {-1,1,0,0};struct Node{string state;int g,h,f;Node(string s,int _g,int _h) :state(s),g(_g),h(_h),f(_g + _h) {}//重載運算符bool operator < (const Node& other) const {return f > other.f;} 
};//預處理target狀態坐標
void initTargetPos(unordered_map <char,int>& pos_map){for(int i = 0;i < 9;i++){char c = TARGET[i];if(c != '0') pos_map[c] = i;}
} //函數求曼哈頓距離和 
int mahattan(const string& state,const unordered_map <char,int>& pos_map){int distance = 0;for(int i = 0;i < 9;i++){char c = state[i];if(c == '0') continue;int target_pos = pos_map.at(c);//當前數字坐標 int cur_x = i % 3;int cur_y = i / 3;//目標位置坐標 int tar_x = target_pos % 3;int tar_y = target_pos / 3;distance += abs(cur_x - tar_x) + abs(cur_y - tar_y);}return distance;
}int A_star(string start){if(start == TARGET) return 0;//預處理目標位置 unordered_map <char,int> pos_map;initTargetPos(pos_map);priority_queue <Node> open_list;unordered_map <string,int> min_cost;int start_h = mahattan(start,pos_map);open_list.push(Node(start,0,start_h));min_cost[start] = 0;while(!open_list.empty()){Node cur = open_list.top();open_list.pop();string state = cur.state;if(state == TARGET) return cur.g;//非最優路徑則跳過if(min_cost[state] < cur.g) continue;//找出0的位置 int pos = state.find('0');int x = pos % 3;int y = pos / 3;for(int i = 0;i < 4;i++){int tx = x + dx[i];int ty = y + dy[i];//越界 if(tx < 0 || tx >= 3 || ty < 0 || ty >= 3) continue;//0的新坐標 int new_pos = tx + ty * 3;string new_state = state;swap(new_state[pos],new_state[new_pos]);int new_g = cur.g + 1;//未曾入隊或有更優解 if(min_cost.find(new_state) == min_cost.end() || new_g < min_cost[new_state]){min_cost[new_state] = new_g;int new_h = mahattan(new_state,pos_map);open_list.push(Node(new_state,new_g,new_h));} }}
}int main(){ios::sync_with_stdio(0);cin.tie(0);string start;cin >> start;cout << A_star(start) << endl;return 0;
}