Shulou(Shulou.com)06/01 Report--

This article mainly explains "how to use C++ code to realize horse pedal chessboard". The content of the explanation in the article is simple and clear, and it is easy to learn and understand. let's study and learn how to use C++ code to realize horse pedal chessboard.

(1) description of the classical algorithm of the horse pedal chessboard:

The main results are as follows: (1) Horse chessboard is one of the classical programming problems, and there are two main solutions: one is based on depth-first search, the other is based on greedy algorithm. The first method based on depth-first search is a more commonly used algorithm, and the depth-first search algorithm is also one of the classical algorithms in the data structure, which mainly uses the idea of recursion, level-by-level search, traversing all the results, and finally find the right solution. The algorithm based on greed is to establish the greedy criterion, once the setting can not be modified, he only cares about the local optimal solution, but may not get the optimal solution.

[problem description] about the basic process of the horse stepping on the chessboard: the chess board is an 8-8 checkered chessboard. Now put the "horse" in any specified box and move the "horse" according to the rules of the "horse" move. It is required that each box can only enter once, eventually making the "horse" walk all over the 64 squares of the chessboard.

[algorithm analysis]

① is in the four corners, Ma Ta-ri has only two choices.

② in the rest, Ma Ta Rizhao has four, six, eight choices.

Solution: add two additional layers to the outer layer to make sure that each grid in the 8-8 box has 8 different choices.

Important: in order to ensure that each grid can read Japanese characters, and the possibility of selection is the same, initialization except for the outermost two layers of grid tags is not accessed, each grid in the outermost two layers is marked as visited to achieve the goal!

Explanation: the area marked red in the picture is initialized by default to the horse has stepped on the Japanese character, the set has been accessed, and the table in the middle of 8x8 is marked as the horse has not been accessed!

And in each table, the horse has 8 different choices when visiting, and the different choices in these 8 will be appended to their corresponding x and y coordinates.

The selection of these 8 is as follows:

[code show 1]: recursive solution (backtracking solution), list all the solutions, and find out the appropriate solution starting from the (2jue 2) position:

# include # include using namespace std; int chessboard [12] [12] = {0}; int cnt = 0; / the number of squares marked the horse has gone int sum = 0; / / the specific number of schemes marking the horse to complete the whole journey int move [8] [2] = {{2jue 1}, {1mague 2}, {- 1magin 2}, {- 2ct 1}, {- 2ct 1}, {- 2ct 1}, {- 1m lyric 2}, {1m v 2} / / offset of the current position of the initial horse to the xjournal y of the eight adjacent Japanese characters around it / / output the solution void PrintChess () of the horse pedal chessboard; / / the recursive process void Horse (int x department int y) of the horse pedal chessboard; int main (void) {int iForce j; for (iP0TX I)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.