Not Yet Answered # Knight Tour Stack

StuXYZ 731

1

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.

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

get the input from user may include

-Bank balance

-Amount invested in business

-Amount given to other business partners as loan

and

-Amount payable to others

Made this in cpp.sh

Why would I need the x=y+1-1;?

x=y; just doesnt seem to work

Why is this?

And I know my coding ...

there are five tables (personTb, addressTb,churchTb) each holds data pertinent to an individual; (personAddress,personChurch) each hold the primary key for the person table and corresponding table IE personAddress holds primary key for addressTb.

both snippets work, my question is;** Is my join correctly formatted? **

```
select
concat(personTb.p_fName,' ',personTb.p_mName,'. ',personTb.p_lName) ...
```