八数码难题
2021-01-07 18:02阅读：
八数码难题 P1379/BD358
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入格式
输入初始状态，一行九个数字，空格用0表示
输出格式
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
输入 #1复制
283104765
输出 #1复制
4
奇偶性考察：
对于给定八数码棋局的初始状态，我们的目标是通过交换空格与其相邻棋子使棋盘达到目标状态。
其中，游戏规则是只能交换空格与其上下左右四个方向的相邻棋子。
假设棋局目标状态为如下形式：（A、B、C、D、E、F、G、H表示棋子）
A B C
D E F
G H
而初始状态就是A、B、C、D、E、F、G、H这八个棋子在这九个棋格上的任意分布。
并且我们对棋盘中每个棋格进行如下形式的编号：
1 2 3
4 5 6
7 8 9
那么，对于一个任意的棋局状态，我们可以取得这八个棋子（A、B、C、D、E、F、G、H）的一个数列：棋子按照棋格的编号依次进行排列，记为p=c[1]c[2]c[3]c[4]c[5]c[6]c[7]c[8]（即A、B、C、D、E、F、G、H的一个排列）。
在分析之前，先引进逆序和逆序数的概念：对于棋子数列中任何一个棋子c[i]（1≤i≤8），如果有j>i且c[j] <
c[i]，那么 c[j]是c[i]的一个逆序，或者
c
i]和c[j]构成一个逆序对。定义棋子c[i]的逆序数为c[i]的逆序个数；棋子数列的逆序数为该数列所有棋子的逆序数总和。注：约定A
< B < C < D < E < F < G < H。
现在，我们对一个任意的棋局状态p=c[1]c[2]c[3]c[4]c[5]c[6]c[7]c[8]进行分析：
引理1：如果交换任何两个相邻的棋子，那么棋子数列的逆序数将发生奇偶性互变（奇偶性互变是指由奇数变为偶数，或由偶数变为奇数，下同）。
其证明很简单，假设交换的是c[i]和c[i+1]，那么对于c[j]（1≤j≤i-1或i+2≤j≤8）的逆序数并不改变。若交换之前
c[i] <
c[i+1]，那么交换之后，c[i]的逆序数不变，而c[i+1]的逆序数加1（因为c[i]成了它的一个逆序）；同理，若交换之前
c[i]>c[i+1]，那么交换之后，c[i]的逆序数减1，而c[i+1]的逆序数不变。所以，引理1成立。
引理2：如果棋子数列经过n次相邻棋子交换后，若n为偶数，则数列逆序数奇偶性不变；若n为奇数，则数列逆序数将发生奇偶性互变。
其证明可以由引理1简单推出。
引理3：在满足上述约定的八数码问题中，空格与相邻棋子的交换不会改变棋局中棋子数列的逆序数的奇偶性。
证明：显然空格与左右棋子交换不会改变棋子数列的逆序数（因为数列并没有改变）。现在考虑空格与上下棋子交换的情况：若空格与上方的棋子交换（假设交换是可行的），将得到一个新数列。若假设交换棋子为c[i]=X，那么原数列p=c[1]...X
c[i+1]c[i+2]...c[8]将变为新数列q=c[1]...c[i+1]c[i+2]X
...c[8]（注意：在棋盘中，上下相邻的两棋格之间隔有两个棋格）。由原数列p到新数列q的转变可以通过如下方式加以解释：用X与c[i+1]、
c[i+2]先后进行两次相邻交换而完成状态转变。所以根据引理2知，由p状态到q状态并不会改变改变棋子数列的逆序数的奇偶性。同理可证空格与下方棋子交换也不会改变棋子数列的逆序数的奇偶性。所以，空格与相邻棋子的交换不会改变棋局中棋子数列的逆序数的奇偶性。
定理1
（1）当初始状态棋局的棋子数列的逆序数是奇数时，八数码问题无解；
（2）当初始状态棋局的棋子数列的逆序数是偶数时，八数码问题有解。
证明：由引理3知，按照八数码问题的游戏规则，在游戏过程中，棋局的棋子数列的逆序数的奇偶性不会发生变化。而上面规定的目标状态没有逆序存在，所以目标状态下棋局的逆序数为偶数（实际为0）。显然，可能的初始状态棋局的棋子数列的逆序数可能为奇数，也可能为偶数（因为把一个初始状态中任意相邻两个棋子交换，得到的新的状态作为初始状态，它们的奇偶性相反）。所以，对于任意一个初始状态，若其棋局的棋子数列的逆序数为奇数，则永远也不可能达到目标状态，即八数码问题无解；若其棋局的棋子数列的逆序数为偶数。
补充一点：针对八数码问题，空白方块与上下行的数字块交换不会引起奇偶性互变，因为八数码的列数是奇数。
推广一下：对于N*M数码问题，空白在同一行交换不会导致奇偶性互变；上下行交换，如果列为奇数，则不会导致奇偶性互变，如果列数为偶数，则会导致奇偶性互变，所以此时还要考虑上下行交换的次数，综合得出答案。
一）宽搜
#include 'bits/stdc++.h'
using namespace std;
int bfs(string s)
{
map < string,int >
d;//通过hash来保存距离
queue < string > q;//BFS的对列
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
string end='123804765';//中止情况
q.push(s);
d[s]=0;
while(!q.empty())
{
string
now=q.front();
q.pop();
if(now==end)
{
return d[now];
}
int
dis=d[now];
int
pos=now.find('0');
int
x=pos/3,y=pos%3;//1维->2维基本操作
for(int j=0;j <
4;j++)//遍历
{
int fx=x+dx[j],fy=y+dy[j];
if(fx>=0 && fx< 3 && fy>=0
&& fy< 3)
{
swap(now[fx*3+fy],now[pos]);
if( ! d.count(now))
{
d[now]=dis+1;
q.push(now);
}
swap(now[fx*3+fy],now[pos]);//还原
}
}
}
}
int main ()
{
string s;cin>>s;
cout<<bfs(s)<<endl;
return 0;
}
BD363:
//八数码－宽度搜索
#include
using namespace std;
const int MAXN=370000;
int n, final, Ans, p;
int last[MAXN], qe[MAXN], rank[MAXN];
//last上一步的号码，用于输出路径（本题无输出路径，仅作参考）
//qe存储队列
//rank 记录当前搜索深度，即走了多少次
bool visit[MAXN];//结点是否已经访问
int s[9];//当前八数码的状态
int front = 1,rear = 1;//队列首尾
int turn()//转换成数字
{
int i;
int ans = 0;
for(i = 0; i < 9; i++)
ans = ans * 10 + s[i];
return ans;
}
int cantor()//康托压缩
{
bool use[9] = {0};
int i, j, no;
int ans = 0;
for(i = 8; i >= 1; i--)
{
no = 0;
use[s[8 - i]] = true;
for(j = 0; j < s[8 - i]; j++)
{
if(use[j] == true)
no++;
}
ans = (ans + s[8 - i] - no) * i;//0
开始
}
return ans;
}
void init()
{
int i;
cin>>n;
qe[1] = n;
visit[cantor()] = true;
n = 0;
s[0] = 1;s[1] = 2;s[2] = 3;
s[3] = 8;s[4] = 0;s[5] = 4;
s[6] = 7;s[7] = 6;s[8] = 5;
final = cantor();//末状态
}
void Ucan(int num)//反康托展开，这里用数字展开，而非康托值展开
{
int i;
for(i = 8; i >= 0; i--)
{
s[i] = num % 10;
num /= 10;
}
}
int findzero()//到0的位置
{
int i;
for(i = 0; i < 9; i++)
if(s[i] == 0)
return i;
}
void bfs(int c)
{
int t, num;
t = s[p]; s[p] = s[p + c]; s[p + c] = t;
num = cantor();
if(visit[num] != true)
{
qe[++rear] = turn();//换成数字
visit[num] = true;
last[rear] = front;
rank[rear] = rank[front] + 1;
if(num == final)//到答案
Ans = rank[front] +
1;
}
t = s[p]; s[p] = s[p + c]; s[p + c] = t;
}
int main()
{
// freopen('Puzzle8.in','r',stdin);
// freopen('Puzzle8.out','w',stdout);
init();
if(visit[final] == true)//初状态即末状态
{
printf('0');
return 0;
}
while(front <= rear && Ans == 0)
{
Ucan(qe[front]);
p = findzero();
if(p >= 3)//向上搜索
bfs(-3);
if(Ans == 0 && p < 6)
bfs(3);//向下搜索
if(Ans == 0 && (p % 3) >
0)
bfs(-1);//向左搜索
if(Ans == 0 && (p % 3) <
2)
bfs(1);//向右搜索
front++;
}
if(Ans == 0)//始终没有答案
printf('-1');
else
printf('%d', Ans);
return 0;
}
二）宽搜＋康托展开
#include
using namespace std;
const int MAXN=370000;
int n, final, Ans, p;
int last[MAXN], qe[MAXN], rank[MAXN];
//last上一步的号码，用于输出路径（本程序无输出路径，仅作参考）
//qe存储队列
//rank 记录当前搜索深度，即走了多少次
bool visit[MAXN];//结点是否已经访问
int s[9];//当前八数码的状态
int front = 1,rear = 1;//队列首尾
int turn()//转换成数字
{
int i;
int ans = 0;
for(i = 0; i < 9; i++)
ans = ans * 10 + s[i];
return ans;
}
int cantor()//康托压缩
{
bool use[9] = {0};
int i, j, no;
int ans = 0;
for(i = 8; i >= 1; i--)
{
no = 0;
use[s[8 - i]] = true;
for(j = 0; j < s[8 - i]; j++)
{
if(use[j] == true)
no++;
}
ans = (ans + s[8 - i] - no) * i;//0
开始
}
return ans;
}
void init()
{
int i;
cin>>n;
qe[1] = n;
visit[cantor()] = true;
n = 0;//123804765
s[0] = 1;s[1] = 2;s[2] = 3;
s[3] = 8;s[4] = 0;s[5] = 4;
s[6] = 7;s[7] = 6;s[8] = 5;
final = cantor();//末状态
}
void Ucan(int num)//反康托展开，这里用数字展开，而非康托值展开
{
int i;
for(i = 8; i >= 0; i--)
{
s[i] = num % 10;
num /= 10;
}
}
int findzero()//到0的位置
{
int i;
for(i = 0; i < 9; i++)
if(s[i] == 0)
return i;
}
void bfs(int c)
{
int t, num;
t = s[p]; s[p] = s[p + c]; s[p + c] = t;
num = cantor();
if(visit[num] != true)
{
qe[++rear] = turn();//换成数字
visit[num] = true;
last[rear] = front;
rank[rear] = rank[front] + 1;
if(num == final)//到答案
Ans = rank[front] +
1;
}
t = s[p]; s[p] = s[p + c]; s[p + c] = t;
}
int main()
{
// freopen('Puzzle8.in','r',stdin);
// freopen('Puzzle8.out','w',stdout);
init();
if(visit[final] == true)//初状态即末状态
{
printf('0');
return 0;
}
while(front <= rear && Ans == 0)
{
Ucan(qe[front]);
p = findzero();
if(p >= 3)//向上搜索
bfs(-3);
if(Ans == 0 && p < 6)
bfs(3);//向下搜索
if(Ans == 0 && (p % 3) >
0)
bfs(-1);//向左搜索
if(Ans == 0 && (p % 3) <
2)
bfs(1);//向右搜索
front++;
}
if(Ans == 0)//始终没有答案
printf('-1');
else
printf('%d', Ans);
return 0;
}
三）深度优先＋康托＋哈希
#include 'bits/stdc++.h'
using namespace std;
#define HashTableSize 362880
#define NOT
!
#define MaxDeep 50
typedef struct maps
{
int detail[3][3];
int x, y;
// 记录
空格（0）的坐标
}Map,*PMap;
Map org;
// 初始状态
Map end;
// 目标状态
bool HashTable[HashTableSize]={false};
//hash表
int const derection[4][2] ={ { -1 , 0 } , {1, 0 }, { 0 , -1
} , { 0, 1 } } ; // 可移动的四个方向
int Path[ MaxDeep + 1 ];
int Step;
bool Finish;
void input()
{
int i,j;
int sum;
for(i = 0 ; i < 9 ; i ++ )
{
scanf('',
*org.detail + i );
if(0 ==
*(*org.detail + i) )
{
org.x = i / 3;
org.y = i % 3;
}
}
for(i = 0 ; i < 9 ; i ++ )
//计算逆序
{
if( 0 ==
*(*org.detail + i) )
continue;
for(j = 0 ;
j < i; j ++ )
if( 0 != *(*org.detail+j) &&
*(*org.detail + j) < *(*org.detail + i) )
{
sum ++;
}
}
if( sum%2 == 0 )
// 目标状态各个数字对应的坐标位置
{
end.detail[0][0] = 1 , end.detail[0][1] = 2 , end.detail[0][2] = 3
;
end.detail[1][0] = 4 , end.detail[1][1] = 5 , end.detail[1][2] = 6
;
end.detail[2][0] = 7 , end.detail[2][1] = 8 , end.detail[2][2] = 0
;
}
else
{
end.detail[0][0] = 1 , end.detail[0][1] = 2 , end.detail[0][2] = 3
;
end.detail[1][0] = 8 , end.detail[1][1] = 0 , end.detail[1][2] = 4
;
end.detail[2][0] = 7 , end.detail[2][1] = 6 , end.detail[2][2] = 5
;
}
return;
}
inline bool IsEqual(Map a , Map b)//检测两个状态是否一样
{
return 0 == memcmp((const void
*)(*a.detail),(const void *)(*b.detail),36);
}
int HashValue(Map a)//hash值的计算
{
int count ;
int i , j ;
int value =0 ;
static int
pv[9]={1,1,2,6,24,120,720,5040,40320};
for(i = 0 ; i < 9 ; i ++ )
{
for(j = 0, count =0
; j < i ; j ++ )
{
if( *(*a.detail+i) < *(*a.detail+j) )
{
count
++;
}
}
value +=
pv[i]*count;
}
return value;
}
void Dfs(Map& node , int deep )//深度优先搜索
{
if(deep > MaxDeep )
return
;
if( true == IsEqual( node , end) )
{
Finish =
true;
Step =
deep;
return
;
}
for(int k =0 ;k < 4 &&
NOT Finish ; k ++ )
{
Map tmp =
node ;
tmp.x =
node.x + derection[k][0],
tmp.y =
node.y + derection[k][1];
if(tmp.x < 0 || tmp.x > 2 || tmp.y <0 || tmp.y
>2 )
{
continue;
}
tmp.detail[
node.x ][ node.y ] = tmp.detail[ tmp.x ][ tmp.y ];
//移动空格
tmp.detail[
tmp.x ][ tmp.y ] = 0 ;
int
tmpindex = HashValue( tmp );
if(HashTable[ tmpindex ] == true )
continue;
HashTable[
tmpindex ] = true;
Path[ deep
] = k ;
Dfs( tmp ,
deep + 1) ;
HashTable[
tmpindex ] = false;
}
return ;
}
void output()// 输出 结果
{
Map now = org ;
int oldx,oldy;
int count =0 ;
printf('共需要 %d 步.', Step);
for(int i =0 ; i < 3; i ++ )
{
for(int j
=0 ; j < 3; j ++)
{
printf('=',org.detail[ i ][ j ]);
}
printf('');
}
for( int k =0 ; k < Step ; k ++ )
{
oldx =
now.x , oldy = now.y ;
now.x +=
derection[ Path[ k ] ][ 0 ], now.y += derection[ Path[ k ] ][ 1
];
now.detail[
oldx ][ oldy ] = now.detail[ now.x ][ now.y ];
//移动空格
now.detail[
now.x ][ now.y ] = 0 ;
printf('
↓ 第%d步',++count);
getchar();
for(int i
=0 ; i < 3; i ++ )
{
for(int j =0 ; j < 3; j
++)
{
printf('=',now.detail[ i ][ j ]);
}
printf('');
}
}
printf('The End!');
return ;
}
int main()
{
input();
HashTable[ HashValue( org ) ] = true;
Dfs( org , 0 );
output();
return 0;
}
