首页 > 代码库 > 8数码问题

8数码问题

八数码游戏(八数码问题)描述为:在3×3组成的九宫格棋盘上,摆有八个将牌,每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格,允许其周围的某一个将牌向空格移动,这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是:给定一种初始的将牌布局或结构(称初始状态)和一个目标的布局(称目标状态),问如何移动将牌,实现从初始状态到目标状态的转变。

对于八数码问题的解决,首先要考虑是否有答案。每一个状态可认为是一个1×9的矩阵,问题即通过矩阵的变换,是否可以变换为目标状态对应的矩阵?由数学知识可知,可计算这两个有序数列的逆序值,如果两者都是偶数或奇数,则可通过变换到达,否则,这两个状态不可达。这样,就可以在具体解决问题之前判断出问题是否可解,从而可以避免不必要的搜索。

A*:启发中的估价是用估价函数表示的,如:f(n) = g(n) + h(n)  其中f(n) 是节点n的估价函数,g(n)是在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价。 在此八数码问题中,显然g(n)就是从初始状态变换到当前状态所移动的步数,估计代价h(n)我们就可采用当前状态各个数字牌不在目标状态未知的个数,即错位数。


 程序设计步骤:

有open、close、distance三个列表,其中open放的是上一次迭代过程中产生的周围点(周围点不能在close表中,因为不能走已经走过的路),distance放的是所有已经走过的点的最好f值,close放的是已经走过的点

每一次通过得到open中的第一个值temp(open已经排序好的)并将open清空,从而得到temp的周围点(排除已经在close中的点,并且由distance进行更新,即如果比distance中该点的值大,则用distance中该点进行更新,否则将distance进行更新),并将周围点放入open中。进入下一次迭代过程

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;


public class EightPuzzleAlgorithm {
    //八数码问题
    
    
    
    
    
    public void Search(EightNode start,EightNode target,List<EightNode> open,List<EightNode> close,List<EightNode> distance){//distance值储存open中状态的f值
        
//        if(!IsSolution(start.getNodeValue(),target.getNodeValue())){
//            System.out.println("两个数不满足条件,不能查找");
//            return;
//        }
        
        if(close==null){
            close = new ArrayList();
        }
        
        if(open.size()==0){
            System.out.println("查找失败!!!");
            return;
        }
        if(open.get(0).equals((target))){
            System.out.println("查找成功!!!");
            return;
        }
        //对于已经排序好的open来说,选出f值最小的状态
        System.out.println("************************");
        EightNode temp = open.get(0);
        int[]tempNode = temp.getNodeValue();
        for(int i = 0;i<3;i++){
            for(int j = 0;j<3;j++){
                System.out.print("  "+tempNode[i*3+j]);
            }
            System.out.println();
        }
        
        
        
        
        List<int[]>arround = move(temp);
        System.out.println(arround.size()+"********&&***&&");
        
        //产生不包括在close中的arroundNode列表
        List<EightNode>arroundNode = new ArrayList<EightNode>();
        for(int i = 0;i<arround.size();i++){
            EightNode node = new EightNode();
            node.setF(fValue(temp,arround.get(i),target));
            node.setG(gValue(temp));
            node.setH(hValue(temp,arround.get(i),target));
            node.setNodeValue(arround.get(i));
            if (!close.contains(node)){
                arroundNode.add(node);
            }
        }
        close.add(temp);
        
        
        
        //更新distance(distance用于储存所有走过点的周围点的信息)。
        for(int i = 0;i<arroundNode.size();i++){
            boolean flag = false;
            for(int j = 0;j<distance.size();j++){
                if(arroundNode.get(i).equals(distance.get(j))){
                    flag = true;
                    if(distance.get(j).getF()>arroundNode.get(i).getF()){
                        distance.set(j, arroundNode.get(i));
                    }
                    break;
                }
            }
            if(flag == false){
                distance.add(arroundNode.get(i));
            }
        }
        
        //更新open
        open = new ArrayList();
        open.addAll(arroundNode);
        System.out.println(open.size()+"***********&&");
        for(int i = 0;i<open.size();i++){
            for(int j = 0;j<distance.size();j++){
                if(open.get(i).equals(distance.get(j))){
                    open.set(i, distance.get(j));
                }
            }
        }
        System.out.println(open.size()+"***…………********&&");
        open = sort(open);
        
        
        Search(start,target,open,close,distance);
    }
    
