I'm trying to solve the Knight's tour problem in Java. My goal is to calculate all possible tours of a horse on a chessboard with any dimension. What I have tried to use is an adjadency-lists data structure. The problem now, is that I know which squares are adjacent to a square, but I don't know what direction the adjacent square is in. How would I fix this?
The knight's tour problem is an instance of the more general Hamiltonian path problem in graph theory. The problem of finding a closed knight's tour is similarly an instance of the Hamiltonian cycle problem. Unlike the general Hamiltonian path problem, the knight's tour problem can be solved in linear time.
For example, on a 4x4 chessboard a knight's tour is also impossible. In fact, the 5 × 6 and the 3 x 10 chessboards are the smallest rectangular boards that have knight's tours.
The answer is: NO, mission impossible. The proof is pretty simple: To complete a knight's tour, the knight must make 63 moves- no more, no less.
Assigning a value to each square (determined by the knight's move order) and adding the numbers on each column and each row together always result in 260. William Beverley composed the first magic knight's tour in 1847.
Here's just a rough outline of what you should do:
Sample Square class:
public class Square
{
public final Square up;
public final Square down;
public final Square left;
public final Square right;
public Square(Square up, Square down, Square left, Square right)
{
this.up=up;
this.down=down;
this.left=left;
this.right=right;
}
public Square getUp(){return up;}
public Square getDown(){return down;}
public Square getLeft(){return left;}
public Square getRight(){return right;}
}
Sample Knight class:
public class Knight
{
private Square mySquare;
public Knight(Square start)
{
mySquare = start;
}
/* 7 0
* 6 1
*
* 5 2
* 4 3
*/
public boolean move(int dir)
{
switch(dir)
{
case 0: try{
mySquare=mySquare.getUp().getUp().getRight(); return true;
} catch (NullPointerException e) {return false}
case 1: try{
mySquare=mySquare.getUp().getRight().getRight(); return true;
} catch (NullPointerException e) {return false}
case 2: try{
mySquare=mySquare.getDown().getRight().getRight(); return true;
} catch (NullPointerException e) {return false}
case 3: try{
mySquare=mySquare.getDown().getDown().getRight(); return true;
} catch (NullPointerException e) {return false}
case 7: try{
mySquare=mySquare.getUp().getUp().getLeft(); return true;
} catch (NullPointerException e) {return false}
case 6: try{
mySquare=mySquare.getUp().getLeft().getLeft(); return true;
} catch (NullPointerException e) {return false}
case 5: try{
mySquare=mySquare.getDown().getLeft().getLeft(); return true;
} catch (NullPointerException e) {return false}
case 4: try{
mySquare=mySquare.getDown().getDown().getLeft(); return true;
} catch (NullPointerException e) {return false}
default: return false;
}
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With