eight-puzzledlg.cpp

九宫图 用过程表示法解

// Eight-PuzzleDlg.cpp : 实现文件
//

#include "stdafx.h"
#include "Eight-Puzzle.h"
#include "Eight-PuzzleDlg.h"
#include ".\eight-puzzledlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#endif


// CEightPuzzleDlg 对话框



CEightPuzzleDlg::CEightPuzzleDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CEightPuzzleDlg::IDD, pParent)
{
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
	int pathA[9]={1,2,0,4,5,6,7,8,1};
	memcpy(m_pathA,pathA,sizeof(int)*9);

	int pathB[9]={2,3,4,5,6,7,8,0,2};
	memcpy(m_pathB,pathB,sizeof(int)*9);

	int pathC[7]={8,0,4,5,6,7,8};
	memcpy(m_pathC,pathC,sizeof(int)*7);

	int pathD[5]={1,2,0,8,1};
	memcpy(m_pathD,pathD,sizeof(int)*5);

	int pathE[7]={1,2,3,4,0,8,1};
	memcpy(m_pathE,pathE,sizeof(int)*7);

	int pathF[9]={1,2,3,4,5,6,7,8,1};
	memcpy(m_pathF,pathF,sizeof(int)*9);

	int pathG[5]={8,0,6,7,8};
	memcpy(m_pathG,pathG,sizeof(int)*5);

	int pathH[5]={0,4,5,6,0};
	memcpy(m_pathH,pathH,sizeof(int)*5);

	int pathS1[5]={2,3,4,0,2};
	memcpy(m_pathS1,pathS1,sizeof(int)*5);

	int pathS2[9]={1,2,3,4,5,6,7,8,1};
	memcpy(m_pathS2,pathS2,sizeof(int)*9);

}

void CEightPuzzleDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
}

BEGIN_MESSAGE_MAP(CEightPuzzleDlg, CDialog)
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	//}}AFX_MSG_MAP
	ON_BN_CLICKED(IDOK, OnBnClickedOk)
END_MESSAGE_MAP()


// CEightPuzzleDlg 消息处理程序

BOOL CEightPuzzleDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// 设置此对话框的图标。当应用程序主窗口不是对话框时，框架将自动
	//  执行此操作
	SetIcon(m_hIcon, TRUE);			// 设置大图标
	SetIcon(m_hIcon, FALSE);		// 设置小图标

	// TODO: 在此添加额外的初始化代码
	SetDlgItemInt(IDC_EDIT0,0);
	SetDlgItemInt(IDC_EDIT1,3);
	SetDlgItemInt(IDC_EDIT2,8);
	SetDlgItemInt(IDC_EDIT3,2);
	SetDlgItemInt(IDC_EDIT4,4);
	SetDlgItemInt(IDC_EDIT5,7);
	SetDlgItemInt(IDC_EDIT6,6);
	SetDlgItemInt(IDC_EDIT7,5);
	SetDlgItemInt(IDC_EDIT8,1);
	
	return TRUE;  // 除非设置了控件的焦点，否则返回 TRUE
}

// 如果向对话框添加最小化按钮，则需要下面的代码
//  来绘制该图标。对于使用文档/视图模型的 MFC 应用程序，
//  这将由框架自动完成。

void CEightPuzzleDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // 用于绘制的设备上下文

		SendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);

		// 使图标在工作矩形中居中
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// 绘制图标
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

//当用户拖动最小化窗口时系统调用此函数取得光标显示。
HCURSOR CEightPuzzleDlg::OnQueryDragIcon()
{
	return static_cast<HCURSOR>(m_hIcon);
}

