eignumdlg.cpp

8数码

        { 
            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 ++;  
            } 
    } 
    org.hx = 0 ; 
     org.fx = evaluate_hx( org.detail ); 

    if( sum%2 == 0 )        // 保存各个数字的坐标。
	 { 
       end[0][0] = 2 , end[0][1] = 2 ; 
        end[1][0] = 0 , end[1][1] = 0 ; end[2][0] = 0 , end[2][1] = 1 ;  
        end[3][0] = 0 , end[3][1] = 2 ; end[4][0] = 1 , end[4][1] = 0 ;  
        end[5][0] = 1 , end[5][1] = 1 ; end[6][0] = 1 , end[6][1] = 2 ;  
        end[7][0] = 2 , end[7][1] = 0 ; end[8][0] = 2 , end[8][1] = 1 ;  
    } 
    else 
    { 
        end[0][0] = 1 , end[0][1] = 1 ; 
        end[1][0] = 0 , end[1][1] = 0 ; end[2][0] = 0 , end[2][1] = 1 ;  
        end[3][0] = 0 , end[3][1] = 2 ; end[4][0] = 1 , end[4][1] = 2 ;  
        end[5][0] = 2 , end[5][1] = 2 ; end[6][0] = 2 , end[6][1] = 1 ;  
        end[7][0] = 2 , end[7][1] = 0 ; end[8][0] = 1 , end[8][1] = 0 ;  
    } 

    return; 
}  



/** 
 * 
 * hash值的计算 
 * 
**/ 
int CEigNumDlg::HashValue(Map a)    
{ 
   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; 
} 

/** 
 * 
 *状态插入到hash表中。返回的是插入到的hash表中对应的下标值 
 * 
 **/ 
int CEigNumDlg::InsertHashTable(Map a , int parent) 
{ 
    int index = HashValue( a ); 
    if(NULL == HashTable[index])  //如果为TURE，那么说明hash表中不存在该状态，应该插入到hash表中 
    { 
        a.parent = parent; 
         HashTable[index] = new Map; 
        *HashTable[index] = a; 
        FlageNew = true; 
        N++;
    } 
    else 
    { 
        FlageNew = false; 
    } 
    return index; 
} 

void CEigNumDlg::Axin() 
{ 
    Map node; 
    priority_queue<Map> Queue; 
    org.myindex = InsertHashTable( org , -1 ); 
    Queue.push( org ); 
    while( NOT Queue.empty() ) 
    { 
        node = Queue.top(); 
        Queue.pop(); 

        for(int k =0 ; k < 4; 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 = InsertHashTable( tmp , node.myindex ); 

            if( false == FlageNew )        //如果不是新状态的,即以前访问过改节点，不再加入队列中 
            { 
                continue; 
            } 

            tmp.parent = node.myindex; 
            tmp.myindex = tmpindex; 
            tmp.hx = node.hx + 1 ; 
            tmp.fx = tmp.hx + evaluate_hx( tmp.detail ); 
            if( tmp.fx  == tmp.hx )  
            { 
                result = tmp; 
                return ; 
            } 
            Queue.push(tmp); 
        } 
    } 
    return ; 
 } 


/** 
 * 
 * 通过hash表中记录的进行查找路径 
 * 
 **/ 
