There is a chessboard 8x8. Suppose each cell of the board contains a certain number of apples. A chess piece “knight” can walk according to the classic rules of the knight's move. Once in the next cage, the horse collects all the apples that are in it. There are restrictions on the number of moves. Your program should accept the following arguments as input: the maximum number of moves, the name of the file containing the scheme for filling the chessboard with apples. The lines in the file correspond to the lines of the chessboard, the lines are separated by hyphens. Numbers in rows are separated by spaces. Your program should display the maximum possible number of apples collected by the knight, with a given limit of moves and an arbitrary choice of the starting position.

Actually, I would like to understand how this method should be solved. I need the code itself, of course, but I think I can write a program myself if I understand its main idea. There was an idea to solve through the greedy algorithm, moving into a cell containing the maximum possible number of apples (compared the number of apples in each of the cells available at the moment and went into the cell with the maximum number), but, I think this solution is soft saying not quite right. The task must contain a recursion. Submit an idea for solving this program or advise literature on this topic, please. Thank you in advance! : D

  • 3
    Hm And where does the chess horse? - VladD
  • With that, I managed to insert the wrong condition. Alas, lack of sleep is to blame =) - Andrei Gabrielyan
  • I remember something like that was solved (I don’t remember what exactly the task was, but just about the horse). It is necessary to consider the chessboard as a graph (as already written by @KoVadim), it is most convenient to work with the graph using the adjacency list. And then I can’t offer anything smarter than brute force - Donil

3 answers 3

I think that such problems are solved by complete brute force. That is, for each cell we do a complete search of moves. Yes, it will be a long time, but ...

Experts can solve the problem in another way. A chessboard for a horse is a graph. The number of apples in a cage is the value at the top. The task is to search for a chain with a maximum amount. In graph theory, there are many algorithms for finding the shortest path , but I think they will easily “turn over”.

  • A complete search will not work, since each step has branch 2..8 and the number of steps can reach 63, that is, about 2 63..8 63 operations (closer to the second digit) are 20..50 zeros in after one in number. - jfs

Well, in addition to the mentioned graph, it is also worth adding that your variant with the greedy algorithm is incorrect. Just because the path 2-1 will give less than the path 1-9, which will be ignored by a similar greedy algorithm.

It is worth noting that the knight goes to any point on the board in 4-5 moves, so a good graph will be very confusing in this task and rather complicated in construction and analysis. Therefore, to simplify it, you can use its private view - an undirected octary (according to the number of moves of a horse) tree with a height that limits the moves of a horse.

    I don’t know if it will work in this case, but since in the task it is necessary to find only the “maximum possible number of apples collected by the horse” without memorizing the distance traveled, it is possible to effectively implement it with dynamic programming if there is an optimal substructure in the problem (if the solution of the subtask is part of the optimal solution of the larger problem).