void CEightPuzzleDlg::OnBnClickedOk()
{
	ZeroMemory(m_nums,sizeof(int)*9);
	m_nums[0] = GetDlgItemInt(IDC_EDIT0);
	m_nums[1] = GetDlgItemInt(IDC_EDIT1);
	m_nums[2] = GetDlgItemInt(IDC_EDIT2);
	m_nums[3] = GetDlgItemInt(IDC_EDIT3);
	m_nums[4] = GetDlgItemInt(IDC_EDIT4);
	m_nums[5] = GetDlgItemInt(IDC_EDIT5);
	m_nums[6] = GetDlgItemInt(IDC_EDIT6);
	m_nums[7] = GetDlgItemInt(IDC_EDIT7);
	m_nums[8] = GetDlgItemInt(IDC_EDIT8);
	if(CheckArray()==false)
	{
		return;
	}
	if(IsSgState()==true)
	{
		OUTPUT;

		MessageBox("S(0)==S(g)");
		return;
	}
	else
	{
		OUTPUT;
		Step(1);
	}
}

bool CEightPuzzleDlg::CheckArray()
{
	bool bfound = false;
	for(int i=0;i<9;i++)
	{
		bfound = false;
		for(int j=0;j<9;j++)
		{
			if(bfound == true)
			{
				break;
			}

			if(m_nums[j]==i)
			{
				bfound = true;
			}
			else
			{
				bfound = false;
			}
		}
		if(bfound == false)
		{
			CString strmsg;
			strmsg.Format("Can't found number %d",i);
			MessageBox(strmsg);
			return false;
		}
	}
	return true;
}

bool CEightPuzzleDlg::IsSgState()
{
	for(int i=0;i<9;i++)
	{
		if(m_nums[i]!=i)
		{
			return false;
		}
	}
	return true;
}