    public int hValue(EightNode temp1,int[]arroundi,EightNode target1){
        int[]temp = temp1.getNodeValue();
        int[]target=target1.getNodeValue();
        int h = 0;
        for(int i = 0;i<target.length;i++){
            if(target[i]!=arroundi[i]){
                h=h+1;
            }
        }
        return h;
    }
    
    public List<EightNode>sort(List<EightNode>open){
        for(int i = 0;i<open.size();i++){
            for(int j =i+1;j<open.size();j++){
                if(open.get(i).getF()>open.get(j).getF()){
                    EightNode temp = open.get(i);
                    open.set(i, open.get(j));
                    open.set(j, temp);
                }
            }
        }
        return open;
    }
    
    
    
    public int gValue(EightNode temp){
        return temp.getG()+1;
    }
    public int fValue(EightNode temp1,int[]arroundi,EightNode target1){
        return hValue(temp1,arroundi,target1)+gValue(temp1);
    }
    
    
    



    //对于一个open选出来的状态,如何获取它邻近的状态
    public List<int[]> move(EightNode temp1){
        int[]temp = temp1.getNodeValue();
        List<int[]>list = new ArrayList<int[]>();
        //先找出0(空格所在的位置)
        int position = 0;
        for(int i = 0;i<temp.length;i++){
            if(temp[i]==0){
                position = i;
                break;
            }
        }
        if(position==0){
            list.add(swap(temp.clone(),0,1));
            list.add(swap(temp.clone(),0,3));
        }else if(position==1){
            list.add(swap(temp.clone(),1,0));
            list.add(swap(temp.clone(),1,4));
            list.add(swap(temp.clone(),1,2));
        }else if(position==2){
            list.add(swap(temp.clone(),2,1));
            list.add(swap(temp.clone(),5,2));
        }else if(position==3){
            list.add(swap(temp.clone(),3,0));
            list.add(swap(temp.clone(),3,4));
            list.add(swap(temp.clone(),3,6));
        }else if(position==4){
            list.add(swap(temp.clone(),4,1));
            list.add(swap(temp.clone(),4,3));
            list.add(swap(temp.clone(),4,5));
            list.add(swap(temp.clone(),4,7));
        }else if(position==5){
            list.add(swap(temp.clone(),5,2));
            list.add(swap(temp.clone(),5,8));
            list.add(swap(temp.clone(),5,4));
        }else if(position==6){
            list.add(swap(temp.clone(),6,3));
            list.add(swap(temp.clone(),6,7));
        }else if(position==7){
            list.add(swap(temp.clone(),7,6));
            list.add(swap(temp.clone(),7,8));
            list.add(swap(temp.clone(),7,4));
        }else if(position==8){
            list.add(swap(temp.clone(),8,5));
            list.add(swap(temp.clone(),8,7));
        }
        return list;
    }
    
    
    public int[] swap(int[] temp,int i,int j){
        int a = temp[i];
        temp[i] = temp[j];
        temp[j] = a;
        return temp;
    }
    
    
    
    
    
    
    //判断是否有解,两个数组的逆序数同为偶数或是奇数
    public  boolean IsSolution(int []current,int[]target){
        int n1 = InverseNumber(current);
        int n2 = InverseNumber(target);
        if(n1%2==n2%2){
            return true;
        }else{
            return false;
        }
    }

    private  int InverseNumber(int[] current) {
        int length1 = current.length;
        int count1 = 0;
        for(int i = 0;i<length1;i++){
            int temp = current[i];
            for(int j = i+1;j<length1;j++){
                if(temp>current[j]){
                    count1 = count1+1;
                }
            }
        }
        return count1;
    }
    
    
    
    
    
}

 

8数码问题