knight's tour question
Hello! I have some C++ question with this program.
A knight in chess can move to any square on the standard 8x8 chess board from any other square on the board, given enough turns. Its basic move is two steps forward and one step to the side. It can face any direction. The knight wants to travel from a starting square to an ending square. Don’t allow any moves to go off the board. Notice that there are some traps on the chess board. The knight cannot move to any trap square. Can the knight arrive at his destination? If yes, what is the minimum number of movements along the path?
I really don't know how can I make a program to solve these questions.Can anyone help me? I am really confused.
A knight in chess can move to any square on the standard 8x8 chess board from any other square on the board, given enough turns. Its basic move is two steps forward and one step to the side. It can face any direction. The knight wants to travel from a starting square to an ending square. Don’t allow any moves to go off the board. Notice that there are some traps on the chess board. The knight cannot move to any trap square. Can the knight arrive at his destination? If yes, what is the minimum number of movements along the path?
I really don't know how can I make a program to solve these questions.Can anyone help me? I am really confused.
Although there are the inputs and outputs, I still do not know what to do.
input:
8
1 2
3 6
0
output:
Yes
2
(1 2)
(2 4)
(3 6)
input:
8
1 2
3 6
0
output:
Yes
2
(1 2)
(2 4)
(3 6)
I would start with a chessboard and a pen and paper and solve the problems there. Once you understand the problem you will get ideas how to code it.
I have already write down some path that the knight will pass through, I understand the question yet I don not know how to code it. Maybe I am just the beginner in programming :)
It's probably too difficult for a beginner but if you insist just Google for knight problem C++
Explain the input. (What is the 8? What is the 0?)
What is a "trap"?
How are they indicated in the input?
BTW, this is not the "Knight's Tour" problem.
What is a "trap"?
How are they indicated in the input?
BTW, this is not the "Knight's Tour" problem.
Without traps you could probably solve this analytically.
With traps you may have to resort to a back-tracking algorithm.
With traps, just use Dijkstra's algorithm.
As @dutch says, your input example is ill-defined. I'm guessing - because you haven't said - that the 8 refers to the size of the board and the 0 is the number of traps. How do you (or would you, in general) specify traps?
With traps, just use Dijkstra's algorithm.
As @dutch says, your input example is ill-defined. I'm guessing - because you haven't said - that the 8 refers to the size of the board and the 0 is the number of traps. How do you (or would you, in general) specify traps?
Last edited on
Topic archived. No new replies allowed.