void CEightPuzzleDlg::Step(int step)
{
	int temp=0;
	int x=0;
	switch(step)
	{
	case 1:
		{
			if (m_nums[1]==1)
			{
				Step(3);
			}
			else
			{
				while(m_nums[3]==0||m_nums[3]==1)
				{
					//when X3==0
					if(m_nums[3]==0)
					{
						if(m_nums[2]!=1)
						{
							temp = m_nums[3];
							m_nums[3]=m_nums[2];
							m_nums[2]=temp;
						}
						else if(m_nums[4]!=1)
						{
							temp = m_nums[3];
							m_nums[3]=m_nums[4];
							m_nums[4]=temp;
						}

					}
					//when X3==1
					if(m_nums[3]==1)
					{
						int x = FindZero();
						switch(x)
						{
						case 0:
						case 2:
						case 4:
							{
								while(m_nums[3]==0||m_nums[3]==1)
								{
									x = FindZero();
									Swap(m_nums[x],m_nums[m_pathS1[GetPos(m_pathS1,5,x)+1]]);
									OUTPUT;
								}
								break;
							}
						case 1:
						case 5:
						case 6:
						case 7:
						case 8:
							{
								while(m_nums[3]==0||m_nums[3]==1)
								{
									x = FindZero();
									Swap(m_nums[x],m_nums[m_pathS2[GetPos(m_pathS2,9,x)+1]]);
									OUTPUT;
								}
								break;
							}
						}
							
					}
				}
				Step(2);
			}
			break;
		}
	case 2:
		{
			
			while(!(m_nums[1]==1&&m_nums[8]==0))
			{
				x = FindZero();

				Swap(m_nums[x],m_nums[m_pathA[GetPos(m_pathA,9,x)+1]]);

				OUTPUT;
			}
			Step(3);
			break;
		}
	case 3:
		{
			while(!(m_nums[2]==2&&m_nums[0]==0))
			{
				x = FindZero();
				Swap(m_nums[x],m_nums[m_pathB[GetPos(m_pathB,9,x)+1]]);

				OUTPUT;
			}
			if(m_nums[3]==3)
			{
				Step(7);
			}
			else
			{
				Step(4);
			}
			break;
		}
	case 4:
		{
			while(!(m_nums[0]==3&&m_nums[8]==0&&m_nums[1]==1&&m_nums[2]==2))
			{
				x = FindZero();
				Swap(m_nums[x],m_nums[m_pathC[GetPos(m_pathC,7,x)+1]]);

				OUTPUT;
			}
			Step(5);
			break;
		}
	case 5:
		{
			while(!(m_nums[0]==0&&m_nums[8]==1&&m_nums[1]==2&&m_nums[2]==3))
			{
				x = FindZero();
				Swap(m_nums[x],m_nums[m_pathD[GetPos(m_pathD,5,x)+1]]);

				OUTPUT;
			}
			Step(6);
			break;
		}
	case 6:
		{
			while(!(m_nums[8]==0&&m_nums[1]==1&&m_nums[2]==2&&m_nums[3]==3))
			{
				x = FindZero();
				Swap(m_nums[x],m_nums[m_pathE[GetPos(m_pathE,7,x)+1]]);

				OUTPUT;
			}
			Step(7);
			break;
		}
	case 7:
		{
			while(!(m_nums[4]==4&&m_nums[0]==0))
			{
				x = FindZero();
				Swap(m_nums[x],m_nums[m_pathC[GetPos(m_pathC,7,x)+1]]);

				OUTPUT;
			}
			if(m_nums[5]==5)
			{
				Step(1);
			}
			else
			{
				Step(8);
			}
			break;
		}
	case 8:
		{
			while(!(m_nums[0]==5&&m_nums[8]==0))
			{
				x = FindZero();
				Swap(m_nums[x],m_nums[m_pathG[GetPos(m_pathG,5,x)+1]]);

				OUTPUT;
			}
			Step(9);
			break;
		}
	case 9:
		{
			while(!(m_nums[4]==0))
			{
				x = FindZero();
				Swap(m_nums[x],m_nums[m_pathF[GetPos(m_pathF,9,x)+1]]);

				OUTPUT;
			}
			//////////////////
			Swap(m_nums[0],m_nums[4]);
			Swap(m_nums[6],m_nums[0]);
			OUTPUT;
			Step(10);
			break;
		}
	case 10:
		{
			while(!(m_nums[7]==0&&m_nums[1]==1&&m_nums[2]==2&&m_nums[3]==3&&m_nums[4]==4&&m_nums[5]==5))
			{
				x = FindZero();
				Swap(m_nums[x],m_nums[m_pathF[GetPos(m_pathF,9,x)+1]]);

				OUTPUT;
			}
			Step(11);
			break;
		}
	case 11:
		{
			while(!(m_nums[0]==0&&m_nums[1]==1&&m_nums[2]==2&&m_nums[3]==3&&m_nums[4]==4&&m_nums[5]==5&&m_nums[6]==6&&m_nums[7]==7&&m_nums[8]==8)&&
				!(m_nums[0]==0&&m_nums[1]==1&&m_nums[2]==2&&m_nums[3]==3&&m_nums[4]==4&&m_nums[5]==5&&m_nums[6]==6&&m_nums[7]==8&&m_nums[8]==7))
			{
				x = FindZero();
				Swap(m_nums[x],m_nums[m_pathG[GetPos(m_pathG,5,x)+1]]);

				OUTPUT;
			}
			if((m_nums[0]==0&&m_nums[1]==1&&m_nums[2]==2&&m_nums[3]==3&&m_nums[4]==4&&m_nums[5]==5&&m_nums[6]==6&&m_nums[7]==8&&m_nums[8]==7))
			{
				MessageBox("Can't Get Answer!");
			}

			SetDlgItemInt(IDC_EDIT0,m_nums[0]);
			SetDlgItemInt(IDC_EDIT1,m_nums[1]);
			SetDlgItemInt(IDC_EDIT2,m_nums[2]);
			SetDlgItemInt(IDC_EDIT3,m_nums[3]);
			SetDlgItemInt(IDC_EDIT4,m_nums[4]);
			SetDlgItemInt(IDC_EDIT5,m_nums[5]);
			SetDlgItemInt(IDC_EDIT6,m_nums[6]);
			SetDlgItemInt(IDC_EDIT7,m_nums[7]);
			SetDlgItemInt(IDC_EDIT8,m_nums[8]);
			
			break;
		}
	default:
		{
			return;
		}
	}
}

int CEightPuzzleDlg::FindZero()
{
	for(int i=0;i<9;i++)
	{
		if(m_nums[i]==0)
		{
			return i;
		}
	}
}