Hi I am wondering how you would create a program for the knight tour instead of using recursion using a stack.
I just want the ideal behind using a stack/queue instead of recursion please no code:)
hellocsprogram 0 Newbie Poster
StuXYZ 731 Practically a Master Poster
The quick solution to this is to actually know the algorithm that the knights tour works on. It can be shown that for any size square and rectangular board (above a minimum size), that simply selecting the unvisited square with the least possible open moves from it, is the optimal strategy.
The use of an algorithm like that greatly simplifies the problem.
However, the question asked is how to do it with recusion and a stack.
There are several methods to do this but I will outline just one.
Consider the first move; the Knight has a number of positions to go to [we will ignore symmetry reductions that can simplify this further]
If we define a simple mechanism of ordering moves, say we use a clock trick e.g. the move at 1 o'clock is move 1, the move at 3o'clock is move 2 etc, if a move not possible [off side of the board], then just carry on counting to the next one.
Take the first move, put onto a stack the first option (always 1 in this case).
Next update the visited map, with the original square and the first move.
Take the second move, do the same, most likely the first square again so add another 1 to the stack. and update the visited map.
At some point you will get to a move were the first move (1) is blocked by a visited square, no problem look for the next move 2, if that is ok add 2 to stack etc and carry on.
Finally you will either (a) get to a solution or get to a point were
the knight has no legal moves. ok now you back track up the stack and try to iterate (loop) over the options for the previous move.
When you have exhausted all of those options you back track further
up the stack (removing the lower part of the stack and re adding elements as necessary).
At some point you will either (a) have a solution (b) have exhaused the original point on the stack and have proved there is no solution.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.