- #include<iostream>
- #include<math.h>
- #include <stdlib.h>
- #define FALSE 0
- #define TRUE 1
- using namespace std;
- /*程序开头*/
- void preface(){
- cout<<"————————欢迎使用本程序3_3————————"<<endl<<"请输入0~8之间的数,0表示空格"<<endl;
- cout<<endl<<"目标状态是"<<endl<<1<<" "<<2<<" "<<3<<endl<<8<<" "<<0<<" "<<4<<endl<<7<<" "<<6<<" "<<5<<endl;
- cout<<"————————"<<endl<<"现在游戏开始:"<<endl<<endl;
- }
- /*输出八数码排列*/
- void show(int init[][3]){
- int i,j;
- cout<<"——————————"<<endl;
- for(i=0;i<3;i++){
- for(j=0;j<3;j++)
- cout<<init[i][j]<<" ";
- cout<<endl;
- }
- cout<<"====================="<<endl;
- }
- /*输出初始八数码排列*/
- void start(int init[][3]){
- cout<<"——————————————"<<endl<<"初始排列是:"<<endl;
- show(init);
- cout<<"程序开始运算!"<<endl<<endl;
- }
- /*输入八数码排列*/
- void input(int initial[][3],int *row,int *colunm,int sip_init[]){
- int i,j;
- int w,q;
- int buffer, flag, zero = 0;
- for (i = 0; i < 3; i++){
- for(j = 0; j < 3; j++){
- flag = TRUE;
- cout<<"请输入第"<<i+1<<"行,第"<<j+1<<"列的元素的值:";
- scanf("%d", &buffer);
- if(buffer < 0 || buffer > 8){ //范围不对
- cout<<"范围错误,请输入0~8之间的数字"<<endl;
- flag = FALSE;
- j--;
- }
- for (q = 0; q <= i && flag == 1; q++) //检查重复
- for (w = 0; w < j; w++)
- if(buffer == initial[q][w]){
- cout<<"重复,请重新输入"<<endl;
- j--;
- flag=FALSE;
- break;
- }
- if(flag==TRUE){
- if(buffer == 0){ //存储0的位置
- *row = i;
- *colunm = j;
- }
- initial[i][j] = buffer;//存储数组中
- sip_init[i*3+j]=buffer;//存储算奇偶性数组中
- }
- }
- cout<<endl;
- }
- }
- /*除2余数*/
- int parity(int sip_init[]){
- int count;
- int i,j;
- count=0;
- for(i=0;i<9;i++){
- if(sip_init[i]==0)
- continue;
- else{
- for(j=0;j<i;j++){
- if(sip_init[i]<sip_init[j])
- count++;
- }
- }
- }
- return count%2;//模2
- }
- /*判断奇偶性*/
- void calculate_parity(int sip_init[]){
- int flag=1;
- if(parity(sip_init)!=flag){//和目标数列的奇偶性进行比较,如果不匹配的话,那么就判断无解
- cout<<"该排列与目标排列奇偶性不匹配,因而无解!"<<endl;
- exit(0);
- }
- }
- /*计算G(n)*/
- int calculate(int initial[3][3], int end[3][3]){
- int w,k;
- int i,j;
- int count=0; //记录所有棋子移动到正确位置所需步数
- for(i = 0; i < 3; i++)
- for(j = 0; j < 3; j++)
- {
- if(initial[i][j] == 0) //如果是0不管
- continue;
- else if(initial[i][j] != end[i][j]) {
- for(k=0; k<3; k++)
- for(w=0; w<3; w++)
- if(initial[i][j] == end[k][w])
- count = count +abs(i-k) + abs(j-w); //绝对值加减
- }
- }
- return count; //返回步数
- }
- /*交换位置*/
- void change(int init[][3], int line_1, int column_1, int line_2, int column_2){
- int casual; //中间数
- casual=init[line_1][column_1];
- init[line_1][column_1]=init[line_2][column_2];
- init[line_2][column_2]=casual;
- }
- /*交换位置同时计算交换位置后的G(n)*/
- int assem(int initial[3][3], int target[3][3],int row, int column,int a,int b){
- int temp;
- change(initial, row+a, column+b, row,column); //换位
- return temp = calculate(initial, target); //计算G(n)
- }
- /*初始数组,目标数组,G(n),操作数,操作标识,0的横竖位置,操作数*/
- int search(int initial[3][3], int target[3][3], int Gn, int jishu,int biaoji, int row, int column,int count){
- int temp;
- int temp_zhi;
- if(count!=0){//表述目前状态
- cout<<endl<<"本搜索枝第"<<count<<"次运算"<<" "<<"G(n)为"<<Gn<<endl;
- show(initial);}
- if(Gn == 0){ //Gn为0,完成任务
- cout<<"搜索任务完成"<<endl;
- return TRUE;
- }
- if(row > 0 && biaoji != 0)
- {
- change(initial, row - 1, column, row , column); //将0与其上面的元素交换存储位置
- temp = calculate(initial, target);
- if(temp >= Gn) //如果交换后步数大于等于原来的步数
- change(initial, row - 1, column, row , column); //再将其交换回来
- else if(temp < Gn) //如果交换后步数小于原来的步数
- {
- temp_zhi = search(initial, target, temp, jishu+1, 2, row-1, column,++count);
- if( temp_zhi == 1) //进行下一步的移动
- return TRUE;
- change(initial, row - 1, column, row , column); //再将其交换回来
- }
- }
- if(column > 0 && biaoji != 1)
- {
- change(initial, row, column - 1, row , column); //将0与其左边的元素交换存储位置
- temp = calculate(initial, target);
- if(temp >= Gn)
- change(initial, row, column - 1, row , column);
- else if(temp < Gn)
- {
- temp_zhi = search(initial, target, temp, jishu+1, 3, row, column - 1,++count);
- if(temp_zhi == 1)
- return TRUE;
- change(initial, row, column - 1, row , column);
- }
- }
- if(row < 2 && biaoji != 2)
- {
- change(initial, row + 1, column, row , column); //将0与其下面的元素交换存储位置
- temp = calculate(initial, target);
- if(temp >= Gn)
- change(initial, row + 1, column, row , column);
- else if(temp < Gn)
- {
- temp_zhi =search(initial, target, temp, jishu+1,0, row+1, column,++count);
- if(temp_zhi == 1)
- return TRUE;
- change(initial, row + 1, column, row , column);
- }
- }
- if(column < 2 && biaoji != 3)
- {
- change(initial, row, column + 1, row , column); //将0与其右边的元素交换存储位置
- temp = calculate(initial, target);
- if(temp >= Gn)
- change(initial, row, column + 1, row , column);
- else if(temp < Gn)
- {
- temp_zhi = search(initial, target, temp, jishu+1, 1, row, column+1,++count);
- if(temp_zhi == 1)
- return TRUE;
- change(initial, row, column + 1, row , column);
- }
- }
- return FALSE;
- }
- int main(){
- int jishu = 0, sip_init[9];
- int row;
- int column;
- int initial[3][3],count=1;
- int target[3][3] = {1, 2, 3, 8, 0, 4, 7, 6, 5};
- preface();//输入及输入判断部分
- input(initial, &row,&column,sip_init);
- start(initial);
- calculate_parity(sip_init);//判断奇偶性部分
- if(search (initial, target,calculate(initial,target),jishu,4,row,column,0) == 0)//程序运行以及返回结果
- cout<<endl<<"此8数码的问题可能无解!";
- system("pause");
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/0607201614779.html
来源: http://www.codesnippet.cn/detail/0607201614779.html