void CEigNumDlg::FindPath() 
{ 
    Map now; 
  //  stack<Map> Stack; 
	while (!Stack.empty())
		Stack.pop();

    Stack.push(result); 
    now = result; 
    int count=0; 
    while(now.parent != -1 ) 
    { 
        Stack.push(*HashTable[now.parent]); 
        now = Stack.top(); 
    } 
	SetDlgItemInt(IDC_BUSHU,Stack.size()-1);
	SetDlgItemInt(IDC_JIEDIAN,N);
	B=fenzi(N,Stack.size());

	char buffer[200];
	sprintf(buffer,"%f",B);
	CString cstr(buffer);
	SetDlgItemText(IDC_FENZHI,cstr);

    
  /*  printf("共需： %d 步\n",Stack.size()-1); 
    printf("共产生： %d 节点数\n",N);
    B=fenzi(N,Stack.size());
	cout<<"平均分枝因子： "<<B<<endl;
    getchar(); 
    while( NOT Stack.empty()) 
    { 
        now = Stack.top(); 
        Stack.pop(); 
        for(int i =0 ; i < 3; i ++ ) 
        { 
            for(int j =0 ; j < 3; j  ++) 
            { 
                printf("%3d",now.detail[i][j]); 
            } 
            printf("\n"); 
        }
		
		SetDlgItemInt(IDC_EDIT10,now.detail[0][0]);
		SetDlgItemInt(IDC_EDIT11,now.detail[0][1]);
		SetDlgItemInt(IDC_EDIT12,now.detail[0][2]);
		SetDlgItemInt(IDC_EDIT13,now.detail[1][0]);
		SetDlgItemInt(IDC_EDIT14,now.detail[1][1]);
		SetDlgItemInt(IDC_EDIT15,now.detail[1][2]);
		SetDlgItemInt(IDC_EDIT16,now.detail[2][0]);
		SetDlgItemInt(IDC_EDIT17,now.detail[2][1]);
		SetDlgItemInt(IDC_EDIT10,now.detail[2][2]);
        /*if(0 != Stack.size() ) 
        { 
            printf("\n    ↓ 第%d步\n",++count); 
            getchar(); 
        } 
		
    } */
   // printf("\nThe End!\n"); 
    return ; 
} 
void CEigNumDlg::OnTimer(UINT_PTR nIDEvent)
{
	// TODO: 在此添加消息处理程序代码和/或调用默认值

	Map now; 
 /*
    Stack.push(result); 
    now = result; 
    int count=0; 
    while(now.parent != -1 ) 
    { 
        Stack.push(*HashTable[now.parent]); 
        now = Stack.top(); 
    } 
    */
   /* printf("共需： %d 步\n",Stack.size()-1); 
    printf("共产生： %d 节点数\n",N);
    B=fenzi(N,Stack.size());
	cout<<"平均分枝因子： "<<B<<endl;
    getchar(); 
	*/
    if( NOT Stack.empty()) 
    { 
        now = Stack.top(); 
        Stack.pop(); 
       /* for(int i =0 ; i < 3; i ++ ) 
        { 
            for(int j =0 ; j < 3; j  ++) 
            { 
                printf("%3d",now.detail[i][j]); 
            } 
            printf("\n"); 
        }
		*/
		SetDlgItemInt(IDC_EDIT10,now.detail[0][0]);
		SetDlgItemInt(IDC_EDIT11,now.detail[0][1]);
		SetDlgItemInt(IDC_EDIT12,now.detail[0][2]);
		SetDlgItemInt(IDC_EDIT13,now.detail[1][0]);
		SetDlgItemInt(IDC_EDIT14,now.detail[1][1]);
		SetDlgItemInt(IDC_EDIT15,now.detail[1][2]);
		SetDlgItemInt(IDC_EDIT16,now.detail[2][0]);
		SetDlgItemInt(IDC_EDIT17,now.detail[2][1]);
		SetDlgItemInt(IDC_EDIT18,now.detail[2][2]);
        /*if(0 != Stack.size() ) 
        { 
            printf("\n    ↓ 第%d步\n",++count); 
            getchar(); 
        } 
		*/
    } 
	CDialog::OnTimer(nIDEvent);
}

void CEigNumDlg::OnBnClickedShow()
{
	// TODO: 在此添加控件通知处理程序代码
	SetTimer(1,2000,0);

}

void CEigNumDlg::OnBnClickedStep()
{
	// TODO: 在此添加控件通知处理程序代码
	KillTimer(1);
	Map now; 
	if (m_flag)
	{

  //  stack<Map> Stack; 
	while (!Stack.empty())
		Stack.pop();

    Stack.push(result); 
    now = result; 
    int count=0; 
    while(now.parent != -1 ) 
    { 
        Stack.push(*HashTable[now.parent]); 
        now = Stack.top(); 
    } 
	m_flag=FALSE;
	}
	
	if( NOT Stack.empty()) 
    { 
        now = Stack.top(); 
        Stack.pop(); 
       /* for(int i =0 ; i < 3; i ++ ) 
        { 
            for(int j =0 ; j < 3; j  ++) 
            { 
                printf("%3d",now.detail[i][j]); 
            } 
            printf("\n"); 
        }
		*/
		SetDlgItemInt(IDC_EDIT10,now.detail[0][0]);
		SetDlgItemInt(IDC_EDIT11,now.detail[0][1]);
		SetDlgItemInt(IDC_EDIT12,now.detail[0][2]);
		SetDlgItemInt(IDC_EDIT13,now.detail[1][0]);
		SetDlgItemInt(IDC_EDIT14,now.detail[1][1]);
		SetDlgItemInt(IDC_EDIT15,now.detail[1][2]);
		SetDlgItemInt(IDC_EDIT16,now.detail[2][0]);
		SetDlgItemInt(IDC_EDIT17,now.detail[2][1]);
		SetDlgItemInt(IDC_EDIT18,now.detail[2][2]);
        
	}
}

void CEigNumDlg::OnBnClickedReset()
{
	// TODO: 在此添加控件通知处理程序代码

		SetDlgItemInt(IDC_EDIT1,0);
		SetDlgItemInt(IDC_EDIT2,0);
		SetDlgItemInt(IDC_EDIT3,0);
		SetDlgItemInt(IDC_EDIT4,0);
		SetDlgItemInt(IDC_EDIT5,0);
		SetDlgItemInt(IDC_EDIT6,0);
		SetDlgItemInt(IDC_EDIT7,0);
		SetDlgItemInt(IDC_EDIT8,0);
		SetDlgItemInt(IDC_EDIT9,0);
		SetDlgItemInt(IDC_EDIT10,0);
		SetDlgItemInt(IDC_EDIT11,0);
		SetDlgItemInt(IDC_EDIT12,0);
		SetDlgItemInt(IDC_EDIT13,0);
		SetDlgItemInt(IDC_EDIT14,0);
		SetDlgItemInt(IDC_EDIT15,0);
		SetDlgItemInt(IDC_EDIT16,0);
		SetDlgItemInt(IDC_EDIT17,0);
		SetDlgItemInt(IDC_EDIT18,0);

		m_flag=TRUE;
		CheckRadioButton(IDC_RADIO1,IDC_RADIO2, IDC_RADIO1);
}

void CAboutDlg::OnBnClickedAbout()
{
	// TODO: 在此添加控件通知处理程序代码
}