The Knight's Tour 4
Sep. 6th, 2009 09:28 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
davidnI have to wonder if solving a completely insurmountable Professor Layton puzzle by writing a program to work out the solution is considered cheating. They throw the original Knight's Tour problem at you, for goodness' sake - you're going to have to offer a lot more than 99 Picarats for me to work that out unaided.
dxn.knight.Solver
package dxn.knight;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class Solver {
private static List stateStack;
private static int stackPointer = 0;
private static State lastState;
private static Random random = new Random();
private static int maxStackSize = 0;
private static int maxDepth = 0;
private static int movesWithoutProgress = 0;
private static final int MOVES_TO_ATTEMPT = 100000;
public static void main(String[] args) {
//Put the initial state on the stack
stateStack = new ArrayList();
State initialState = new State();
stateStack.add(initialState);
stackPointer = 1;
lastState = initialState;
while (!lastState.isCompleted()) {
//If we haven't completed the puzzle yet, pull
//the latest state from the stack and then
//add its possible states (in random order) back to it
stackPointer--;
if (stackPointer == -1) {
System.out.println("Sorry, out of states...");
System.exit(0);
}
State currentState = stateStack.get(stackPointer);
lastState = currentState;
stateStack.remove(stackPointer);
List newStates = currentState.getAvailableStates();
stackPointer += newStates.size();
stateStack.addAll(shuffleStates(newStates));
//Show progress, if any
if (stateStack.size() > maxStackSize) {
maxStackSize = stateStack.size();
System.out.println("Biggest stack size: " + maxStackSize);
}
if (lastState.getDepth() > maxDepth) {
maxDepth = lastState.getDepth();
System.out.println("Best depth: " + maxDepth);
movesWithoutProgress = 0;
}
else {
movesWithoutProgress++;
}
//If we haven't got any further for a while
//it's probably not going to get anywhere -
//restart everything and hope it goes better next time
//(IT department solution)
if (movesWithoutProgress > MOVES_TO_ATTEMPT) {
System.out.println(MOVES_TO_ATTEMPT + " moves without progress, restarting");
stateStack = new ArrayList();
stateStack.add(initialState);
lastState = initialState;
stackPointer = 1;
movesWithoutProgress = 0;
maxDepth = 0;
maxStackSize = 0;
}
}
System.out.println("\nSolved it");
System.out.println("---------\n");
List solution = new ArrayList();
State solState = lastState;
while (solState != null) {
solution.add(solState);
solState = solState.getParent();
}
for (int i = solution.size()-1; i >= 0; i--) {
System.out.println(solution.get(i).toString());
}
}
public static List shuffleStates(List states) {
List shuffledStates = new ArrayList();
while (states.size() > 0) {
int index = random.nextInt(states.size());
shuffledStates.add(states.get(index));
states.remove(index);
}
return shuffledStates;
}
}
dxn.knight.State
package dxn.knight;
import java.util.ArrayList;
import java.util.List;
public class State {
public static final int BOARD_SIZE_X = 8;
public static final int BOARD_SIZE_Y = 8;
private char[][] board = new char[BOARD_SIZE_X][BOARD_SIZE_Y];
private int depth = 0;
private State parent = null;
public char[][] getBoard() {
char[][] boardCopy = new char[BOARD_SIZE_X][BOARD_SIZE_Y];
for (int y = 0; y < BOARD_SIZE_Y; y++) {
for (int x = 0; x < BOARD_SIZE_X; x++) {
boardCopy[x][y] = board[x][y];
}
}
return boardCopy;
}
public State() {
this.depth = 0;
for (int y = 0; y < BOARD_SIZE_Y; y++) {
for (int x = 0; x < BOARD_SIZE_X; x++) {
board[x][y] = '.';
}
}
board[0][0] = 'N';
}
public State(State oldState, Move moveToMake) {
//Copy the board and apply the given move to it to make the new state
char[][] newBoard = oldState.getBoard();
this.board = newBoard;
Move knightPos = getKnightPosition();
newBoard[knightPos.x][knightPos.y] = '!';
newBoard[knightPos.x+moveToMake.x][knightPos.y+moveToMake.y] = 'N';
this.board = newBoard;
this.depth = oldState.getDepth() + 1;
this.parent = oldState;
}
public int getDepth() {
return this.depth;
}
public State getParent() {
return this.parent;
}
//Create new states from this state - if a move leads to a
//blank space and it's not off the edge of the
//board, it's a possible state
public List getAvailableStates() {
List states = new ArrayList();
Move knightPos = getKnightPosition();
if (knightPos.x >= 2 && knightPos.y >= 1
&& board[(knightPos.x)-2][(knightPos.y)-1] == '.') {
states.add(new State(this, new Move(-2, -1)));
}
if (knightPos.x >= 2 && knightPos.y <= BOARD_SIZE_Y-2
&& board[(knightPos.x)-2][(knightPos.y)+1] == '.') {
states.add(new State(this, new Move(-2, 1)));
}
if (knightPos.x <= BOARD_SIZE_X-3 && knightPos.y >= 1
&& board[(knightPos.x)+2][(knightPos.y)-1] == '.') {
states.add(new State(this, new Move(2, -1)));
}
if (knightPos.x <= BOARD_SIZE_X-3 && knightPos.y <= BOARD_SIZE_Y-2
&& board[(knightPos.x)+2][(knightPos.y)+1] == '.') {
states.add(new State(this, new Move(2, 1)));
}
if (knightPos.x >= 1 && knightPos.y >= 2
&& board[(knightPos.x)-1][(knightPos.y)-2] == '.') {
states.add(new State(this, new Move(-1, -2)));
}
if (knightPos.x >= 1 && knightPos.y <= BOARD_SIZE_Y-3
&& board[(knightPos.x)-1][(knightPos.y)+2] == '.') {
states.add(new State(this, new Move(-1, 2)));
}
if (knightPos.x <= BOARD_SIZE_X-2 && knightPos.y >= 2
&& board[(knightPos.x)+1][(knightPos.y)-2] == '.') {
states.add(new State(this, new Move(1, -2)));
}
if (knightPos.x <= BOARD_SIZE_X-2 && knightPos.y <= BOARD_SIZE_Y-3
&& board[(knightPos.x)+1][(knightPos.y)+2] == '.') {
states.add(new State(this, new Move(1, 2)));
}
return states;
}
public Move getKnightPosition() {
for (int y = 0; y < BOARD_SIZE_Y; y++) {
for (int x = 0; x < BOARD_SIZE_X; x++) {
if (board[x][y] == 'N') {
return new Move(x, y);
}
}
}
return null;
}
public boolean isCompleted() {
for (int y = 0; y < BOARD_SIZE_Y; y++) {
for (int x = 0; x < BOARD_SIZE_X; x++) {
if (board[x][y] == '.') {
return false;
}
}
}
return true;
}
public String toString() {
String out = "";
for (int y = 0; y < BOARD_SIZE_Y; y++) {
out += getIndentString(depth);
for (int x = 0; x < BOARD_SIZE_X; x++) {
out += (board[x][y]);
}
out += "\n";
}
out += "Depth: " + getDepth();
return out;
}
public String getIndentString(int depth) {
String out = "";
for (int i = 0; i < depth; i++) {
out += " ";
}
return out;
}
}
dxn.knight.Move
package dxn.knight;
public class Move {
public int x;
public int y;
//This is a nice simple one
public Move(int x, int y) {
this.x = x;
this.y = y;
}
}
Output and solution path
Biggest stack size: 2
Biggest stack size: 6
Best depth: 1
Biggest stack size: 8
Best depth: 2
Biggest stack size: 14
Best depth: 3
Biggest stack size: 17
Best depth: 4
Biggest stack size: 18
Best depth: 5
Biggest stack size: 19
Best depth: 6
Biggest stack size: 22
Best depth: 7
Biggest stack size: 27
Best depth: 8
Biggest stack size: 28
Best depth: 9
Biggest stack size: 32
Best depth: 10
Biggest stack size: 37
Best depth: 11
Biggest stack size: 41
Best depth: 12
Biggest stack size: 47
Best depth: 13
Biggest stack size: 51
Best depth: 14
Biggest stack size: 56
Best depth: 15
Biggest stack size: 61
Best depth: 16
Biggest stack size: 65
Best depth: 17
Biggest stack size: 70
Best depth: 18
Biggest stack size: 73
Best depth: 19
Biggest stack size: 77
Best depth: 20
Biggest stack size: 81
Best depth: 21
Biggest stack size: 84
Best depth: 22
Biggest stack size: 85
Best depth: 23
Biggest stack size: 86
Best depth: 24
Biggest stack size: 89
Best depth: 25
Biggest stack size: 90
Best depth: 26
Best depth: 27
Biggest stack size: 92
Best depth: 28
Best depth: 29
Biggest stack size: 94
Biggest stack size: 98
Best depth: 30
Biggest stack size: 100
Best depth: 31
Best depth: 32
Best depth: 33
Biggest stack size: 101
Biggest stack size: 102
Best depth: 34
Best depth: 35
Biggest stack size: 104
Best depth: 36
Biggest stack size: 105
Best depth: 37
Biggest stack size: 106
Best depth: 38
Biggest stack size: 109
Best depth: 39
Biggest stack size: 110
Best depth: 40
Biggest stack size: 111
Best depth: 41
Biggest stack size: 112
Best depth: 42
Best depth: 43
Biggest stack size: 113
Best depth: 44
Biggest stack size: 114
Best depth: 45
Best depth: 46
Best depth: 47
Best depth: 48
Best depth: 49
Best depth: 50
Best depth: 51
Best depth: 52
Best depth: 53
Best depth: 54
Best depth: 55
Best depth: 56
100000 moves without progress, restarting
Biggest stack size: 2
Biggest stack size: 6
Best depth: 1
Biggest stack size: 12
Best depth: 2
Biggest stack size: 16
Best depth: 3
Biggest stack size: 20
Best depth: 4
Biggest stack size: 26
Best depth: 5
Biggest stack size: 30
Best depth: 6
Biggest stack size: 34
Best depth: 7
Biggest stack size: 39
Best depth: 8
Biggest stack size: 40
Best depth: 9
Biggest stack size: 43
Best depth: 10
Biggest stack size: 48
Best depth: 11
Biggest stack size: 53
Best depth: 12
Biggest stack size: 57
Best depth: 13
Biggest stack size: 58
Best depth: 14
Biggest stack size: 60
Best depth: 15
Biggest stack size: 64
Best depth: 16
Biggest stack size: 66
Best depth: 17
Biggest stack size: 67
Best depth: 18
Biggest stack size: 70
Best depth: 19
Biggest stack size: 71
Best depth: 20
Biggest stack size: 72
Best depth: 21
Biggest stack size: 73
Best depth: 22
Biggest stack size: 76
Best depth: 23
Biggest stack size: 77
Best depth: 24
Biggest stack size: 79
Best depth: 25
Biggest stack size: 83
Best depth: 26
Biggest stack size: 86
Best depth: 27
Biggest stack size: 87
Best depth: 28
Biggest stack size: 89
Best depth: 29
Biggest stack size: 91
Best depth: 30
Biggest stack size: 92
Best depth: 31
Biggest stack size: 95
Best depth: 32
Best depth: 33
Biggest stack size: 96
Best depth: 34
Biggest stack size: 99
Best depth: 35
Biggest stack size: 102
Best depth: 36
Biggest stack size: 103
Best depth: 37
Biggest stack size: 105
Best depth: 38
Biggest stack size: 108
Best depth: 39
Biggest stack size: 109
Best depth: 40
Biggest stack size: 110
Best depth: 41
Best depth: 42
Biggest stack size: 111
Best depth: 43
Best depth: 44
Best depth: 45
Best depth: 46
Best depth: 47
Biggest stack size: 112
Biggest stack size: 113
Best depth: 48
Best depth: 49
Best depth: 50
Best depth: 51
Best depth: 52
Best depth: 53
Best depth: 54
Best depth: 55
Best depth: 56
Best depth: 57
100000 moves without progress, restarting
Biggest stack size: 2
Biggest stack size: 6
Best depth: 1
Biggest stack size: 12
Best depth: 2
Biggest stack size: 15
Best depth: 3
Biggest stack size: 21
Best depth: 4
Biggest stack size: 26
Best depth: 5
Biggest stack size: 28
Best depth: 6
Biggest stack size: 32
Best depth: 7
Best depth: 8
Biggest stack size: 36
Best depth: 9
Biggest stack size: 38
Best depth: 10
Biggest stack size: 43
Best depth: 11
Biggest stack size: 44
Best depth: 12
Biggest stack size: 45
Best depth: 13
Biggest stack size: 49
Best depth: 14
Biggest stack size: 51
Best depth: 15
Biggest stack size: 55
Best depth: 16
Biggest stack size: 59
Best depth: 17
Best depth: 18
Biggest stack size: 61
Best depth: 19
Biggest stack size: 64
Best depth: 20
Best depth: 21
Biggest stack size: 68
Best depth: 22
Biggest stack size: 69
Best depth: 23
Biggest stack size: 75
Best depth: 24
Biggest stack size: 76
Best depth: 25
Biggest stack size: 78
Best depth: 26
Biggest stack size: 79
Best depth: 27
Best depth: 28
Biggest stack size: 83
Best depth: 29
Best depth: 30
Biggest stack size: 84
Best depth: 31
Biggest stack size: 86
Best depth: 32
Biggest stack size: 87
Best depth: 33
Biggest stack size: 90
Best depth: 34
Biggest stack size: 94
Best depth: 35
Biggest stack size: 95
Best depth: 36
Biggest stack size: 96
Best depth: 37
Best depth: 38
Biggest stack size: 99
Best depth: 39
Biggest stack size: 102
Best depth: 40
Best depth: 41
Biggest stack size: 104
Best depth: 42
Biggest stack size: 106
Best depth: 43
Best depth: 44
Biggest stack size: 108
Best depth: 45
Best depth: 46
Best depth: 47
Best depth: 48
Best depth: 49
Best depth: 50
Best depth: 51
Best depth: 52
Best depth: 53
Biggest stack size: 110
Best depth: 54
Best depth: 55
Best depth: 56
Best depth: 57
Best depth: 58
Best depth: 59
Best depth: 60
Best depth: 61
Best depth: 62
Best depth: 63
Solved it
---------
N.......
........
........
........
........
........
........
........
Depth: 0
!.......
........
.N......
........
........
........
........
........
Depth: 1
!.......
........
.!......
...N....
........
........
........
........
Depth: 2
!.......
..N.....
.!......
...!....
........
........
........
........
Depth: 3
!.......
..!.....
.!..N...
...!....
........
........
........
........
Depth: 4
!.......
..!.....
.!..!...
...!....
.....N..
........
........
........
Depth: 5
!.......
..!.....
.!..!...
...!...N
.....!..
........
........
........
Depth: 6
!.......
..!.....
.!..!...
...!...!
.....!..
......N.
........
........
Depth: 7
!.......
..!.....
.!..!...
...!...!
.....!..
......!.
........
.......N
Depth: 8
!.......
..!.....
.!..!...
...!...!
.....!..
......!.
.....N..
.......!
Depth: 9
!.......
..!.....
.!..!...
...!...!
.....!..
......!.
.....!..
...N...!
Depth: 10
!.......
..!.....
.!..!...
...!...!
.....!..
..N...!.
.....!..
...!...!
Depth: 11
!.......
..!.....
.!..!...
...!...!
N....!..
..!...!.
.....!..
...!...!
Depth: 12
!.......
..!.....
.!..!...
...!...!
!....!..
..!...!.
.N...!..
...!...!
Depth: 13
!.......
..!.....
.!..!...
...!...!
!....!..
..!N..!.
.!...!..
...!...!
Depth: 14
!.......
..!.....
.!..!...
...!...!
!....!..
..!!..!.
.!...!..
...!N..!
Depth: 15
!.......
..!.....
.!..!...
...!...!
!....!..
..!!..!.
.!N..!..
...!!..!
Depth: 16
!.......
..!.....
.!..!...
...!...!
!....!..
..!!N.!.
.!!..!..
...!!..!
Depth: 17
!.......
..!.....
.!..!...
...!...!
!....!..
..!!!.!.
.!!..!N.
...!!..!
Depth: 18
!.......
..!.....
.!..!...
...!...!
!....!.N
..!!!.!.
.!!..!!.
...!!..!
Depth: 19
!.......
..!.....
.!..!.N.
...!...!
!....!.!
..!!!.!.
.!!..!!.
...!!..!
Depth: 20
!......N
..!.....
.!..!.!.
...!...!
!....!.!
..!!!.!.
.!!..!!.
...!!..!
Depth: 21
!......!
..!..N..
.!..!.!.
...!...!
!....!.!
..!!!.!.
.!!..!!.
...!!..!
Depth: 22
!..N...!
..!..!..
.!..!.!.
...!...!
!....!.!
..!!!.!.
.!!..!!.
...!!..!
Depth: 23
!..!...!
..!..!..
.!N.!.!.
...!...!
!....!.!
..!!!.!.
.!!..!!.
...!!..!
Depth: 24
!..!...!
N.!..!..
.!!.!.!.
...!...!
!....!.!
..!!!.!.
.!!..!!.
...!!..!
Depth: 25
!..!...!
!.!..!..
.!!.!.!.
.N.!...!
!....!.!
..!!!.!.
.!!..!!.
...!!..!
Depth: 26
!..!...!
!.!..!..
.!!.!.!.
.!.!...!
!....!.!
N.!!!.!.
.!!..!!.
...!!..!
Depth: 27
!..!...!
!.!..!..
.!!.!.!.
.!.!...!
!....!.!
!.!!!.!.
.!!..!!.
.N.!!..!
Depth: 28
!..!...!
!.!..!..
.!!.!.!.
.!.!...!
!....!.!
!.!!!.!.
.!!N.!!.
.!.!!..!
Depth: 29
!..!...!
!.!..!..
.!!.!.!.
.!.!...!
!....!.!
!.!!!.!.
.!!!.!!.
.!.!!N.!
Depth: 30
!..!...!
!.!..!..
.!!.!.!.
.!.!...!
!....!.!
!.!!!.!.
.!!!.!!N
.!.!!!.!
Depth: 31
!..!...!
!.!..!..
.!!.!.!.
.!.!...!
!....!N!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 32
!..!...!
!.!..!..
.!!.!.!N
.!.!...!
!....!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 33
!..!...!
!.!..!..
.!!.!.!!
.!.!.N.!
!....!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 34
!..!...!
!.!..!N.
.!!.!.!!
.!.!.!.!
!....!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 35
!..!N..!
!.!..!!.
.!!.!.!!
.!.!.!.!
!....!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 36
!..!!..!
!.!..!!.
.!!.!N!!
.!.!.!.!
!....!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 37
!..!!.N!
!.!..!!.
.!!.!!!!
.!.!.!.!
!....!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 38
!..!!.!!
!.!.N!!.
.!!.!!!!
.!.!.!.!
!....!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 39
!.N!!.!!
!.!.!!!.
.!!.!!!!
.!.!.!.!
!....!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 40
!.!!!.!!
!.!.!!!.
.!!N!!!!
.!.!.!.!
!....!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 41
!.!!!.!!
!.!.!!!.
.!!!!!!!
.!.!.!.!
!...N!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 42
!.!!!.!!
!.!.!!!.
.!!!!!!!
.!N!.!.!
!...!!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 43
!.!!!.!!
!N!.!!!.
.!!!!!!!
.!!!.!.!
!...!!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 44
!.!!!.!!
!!!.!!!.
.!!!!!!!
N!!!.!.!
!...!!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 45
!.!!!.!!
!!!.!!!.
.!!!!!!!
!!!!.!.!
!.N.!!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 46
!.!!!.!!
!!!.!!!.
.!!!!!!!
!!!!N!.!
!.!.!!!!
!.!!!.!.
.!!!.!!!
.!.!!!.!
Depth: 47
!.!!!.!!
!!!.!!!.
.!!!!!!!
!!!!!!.!
!.!.!!!!
!.!!!N!.
.!!!.!!!
.!.!!!.!
Depth: 48
!.!!!.!!
!!!.!!!.
.!!!!!!!
!!!!!!.!
!.!.!!!!
!.!!!!!.
.!!!.!!!
.!.!!!N!
Depth: 49
!.!!!.!!
!!!.!!!.
.!!!!!!!
!!!!!!.!
!.!.!!!!
!.!!!!!N
.!!!.!!!
.!.!!!!!
Depth: 50
!.!!!.!!
!!!.!!!.
.!!!!!!!
!!!!!!N!
!.!.!!!!
!.!!!!!!
.!!!.!!!
.!.!!!!!
Depth: 51
!.!!!.!!
!!!.!!!N
.!!!!!!!
!!!!!!!!
!.!.!!!!
!.!!!!!!
.!!!.!!!
.!.!!!!!
Depth: 52
!.!!!N!!
!!!.!!!!
.!!!!!!!
!!!!!!!!
!.!.!!!!
!.!!!!!!
.!!!.!!!
.!.!!!!!
Depth: 53
!.!!!!!!
!!!N!!!!
.!!!!!!!
!!!!!!!!
!.!.!!!!
!.!!!!!!
.!!!.!!!
.!.!!!!!
Depth: 54
!N!!!!!!
!!!!!!!!
.!!!!!!!
!!!!!!!!
!.!.!!!!
!.!!!!!!
.!!!.!!!
.!.!!!!!
Depth: 55
!!!!!!!!
!!!!!!!!
N!!!!!!!
!!!!!!!!
!.!.!!!!
!.!!!!!!
.!!!.!!!
.!.!!!!!
Depth: 56
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!!!!!!
!N!.!!!!
!.!!!!!!
.!!!.!!!
.!.!!!!!
Depth: 57
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!.!!!!
!.!!!!!!
N!!!.!!!
.!.!!!!!
Depth: 58
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!.!!!!
!.!!!!!!
!!!!.!!!
.!N!!!!!
Depth: 59
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!.!!!!
!.!!!!!!
!!!!N!!!
.!!!!!!!
Depth: 60
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!N!!!!
!.!!!!!!
!!!!!!!!
.!!!!!!!
Depth: 61
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!!!!!!
!N!!!!!!
!!!!!!!!
.!!!!!!!
Depth: 62
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!!!!!!
!!!!!!!!
N!!!!!!!
Depth: 63
Additional challenge: Do it in ZZT.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-09-06 03:28 pm (UTC)no subject
Date: 2009-09-06 10:21 pm (UTC)