The problem is described on a given size square, put the chess pieces "Horse" in the designated start position, the rules of the "horse" walking the "horse" must go to the "day" word on the board; from the chess pieces "horse "The starting position begins, searching a feasible path, making the chess pieces" Horse "can walk all the fallen points on the board, and each falling point can only take one;
For example: the size of the chessboard is 5 * 5, the starting falling point of the chessia horse is (3, 3); the algorithm needs to search for a one from the position (3, 3) including from (1, 1), (1, 2) ), (1, 3), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5) a total of 25 cans of the fall;
Problem Analysis Through the above problem description, we have a correct understanding of the content, and we begin to make specific and detailed analysis of the problem, in order to find the correct and viable reasonable way to solve the problem;
First we need to use the appropriate data structure in the program to represent the board, chess pieces, chess pieces of chess pieces in the problem; then we need to analyze the core issues, that is, how to search for a feasible path, what kind of strategy How to say the process of search;
For a chessboard with a size of N * m, the chess pieces are deployed from the current position (x, y), which can reach the next position (x ', y'):
(1) (x 1, y 2) (2) (x 1, y -2) (3) (x - 1, y 2) (4) (x - 1, y - 2) (5) (x 2, y 1) (6) (x 2, y - 1) (7) (x -2, y 1) (8) (x -2, y - 1)
limitation factor:
1. 1 <= x '<= n, 1 <= y' <= m; (N: The height of the chessboard, M: the width of the chessboard); 2. (x ', y') must be in the chess pieces not The new location included; 3. The chess piece walks the procedure record table does not include all the position of the falling laser on the board;
The process of keeping iterations for this process is the process of solving the space search, search until the chess pieces walk the record table including all the fallen locations on the board, you search for a feasible path, the path includes all the falls on the board. Point; or search for a complete solution space, still find a feasible solution, search failed;
Let us explain the process of searching;
Chess board size: 5 * 5 chess start position: (3, 3) search process:
(1) From the current position (3, 3), there can be 8 new location selections; first select the new location 1, put the new position 1 as the current chess position, start a new search; if the search is unsuccessful, search rollback , Select a new location 2, so on, you can search for a complete solution space, as long as you have a solution from this problem, you can guarantee that you can search;
2) From the new location 1, you can select two new locations, first select position 1, start a new search from position 1; (3) The following picture is after 18 steps, starting from position 18 If there is no new location that has not been passed, you can choose, the search failed;
Search Retreat to 17 steps, start from location 17 In addition to 18 new location, from the map, you can see that there is no new location to choose, continue to roll back to 16 steps, search except 17 new location; I know that the search is complete, or searched for a problemless;
(4) The following figure shows the entire search process of successful search; system design one.
II. Class design three. Sequence diagram 4. Core algorithm design Through the above analysis, we can now write the approximate framework of the algorithm. For details, please refer to this article later.
Below we will first list the framework of the classic retrospective algorithm; because the retrospective algorithm used in this paper, the clipper algorithm is appropriately modified;
Classic algorithm:
Void BackTrack (INT T)
{
IF (t> n) Output (x);
Else
For (INT I = f (n, k); i <= g (n, k); i )
{
x [t] = h (i);
IF (ConsTraint (T) && Bound (k)) Backtrack (k 1);
}
}
Algorithms used herein:
BOOL Search (Location Curloc) // Start calculation;
{
M_complex ;
/ / Modify the board mark;
m_chesstable [curloc.x-1] [curloc.y-1] = 1;
/ / Search successfully;
IF (Issuccess ())
Return True;
// There is still no coming, start searching from the current location;
Else
{
// Recursively search for unvereded chess panel;
For (int i = 0; i <8; i )
{
Location newLocation = GetSubtreenode (CURLOC, I);
IF (IsValide &&&&&& "&&&&
m_chesstable [newlocation.x-1] [newlocation.y-1] == 0)
{
IF (Search (newLocation) == True)
{
// Fill in the record table;
Markintable (NewLocation, CURLOC);
Return True;
}
}
}
}
/ / Search failed, restore the chess board logo;
m_chesstable [curloc.x-1] [curloc.y-1] = 0;
Return False;
}
Test data and test results
(1). Test data 1:
Chess sheet size chess start position (1, 1) (4, 4) (2, 3) ... Search the feasible solution without search solution space size 2223223501 ...
Conclusion: This issue is unfair to 4 * 4 and less than 4 * 4 chessboards.
(2). Test data 2:
Chessboard size: 5 * 5 chess start position: (1, 1) Search Solution Space: 76497
Search results illustration:
Features: (3, 3) Search Solution Space Size: 11077
Search results illustration:
Conclusion: For the 5 * 5 chessboard, this problem has a problem with the problem, the search solution is different from the starting position of the chess, from some positions starting, this problem may not be able to solve;
(3). Test data 3:
Chessboard size: 6 * 6
Chess start position: (4, 2)
Searched to solve: 2029720
The results are shown: (4). Test data 4:
Chessboard size: 7 * 7 chess start position: (3, 3) Search Solution Size: 12799463
The result is shown:
Conclusion Through multi-group data test, we found that when the height <= 5, the width width <= 5, the problem of the problem of the board problem is relatively small, and the algorithm used in this paper can search for intact in a short period of time. Sink space;
When the board is 5 * 5, the whole solution is 1829421 = 2 (21); because some of the characteristics of the chessboard and chess pieces (such as: the chess pieces can only reach some special points on the board, and these points must Not included in the walk record table), this brings some difficulties to analyze the time complexity of the chess board algorithm, we can only analyze the time complexity of the algorithm through the characteristics of different size chessboards, through the actual test (in The checkerboard size is 5 * 5), the estimated time complexity is basically in a quantitude complexity and the actual complexity;
The figure above is a 5 * 5-size chess board, and the position of the box is located (3, 3) has 8 points, while the next time, there is 2 points from the next time, there is 2 points, There are 25 - 1 - 8 = 16 points, and the four points in 16 points have not been passed. From these 4 points, there are 2 new search points that can be reached, when the board More than half of the above points have all passed, then the new search point that can be reached from the remaining 12 points is only 1;
Through the above analysis, we can get Space (5 * 5) = 8 * POW (2, 8) * POW (2, 4) * 12 = POW (2, 20); Similarly, we can size 8 * 8 decisions; Of course, some special points in the estimates are some techniques and actual experience, although the final result may not be accurate, but it can guarantee that it is basically on a quantitude;
Space (8 * 8) = POW (4, 8) * POW (4, 4) * POW (2, 20) * POW (2, 32);
It can be seen that the solution space is quite large. We assume that the computer is searched for 3 million steps. For the chess pieces "Ma" gives a starting position, if you want to prove that this problem does not solve, you need to search for the time (below The numbers are estimated):
Time (8 * 8) = Space (8 * 8) / 3 million = POW (2, 76) / 3 million = POW (2, 62) Minutes =
POW (2, 56) = POW (2, 47) = 128 billion years
Note: POW (x, y) represents Y, the Y number;
It can be seen that all solutions to search for a size of 8 * 8 board problems are not possible;
The time complexity of the algorithm is POW (2, n), is a NP difficult solution
