8数码游戏代码,C/C++代码库,德仔网

代码语言
代码分类
【C/C++】 8数码游戏
作者:欣然 / 发布于2016/2/17/ 905
使用了递归的方法处理生成树，核心公式Tx=Hx+Gx，Hx是目前代价，Gx是预期代价
#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;  
    }
试试其它关键字
　8数码　
同语言下
可能有用的
欣然贡献的其它代码(11)