First method, depth search recursive method / * Code by my blog at 2004.10.13 independent diamond chess, deep search, recursive call method * /
#include
#define in 1 // Have a chess piece #define notin 0 // No chess pieces #define neverin 2 // Not arrived position #define MaxN 7 // Chessboard size #define Step 31 // 31 end
INT C [MAXN 1] [MAXN 1]; // Storage space INT Pass [4] [2] = {{0, -1}, {- 1, 10}, {0, 1}, {1, 0}}; // four direction skip position int REACH [4] [2] = {{0, -2}, {- 2, 0}, {0, 2}, {2, 0}}; / / Four directions arrival position bool Findit = false; // Record to find the result
/ / Output a chess game void output (int C [】 [MAXN 1]); // Recursive search solution Void search (int Depth);
INT main (void) {ifstream cin ("cin.txt"); // input for (int i = 1; i <= maxn; i ) {for (int J = 1; j <= maxn; j ) {cin >> C [I] [j];}} // Handling Search (0); // Output System ("PAUSE"); Return 0;}
Void search (int Depth) {if (depth == step && c [4] [4] == 1) {// arrived at the target location Cout << "find solution, pour the following: / n"; OUTPUT (C ); Findit = true; return;} int x1, y1, x2, y2; for (int i = 1; i <= maxn; i ) {for (int J = 1; j <= maxn; j ) {IF C [i] [j] == in) {// has a chess piece for (int K = 0; k <4; k ) {// 4 direction x1 = i pass [k] [0]; y1 = j Pass [k] [1]; x2 = i reach [k] [0]; Y2 = j reach [k] [1]; if (x1> = 1 && x1 <= maxn && y1> = 1 && y2 <= maxn && c [x1 ] [Y1] == In // Skip position There is a child && x2> = 1 && x2 <= maxn && y2> = 1 && y2 <= maxn && c [x2] [y2] == notin) {// reach the position is empty C [i] [j] = notin; // Initial position blank C [x1] [y1] = notin; // Skip position blank C [x2] [Y2] = in; // Jumping to position to PEG Search ( DEPTH 1); // Skip to the target position C [i] [j] = in; // Restore C [x1] [y1] = in; C [x2] [y2] = notin; if (Findit == True ) {OUTPUT (C); Return;}}}}}}}
Void Output (int C [] [MAXN 1]) {cout << "****************************** ************************* / N "; for (int i = 1; i <= maxn; i ) {for (int J = 1 J <= maxn; j ) {cout << C [i] [j] << "";} cout << "/ n";}} second: common method depth search Open set and closed set algorithm It is prepared to prepare the heuristic template with a heap. #ifndef node_h # Define node_h
#include
Class node {
Friend Ostream & Operator << (Ostream & Output, Const Node & Op2); // Output Current Layout
PUBLIC:
INT C [34]; // Chess Status Int MoveID [32]; // Squares of the moving piece number, the 0th element stores the number of steps from the chess game INT Dirction [32]; // Arrived at the movement direction of the bureau, 1, 2, 3, 4 is the up and down left and right int key; // key code, because the solution space is not large, only the depth search of Node ();
Bool Operator> (const node & op2) const; // Take a reactor and vector requires a few operators of Bool Operator <(const node & op2) const; box Operator> = (const node & op2) const; bool operator == ( Const Node & Op2) Const;
Void Output (Ostream & Out) const; // Output
Bool Up (Int ID, Node & Next); // Determines the movement of a piece of picture, the moving layout has a NEXT node BOOL Down (INT ID, Node & next); Bool Left (INT ID, Node & next); Bool Right ( INT ID, NODE & NEXT);
}
# Endif # include
= {{0, 0}, {4, 9}, {5, 10}, {6, 11}, {9, 16}, {10,17 }, {11, 18}, {14, 21}, {15, 22}, {16, 23}, {17, 24}, {18, 25}, {19, 26}, {20, 27}, {0,0}, {0,0}, {23, 28}, {24, 29}, {25, 30}, {0, 0}, {0, 0}, {0, 0}, {0 , 0}, {28, 31}, {29, 32}, {30, 33}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0,0 }, {0,0}, {0,0}, {0,0}};
// The position INT UPIT [34] [2] = {0,0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0,0 }, {0,0}, {0, 0}, {0, 0}, {4, 1}, {5, 2}, {6, 3}, {0, 0}, {0, 0}, {0,0}, {0, 0}, {9, 4}, {10, 5}, {11, 6}, {0, 0}, {0, 0}, {14, 7}, {15 , 8}, {16, 9}, {17, 10}, {18, 11}, {19, 12}, {20, 13}, {23, 16}, {24, 17}, {25,18 }, {28, 23}, {29, 24}, {30, 25}};
// Left-shifted position int LEFTIT [34] [2] = {0,0}, {0, 0}, {0, 0}, {2, 1}, {0, 0}, {0,0 }, {5, 4}, {0, 0}, {0, 0}, {8, 7}, {9, 8}, {10, 9}, {11, 10}, {12, 11}, {0,0}, {0,0}, {15, 14}, {16, 15}, {17, 16}, {18, 17}, {19, 18}, {0, 0}, {0 , 0}, {22, 21}, {23, 22}, {24, 23}, {25, 24}, {26, 25}, {0, 0}, {0, 0}, {29,28 }, {0,0}, {0,0}, {32, 31}};
{= 0 0,}, {5,6}, {0,0, 0}, {0,0}, {5,6}, {0,0}, {0,0}, {5,6}, {0,0 }, {0,0}, {8, 9}, {9, 10}, {10, 11}, {11, 12}, {12, 13}, {0, 0}, {0, 0}, {15, 16}, {17, 18}, {18, 19}, {19, 20}, {0,0}, {0, 0}, {22, 23}, {23 24}, {24, 25}, {25, 26}, {26, 27}, {0, 0}, {0, 0}, {29, 30}, {0, 0}, {0,0 }, {32, 33}, {0,0}, {0,0}}; // Down 1, Up 2, Left 3, Right 4; Bool Node :: Down (INT ID, NODE & NEXT) {IF ( Downit [ID] [0] == 0) {// Due to the outbreak of the movement, return false cannot be shifted;} else {if (c [c [i]]] [0]] == 1 && C [Downit [ID] [1 ]] == 0) {next = * this; // Copy the current NEXT.KEY ;
// Moved chess bureau next.c [id] = 0; Next.c [Downit [ID] [0]] = 0; Next.c [Downit [ID] [1]] = 1;
// Record the number of steps reached by NEXT.MOVEID [0] ; Next.Moveid [Next.MoveID [0]] = ID; Next.dirction [Next.MoveID [0]] = 1;
Return true;} else {// Due to the post-moving position is not allowed to be removed false;}}}}}}}}}}
Bool Node :: Up (Int ID, Node & Next) {IF (Upit [ID] [0] == 0) {// Due to the outbreak of the movement, return false is not shifted;} else {IF (C [Up [Id] [ 0] == 1 && C [UPIT [ID] [1]] == 0) {next = * this; // Copy the current NEXT.KEY ;
// Moved chess bureau next.c [id] = 0; Next.c [Upit [ID] [0]] = 0; Next.c [Upit [ID] [1]] = 1;
// Record the number of steps reached by next to next.moveid [0] ; Next.Moveid [Next.MoveID [0]] = ID; Next.dirction [Next.MoveID [0]] = 2; Return True;} Else {// Due to the post-moving position, it is not allowed to be removed false;}}}}}}}}}
Bool Node :: Left (Int ID, Node & Next) {if (Leftit [ID] [0] == 0) {// Because the outbord cannot be shifted by the outbord;} else {i (ip [ip [id] [ 0] == 1 && C [Leftit [ID] [1]] == 0) {next = * this; // Copy Next.Key ;
// Moved chess bureau next.c [id] = 0; Next.c [leftit [id] [0] = 0; Next.c [leftit [id] [1]] = 1;
// Record the number of steps reached by NEXT.MOVEID [0] ; Next.Moveid [Next.MoveID [0]] = ID; Next.Dirction [Next.MoveID [0]] = 3; Return True;} Else {// Due to the post-moving position, it is not allowed to be removed false;}}} Bool Node :: Right (INT ID, NODE & NEXT) {IF (Rightit [Id] [0] == 0) {Return False;} else { IF (C [Rightit [ID] [0] == 1 && C [Rightit [ID] [1]] == 0) {next = * this; // Copy Next.Key ;
// Moved chess bureau next.c [id] = 0; Next.c [rightit [id] [0]] = 0; Next.c [Rightit [Id] [1]] = 1;
// Record the number of steps reached by NEXT.MOVEID [0] ; Next.MoveId [Next.MoveID [0]] = ID; Next.dirction [Next.MoveID [0]] = 4; Return True;} else {Return False;}}}
Node :: node () {MEMSET (C, 0, SIZEOF (C)); MoveID [0] = 0;}
Bool Node :: Operator> (const node & op2) const {if (key> op2.key) Return True; Else Return false;} Bool Node :: Operator <(const node & op2) const {i (key
No., moving direction: to the right ./N ";} OUT << TMP;} OUT <<" / n ---------------------- Mobile completion - -------------------- / N ";} ostream & operator << (Ostream & Output, const node & op2) {OUTPUT <<" << op2.c [1] << "<< op2.c [2] <<" << op2.c [3] << "/ n"; OUTPUT << "<< op2.c [4] <<" "<< op2.c [5] <<" << op2.c [6] << "/ n"; for (INT i = 1; i <= 3; i ) {for (int J = 7 * i; j <7 * (i 1); j ) {OUTPUT << Op2.c [j ]< "";} Output << "/ n";} Output << "<< Op2.c [ 28] << "<< op2.c [29] <<" << op2.c [30] << "/ n"; output << "<< op2.c [31] <<" << op2.c [32] << "<< op2.c [33] <<" / n "; return output;} / * code by 01120136 My Blog AT 2004.10.9 Independent Diamond Chess Question, Depth Priority Search, try to clear the duplicate chess board number layout is as follows: 01 02 03 04 05 0607 08 09 10 11 12 13 14 15 16 17 18 19 20212 23 24 25 26 27 28 29 30 31 32 33 * /
#include
Vector
/ / Judgment if the NEXT node has expanded, returning True, otherwise falseBool Extended (Node & next); // Search Void search ();
INT main (void) {
Search (); system ("pause"); return 0;}
Void search () {// Initialization Node first; for (int i = 1; i <= 33; i ) {first.c [i] = 1;} first.c [17] = 0; first.key = 0 Open.push_back (first);
// Start loop while (! Open.empty ()) {cout << "is searching ... Extended node:" << closed.size () << "/ n"; make_heap (Open). Begin (), open.end ()); // Built the largest pile POP_HEAP (Open.BEGIN (), Open.end ()); // Remove the head element to prepare Node TMP = Open for heuristic search. Back (); open.pop_back (); // See if the node is the target node IF (tmp.moveid [0]> = 31 && tmp.c [17] == 1) {tmp.output (cout); // Outgoing Solution and returns OFStream Out ("out.txt"); tmp.output (out); return;}
// If it is not generated, all sub-status node next; BOOL HADIT; For (int i = 1; i <= 33; i ) {IF (tmp.c [i]! = 0) {IF (tmp.down i, next) {if (unxtnded == false) {// has not expanded Open.Push_Back (Next);}}}}}}}}}}}}}}}}}}}}}}}}}}}}} (tmp.Up (i, next)) {IF (Extended (Next) == false) {// has not expanded Open.Push_Back (Next);}}}} (tmp.LEFT (i, next)) {if (extended == false) {// has not expanded Open Open .push_back (next);}}}} (tmp.right (i, next)) {if (extended == false) {// has not expanded Open.push_back (next);}}}} // Put the Open Point I just taken into the closed table closed.push_back (tmp);}}
Bool Extended (Node & Next) {// If Next is in the closed, it has expanded, returns true for (ney = closed.egin (); iter! = closed.end (); ore ) {if (* iter = = Next) {RETURN TRUE;}} // Returns true; for (iter = open.begin (); iter! = open.egin (); it ) {if (* i == next ) {Return true;}} // None returns false returnaf false;}
