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.
no subject
Date: 2009-09-06 10:54 pm (UTC)The solver basically performs the clueless experimentation that I was doing, but much faster - it moves a knight around the board to any space that hasn't yet been visited, and if there are no available moves, it rewinds to the last place where there were and tries something else. And if it's tried 100,000 moves without filling in any more squares, it gives up entirely and starts again.
It's not the most intelligent way to solve it by any means - it's still a matter of luck whether its random exploration finds a solution - but it worked once, and that was all I needed it to do :)