When someone suggested that I solve Knight's Tour, I did so with heuristics and recursion.
It takes a lot of time to solve even a 8x8 board:
N-A1
N-C2
N-E1
...
N-E6
N-F4Time used to solve: 5417011 nanoseconds
That seems quite a lot, but the most interesting part of my algorith is that it takes only six times the time for a 50x50 board:
N-A1
N-C2
N-E1
...
N-I32
N-K31Time used to solve: 33299062 nanoseconds
Solver.java:
public class Solver {
private static StringBuilder result = new StringBuilder();
public static String getResult() {
return result.toString();
}
public static boolean solve(int size) {
KnightBoard board = new KnightBoard(size);
Position start = new Position(1, 1);
board.set(start, true);
board.setKnightPosition(start);
return solve(board);
}
private static boolean solve(KnightBoard board) {
if (board.isAllBeenOn()) {
return true;
}
Position[] possibleMoves = board.possibleMoves();
if (possibleMoves.length == 0) {
return false;
}
int index = 0;
for (int i = 0; i < possibleMoves.length; i++) {
int posMoves = board.possibleMoves(possibleMoves[i]).length;
int indexPosMoves = board.possibleMoves(possibleMoves[index]).length;
if (posMoves < indexPosMoves || (posMoves == indexPosMoves && board.getDegree(possibleMoves[i]) < board.getDegree(possibleMoves[index]))) {
index = i;
}
}
result.append(board.getCoord(board.getKnightLocation())).append("\n");
board.setKnightPosition(possibleMoves[index]);
board.set(possibleMoves[index], true);
return solve(board);
}
}
KnightBoard.java:
public class KnightBoard {
private static int[][] posMoves = { { 2, 1 },
{ 2, -1 },
{ -2, 1 },
{ -2, -1 },
{ 1, 2 },
{ 1, -2 },
{ -1, 2 },
{ -1, -2 } };
private int size;
private boolean[][] beenOn;
private Position knightPosition = new Position(1, 1);
private int[][] degree;
public KnightBoard(int size) {
this.size = size;
beenOn = new boolean[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
beenOn[i][j] = false;
}
}
setDegree();
}
private void setDegree() {
degree = new int[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if ((i == 0 && j == 0) || (i == 0 && j == size - 1)
|| (i == size - 1 && j == size - 1)
|| (i == size - 1 && j == 0)) {
degree[i][j] = 2;
} else if ((i == 1 && j == 0) || (i == 1 && j == size - 1)
|| (i == size - 2 && j == size - 1)
|| (i == size - 2 && j == 0) || (i == 0 && j == 1)
|| (i == 0 && j == size - 2)
|| (i == size - 1 && j == size - 2)
|| (i == size - 1 && j == 1)) {
degree[i][j] = 3;
} else if ((i == 1 && j == 1) || (i == 1 && j == size - 2)
|| (i == size - 2 && j == size - 2)
|| (i == size - 2 && j == 1)
|| (i == 0 && (j >= 2 && j < 6))
|| ((i >= 2 && i < 6) && j == 0)
|| (i == size - 1 && (j >= 2 && j < 6))
|| ((i >= 2 && i < 6) && j == size - 1)) {
degree[i][j] = 4;
} else if ((i == 1 && (j >= 2 && j < 6))
|| ((i >= 2 && i < 6) && j == 1)
|| (i == size - 2 && (j >= 2 && j < 6))
|| ((i >= 2 && i < 6) && j == size - 2)) {
degree[i][j] = 6;
} else {
degree[i][j] = 8;
}
}
}
}
public int getDegree(Position pos) {
return degree[pos.getX() - 1][pos.getY() - 1];
}
public int getSize() {
return size;
}
public void set(Position p, boolean beenOn) {
this.beenOn[p.getX() - 1][p.getY() - 1] = beenOn;
}
public boolean get(Position p) {
return this.beenOn[p.getX() - 1][p.getY() - 1];
}
public void setKnightPosition(Position p) {
this.knightPosition = p;
}
public Position getKnightLocation() {
return knightPosition;
}
public boolean isAllBeenOn() {
for (boolean[] bool : beenOn) {
for (boolean wasOn : bool) {
if (!wasOn) {
return false;
}
}
}
return true;
}
public String getCoord(Position p) {
return "N-" + toChar(p.getX()) + p.getY();
}
private String toChar(int x) {
String result = "";
while (true) {
if (x > 26) {
result += (char) ((x % 26) + 64);
x /= 26;
} else {
result += (char) (x + 64);
return result;
}
}
}
public Position[] possibleMoves() {
List<Position> result = new LinkedList<Position>();
for (int[] posMove : posMoves) {
int x = knightPosition.getX() + posMove[0];
int y = knightPosition.getY() + posMove[1];
if (x > 0 && y > 0 && x <= size && y <= size) {
Position possiblePos = new Position(x, y);
if (!get(possiblePos)) {
result.add(possiblePos);
}
}
}
return result.toArray(new Position[result.size()]);
}
public Position[] possibleMoves(Position position) {
List<Position> result = new LinkedList<Position>();
for (int[] posMove : posMoves) {
int x = position.getX() + posMove[0];
int y = position.getY() + posMove[1];
if (x > 0 && y > 0 && x <= size && y <= size) {
Position possiblePos = new Position(x, y);
if (!get(possiblePos)) {
result.add(possiblePos);
}
}
}
return result.toArray(new Position[result.size()]);
}
}
Position.java:
public class Position {
private int x;
private int y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
Main.java:
public class Main {
public static void main(String[] args) {
long time = System.nanoTime();
int solve = 50;
solve(solve);
System.out.println(getResult() + "\nTime used to solve: "
+ (System.nanoTime() - time) + " nanoseconds\n");
}
}
- Is there a way to make this more efficient with smaller boards?
- Can someone explain why the time required to solve are so close?
Any other general comments welcome.