Article Title: JiuGongTu (eight digital) solution process dynamic presentation author: Zhao Hongwei original source: vczx.com Publisher: Zhao Hongwei released type: Original release date: 2004-12-20 View today: 18 Total Views: 2718 Download herein Addition code
I. Title Description: (Jiugong Problem) In a 3 × 3 Nine palace, there are 1-8 these 8 numbers and a space randomly placed in the lattice, as shown in Figure 1-1. This problem is now required: Adjusting the nine-pace to the form shown in Figure 1-1. The rules of the adjustment are: each of the numbers that can only be moved from spaces (upper, lower, or left, right) to the space each time. The solution to this issue is achieved. (Figure 1-1) Second, topic analysis: Jiuguan problem is one of the classic problems in artificial intelligence, the problem is in the 3 × 3 square checkerboard, put the number of 8 pieces, the remaining is not put, each Second move can only be exchanged with adjacent spaces. The program automatically generates the initial state of the problem, converts it into the target arrangement (as shown in Figs. 1-2 to 1-3 below).
(Fig. 1-2) (Figure 1-3) In the Jiuguan problem, two random arrangements generated by the program have two possibilities, and these two cannot be established simultaneously, that is, odd arranging and even arranging. We can use a randomly arranged array from left to right to use a one-dimensional array, as in Figure 1-2, we can represent {8, 7, 1, 5, 2, 6, 3, 4, 0} where 0 represents space. In this array, we first calculate the result that it is able to rearrange, the formula is: σ (f (x)) = y, where f (x) is a number of fewer numbers in front of this number, y is Odd and even numbers have a solution. Then the above array we can solve its results. F (8) = 0; f (7) = 0; f (1) = 0; f (5) = 1; f (2) = 1; f (6) = 3; f (3) = 2; f (4) = 3; y = 0 0 0 1 1 3 2 3 = 10 Y = 10 is an even number, so his rearrangement is the result of Figure 1-3, if the result is the result of odd rearrangement is as shown in Figure 1-1 Row up. Third, the algorithm analyzes the method of solving the problem of the Jiuguan problem is to switch spaces (0) position until the target position is reached. The graphic representation is: (Figure 3-1) To get the best, you need to use the breadth priority search, the nine palaces so it is arranged! The species, that is, 362880 row, the amount of data is very large, the wide search I use, you need to remember the arrangement of each node, if you use the array record, you will take a lot of memory, we take the data appropriate compression.
Save in DWORD form, the compressed form is indicated by 3 digits per number, which is 3 × 9 = 27 bytes. Since the 8 binary representation form 1000, it cannot be represented by 3 bits, I use a small skill is 8 Indicates the bit 000, then uses more 5 characters to indicate the position where 8 is located, you can use DWORD. Use shift and or operation to move the data one by one, which is stronger than the multiplication speed. Several results are defined to store the optimal paths after the result is complete and the search is complete. Class structure is as follows: class CNineGird {public: struct PlaceList {DWORD Place; PlaceList * Left; PlaceList * Right;}; struct Scanbuf {DWORD Place; int ScanID;}; struct PathList {unsigned char Path [9];}; private: PlaceList * m_pPlaceList; Scanbuf * m_pScanbuf; RECT m_rResetButton; RECT m_rAutoButton; public: int m_iPathsize; clock_t m_iTime; UINT m_iStepCount; unsigned char m_iTargetChess [9]; unsigned char m_iChess [9]; HWND m_hClientWin; PathList * m_pPathList; bool m_bAutoRun; private : inline bool AddTree (DWORD place, PlaceList * & parent); void FreeTree (PlaceList * & parent); inline void ArrayToDword (unsigned char * array, DWORD & data); inline void DwordToArray (DWORD data, unsigned char * array); inline bool MoveChess (unsigned char * array, int way); bool EstimateUncoil (unsigned char * array); void GetPath (UINT depth); public: void MoveChess (int way); bool ComputeFeel (); void ActiveShaw (HWND hView); Void DrawGIRD (HDC HDC, Rect ClientRect); Void Drawchess (HDC HDC, Rect ClientRect); Void Reset (); Void Onbutton (Point Pnt, HWND HView); public PUBLIC : Cninegird (); ~ cninegird ();}; Calculating Random Random Aircraft Use the Vector Template with the random_shuffle (,) function to disrupt array data, and calculate what the target result is. Code:
Void cninegird :: reset () {if (m_bautorun) return; vector
vs; int i; for (i = 1; i <9; i ) vs.push_back (i); vs.push_back (0); random_shuffle (vs.begin (), vs.end ()); random_shuffle vs.begin (), vs.end ()); for (i = 0; i <9; i ) {m_ICHESS [i] = vs [i];} if (! Estimateuncoil (m_ICHESS)) {unsigned char Array [9] = {1, 2, 3, 8, 0, 4, 7, 6, 5}; Memcpy (m_iittergetchess, array, 9);} else {unsigned char Array [9] = {1,2,3 , 4, 5, 6, 7, 8, 0}; Memcpy (m_itargetchess, array, 9);} m_istepcount = 0;} Data Compression Function: Inline Void Cninegird :: ArrayTodWord (unsigned char * array, dword & data) { Unsigned char night = 0; for (int i = 0; i <9; i ) {if (array [i] == 8) {night = (unsigned char) i; break;}} array [night] = 0; DATA = 0; DATA = (DWORD) (DWORD) Array [0] << 29 | (dword) array [1] << 26 | (dword) array [2] << 23 | (dword) array [ 3] << 20 | (DWORD) Array [4] << 17 | (dword) array [5] << 14 | (dword) array [6] << 11 | (dword) array [7] << 8 | (DWORD) ARRAY [8] << 5 | Night); Array [Night] = 8;} Unzipped with compression is so good, unzip code:
Inline Void Cninegird :: DWORDTOARRAY (DWORD DATA, Unsigned Char * Array) {Unsigned Char Chtem; for (int i = 0; i <9; i ) {chtem = (unsigned char) (Data >> (32) i 1) * 3) & 0x00000007); Array [i] = chTEM;} chTem = (data & 0x0000001f); array [chTEM] = 8;} Due to expandable data volume is very large, plus I use the DWORD type when I saved, and record each step in a sorted binary tree. According to the rank from the left to the left to some, it is almost the form of nearly 10,000 times in the search. It is N times, and the functions used in the loop are declared as the inline function, and the inserted data will not be repeated in the tree when inserted. The overall speed is accelerated. Two-fork insertion code:
Inline Bool Cninegird :: AddTree (DWORD Place, Placelist * & Parent) {if (PARENT == Null) {Parent = New Placelist (); Parent-> Left = Parent-> Right = NULL; PARENT-> Place = place; Return true;} if (PARENT-> Place == Place) Return False; if (Parent-> Place> Place) {Return AddTree (Place, Parent-> Right);} Return AddTree (Place, Parent-> LEFT); } The calculation result is an odd alignment or an even-aligned code: BOOL CNINEGIRD:: Estimateuncoil (unsigned char * array) {int suun = 0; for (int i = 0; i <8; i ) {for (int J = 0; J <9; J ) {IF (Array [J]! = 0) {IF (Array [J] == i 1) Break; IF (Array [J]
Inline Bool Cninegird :: MoveChess (unsigned char * array, int WAY) {Int Zero, Chang; Bool Move = false; for (ZERO = 0; ZERO <9; Zero ) {ix (array [zero] == 0 Break;} Point PNT; PNT.x = zero% 3; pnt.y = int (zero / 3); switch (WAY) {case 0: // upif (PNT.Y 1 <3) {chang = PNT.Y 1) * 3 pnt.x; array [zero] = array [chang]; array [chang] = 0; Moveok = true;} Break; case 1: // downif (PNT.Y - 1> -1) {chang = (PNT.Y - 1) * 3 Pnt.x; Array [ZERO] = array [chang]; array [chang] = 0; Moveok = true;} Break; Case 2: // Leftif (PNT.X 1 <3) {chang = Pnt.y * 3 Pnt.x 1; Array [ZERO] = array [chang]; array [chang] = 0; Moveok = true;} Break; Case 3 : // Rightif (Pnt.x - 1> -1) {chang = Pnt.y * 3 Pnt.x - 1; array [zero] = array [chang]; array [chang] = 0; Moveok = true; } break;} if (moveok && m_bAutoRun!) {m_iStepCount ; DWORD temp1, temp2; ArrayToDword (array, temp1); ArrayToDword (m_iTargetChess, temp2); if (temp1 == temp2) {MessageBox (NULL, "you really Smart is so fast! " When you go to the target, we can get the optimal search path from the reverse search from the sub-node. Use the variable m_ipathsize to record the sum number, the specific function code:
void CNineGird :: GetPath (UINT depth) {int now = 0, maxpos = 100; UINT parentid; if (m_pPathList = NULL!) {delete [] m_pPathList;} m_pPathList = new PathList [maxpos]; parentid = m_pScanbuf [depth] .Scanid; dwordtoarray (m_pscanbuf [defst] .Place, m_ppathlist [ now] .path); While (ParentID! = -1) {if (now == maxpos) {MaxPos = 10; Pathlist * Temlist = New pathlist [maxpos]; memcpy (temlist, m_pPathList, sizeof (PathList) * (maxpos - 10)); delete [] m_pPathList; m_pPathList = temlist;} DwordToArray (m_pScanbuf [parentid] .Place, m_pPathList [ now] .Path) ParentID = m_pscanbuf [parentid] .scanid;} m_ipathsize = now;} The dynamic arrangement of the demo function is the easiest, in order to make the main form have a timely refresh opportunity, start a thread when the main form is refreshed, The SLE (UINT) function can be suspended. Code: unsigned __stdcall MoveChessThread (LPVOID pParam) {CNineGird * pGird = (CNineGird *) pParam; RECT rect; pGird-> m_iStepCount = 0; :: GetClientRect (pGird-> m_hClientWin, & rect); for (int i = pGird-> m_ipathsize; i> 0; i -) {memcpy (pgird-> m_icles, pgird-> m_ppathlist [i] .path, 9); pgird-> m_istepcount ; invalidateect (pgird-> m_hclientwin, & recent, false); Sleep (300);} char msg [100]; sprintf (msg, "^ _ ^! Get it! / R / n calculation steps When using% D milliseconds", pgird-> m_itime); MessageBox (null, msg, "~ _ ~ ", 0); pgird-> m_bautorun = false; return 0L;} Last introduction to the principle of search functions, first get the source array, convert it into DWORD type, compare it with the target, if the same is complete, different exchange Data and space location, join the binary tree, search for the next result until no step can be left, search for sub-positions that have just been searched, so until the target result is found, the function:
