Sunday, December 12, 2021

Making Knight's Tour Part 4 of 4

 Part 4 of 4: Hamiltonian paths and circuits

When it comes to math, I do wish that I had done more math courses. I do not consider myself a math expert, though I use it all the time and feel it is important to at least understand the concepts. When it comes to Knight’s Tour, graph theory is the mathematical topic of choice for understanding what is going on. A graph is simply a set of vertices (often called nodes by programmers) connected by edges. The game can be represented as a graph with each tile of the board being a vertex and the paths that the knight can take being the edges. The image below shows this.



When travelling through the nodes, the sequence of vertices visited is a walk. If the vertices of the walk are all distinct then you have a path. There is a special path which is made up of all vertices in the graph known as a Hamiltonian path. When you think about it, any solution to the game is a Hamiltonian path.

There is another concept in graph theory called a circuit. The idea here is that you have a path but the last vertex of the path connects to the first vertex of the path to form a cycle. Taken to the extreme, if the circuit visits every vertex once (except the starting vertex) then you have a Hamiltonian circuit. In Knight’s Tour, if the last node in a solution is an L move away from the starting location, then you have a Hamiltonian Circuit. This is a very special solution to the puzzle as you have effectively found two solutions for each tile (going in either direction is fine). Finding a Hamiltonian Circuit is not difficult as you only need to add a constraint to the solver such that it can only take the L leading to the starting location if it is the last move. This will take a very long time as there are many valid solutions that will fail. Once you have found a Hamiltonian circuit, however, creating a solver that will use it is trivial.

Once you know the path, you can simply store that as an array of next tiles.

"hamiltonian": [10,11, 8,18,19,20,12,22,
               
25, 3, 4, 5, 2, 7,31,21,
                
1, 0,28,29,14, 6,39,13,
                
9,40,43,42,34,35,15,46,
               
17,16,44,45,26,47,23,54,
               
57,24,36,37,27,30,63,62,
               
33,32,56,61,58,59,60,38,
               
41,51,48,49,50,55,52,53]

The solver can then simply look up the next move in the circuit.

class KTHamiltonianSolver extends KTSolver {
   
constructor(game) {
       
super(game);
   
}

   
reset() {
       
this.game.restartGame();
   
}

   
nextMove() {
       
let curTile = this.game.lastKnightTile;
        let
target = KT.hamiltonian[curTile];
        this
.game.addKnight(target);
   
}

}

This may seem like cheating, and it sort of is, but using a precalculated solution is actually particularly useful for solving larger puzzles. Larger puzzles can be broken down into several smaller puzzles. If you have solutions that start at one edge and another edge, you can chain the puzzles together to solve larger puzzles without incurring the exponential growth that trying to solve the complete puzzle would incur. This is known as divide and conquer.

So, how do the different solvers compare? The table below shows how all four solvers did for each of the possible starting locations. Note that I only went to 10 billion steps. I also used a C++ version of the solvers so they ran much faster. 




Sunday, November 14, 2021

Making Knight's Tour part 3 of 4

 Heuristics

When you get right down to it, solving the knights tour is simply a search of really large tree.  The biggest problem is that if you take a wrong path then you end up wasting a large amount of time before you realize your mistake and come back track back up to where a viable solution can exist. The obvious solution to this is not to make bad mistakes, but how do you determine if a choice is a good choice or not? Human brains partially solve this problem by employing what is known as heuristics. The idea here is instead of doing complicated calculations the brain will look for shortcuts that usually, though not always, lead to the correct solution. With NP problems heuristics can be a very good way of solving the problems in a reasonable amount of time if you can find an appropriate heuristic.

Creating a heuristic is not a simple task. Usually several different techniques are tried to find out if any of them work with smaller versions of the problem set. The technique can then be applied to larger problems to see if they still work. Often we will start by looking at several versions of the problem and seeing if there's any pattern that can be found. The easiest way of finding a heuristic is to look at what other people have discovered and using their heuristic, but that requires an existing heuristic to already exist. Knight's tour is very popular with mathematicians so several heuristics have been devloped.

For Knights tour the Warnsdorff's heuristic is the heuristic that dominates. This is a quite simple heuristic. The idea is that for each potential move you look at the number of moves that tile will have once you have moved there and selecting the tile that has the least moves available. As you can see by the figure below, each of the tiles that we can move to has a certain number of moves attached to it, but there is also a tie. There are several approaches that can be taken for dealing with ties, so I went with a clockwise order of searching tiles and taking the clock position as the tie-breaker.


One of the things that continually came up when researching this heuristic was that when there was a tie that would quite often be where the problem with the solution was. This would mean that tide tiles would be a good candidate for a faster backtracking method. For this reason I updated the reset function to also include an indication of whether there was a tie at particular decision tree node. 

reset() {
    for (let i = 0; i < 64; ++i) {
        this.game.tiles[i].step = 0;
        this
.game.tiles[i].tiebreaker = false;     } }

 The heart of this Huristic is the counting method. This simply looks to see if the tiles currently occupied with the night and if so returns negative one. The negative one is very important as it is possible at the very end of the game that a valid tile will have zero moves as it will be the only tile available to be moved into. We simply count all the possible moves making sure that we do not count the move back to our source tile.

countTargetMoves(target, source) {
   
if ((target < 0) || (target >= 64))         return -1;  // NOTE invalid is -1 not zero as last move will be 0 moves!!!
   
if ( ! this.game.tiles[target].checkIfAllowedMove(target, source) )         return -1;
    if
(this.game.tiles[target].moveNumber !== KT.NO_MOVE)         return -1;
    let
moveCount = 0;     for (let t = 0; t < KT.knightTileOffsets.length; ++t) {         let knight = target + KT.knightTileOffsets[t];         if ((knight === source) || (knight < 0) || (knight >= 64))             continue;
        let
knightXAdjust = Math.abs( (knight % 8) - (target % 8) );
        let
knightYAdjust = Math.abs( Math.floor(knight / 8) - Math.floor(target / 8) );         if ( ((knightXAdjust+knightYAdjust) === 3) &&
            (
this.game.tiles[knight].moveNumber === KT.NO_MOVE) )
            ++moveCount
;     }     return moveCount }

 Sadly, my fast backtrack method was never tested but has been implemented here for reference. I know it was not used for reason that will become clear once the algorithm is ran. The idea behind fast backtracking is that you do not backtrack a single step but backtrack multiple steps to a decision point you know it is faulty. As we know that the tiles that have multiple tile entries are potential problem areas, this is a good point to do a fast backtrack too.

fastBacktrack() {
   
let curTileIndex = this.game.lastKnightTile;
    if
(curTileIndex === this.game.firstKnightTile) return;
    let
curTile = this.game.tiles[curTileIndex];
    this
.game.undoMove();
   
curTile.step = 0;
   
curTile.tiebreaker = false;
    if
( ! this.game.tiles[this.game.lastKnightTile].tiebreaker)         this.fastBacktrack();
}

 

The next move method seems a lot more complicated than it really is. The big problem that we have is that step is no longer linear as steps may be taken in totally different orders. To get around this problem, we are treating each bit of the step variable as one of the paths that we can take. If the bit is set then we know that path is either not available or has been tried already. To loop over the bits, we simply create a mask variable which we set to 1 to indicate the first bit. The left shift operator, which is represented using <<, is used to shift that one to the appropriate bit position. If the value of step is 255 then we know that all these steps have been tried and can do a backtrack. If moves are still available we simply loop over all the bits and find the lowest count from the moves that are remaining. The lowest move is then the move that we make. As it is simple enough to also do forward checking, we will call the is game still winnable method to do a forward checking step even though this is not required as part of the heuristic.

    nextMove() {
        
let curTile = this.game.lastKnightTile;
        let
step = this.game.tiles[curTile].step;
        let
tiebreaker = this.game.tiles[curTile].tiebreaker;
        if
(step === 255) {
//            this.game.undoMove();
//            step = 0;
           
return this.fastBacktrack();
       
} else {
           
let mask = 1;
            let
index = 0;
            let
lowest = -1;
            let
lowestCount = 9;
            let
lowestMask = 0;
            while
(mask < 256) {
               
if ((step & mask) === 0) {
                   
let target = curTile + KT.knightTileOffsets[index];
                    let
targetMoves = this.countTargetMoves(target, curTile);
//                    console.log(`target ${target} has ${targetMoves}`);
                   
if (targetMoves < 0)
                        step |= mask
;
                    else if
(targetMoves < lowestCount) {
                        lowest = target
;
                       
lowestCount = targetMoves;
                        
lowestMask = mask;
                   
} else if (targetMoves === lowestCount) {
                        tiebreaker =
true;
                   
}
                }
                mask <<=
1;
               
++index;
           
}
            
if (lowestMask > 0) {
                step |= lowestMask
;
                this
.game.addKnight(lowest);
                if
( ! this.game.isGameStillWinnable() ) {
                   
this.game.undoMove();
//                    console.log("Early backtracking!");
               
}
            }
else
               
console.log("No move found???")
        }
       
this.game.tiles[curTile].step = step;
        this
.game.tiles[curTile].tiebreaker = tiebreaker;
   
} 

Running with this Heuristic proved to be very efficient. as it turns out, the heuristic solver is able to find the solution in 63 steps for all of the possible starting locations. With the performance we are getting using this heuristic we are done, so why is there another solver in the game? My exploration of Knight’s Tour would not be complete without looking at circuits and larger boards.


Thursday, October 14, 2021

Making Knight's Tour part 2 of 4

 Part 2 of 4: Backtracking and forward checking

For Queen’s challenge, we started with a brute force approach and worked up to forward checking. For solving Knight’s Tour, we will start with a backtrack solver. our solver four nights tour is very similar to the one that we used for Queen's challenge. The solver class takes the main game class as its parameter which is used to help verify the game state and make moves on the board. There are two methods in the solver class with the first one being the reset method. This method simply loops through all the tiles in the board and sets the current step to 0. the step represents which of the eight moves that the knight has made.

reset() {
   
for (let i = 0; i < 64; ++i) {
       
this.game.tiles[i].step = 0;
   
}
}

 

The next move method is used by the game to perform the next step of the solution search. Here we are using the last tile that the knight was in and using the step value to figure out which directions we have already attempted. If all of the possible steps have been tried and none of them were successful, we know that we have to backtrack which is done by resetting the step to 0 and then calling the undoMove method in the game. If the next step to take is a valid step as determined by calling the checking routines we developed in the previous part, we take that step by calling the game’s addKnight method. Finally, if the next step was not a valid step, and we never backtracked,  we continue on to the next step by returning a recursive call to this method. This could have been also implemented as a while loop surrounding the entire method, but I find this way less complicated with the same results.

nextMove() {
   
let madeMove = false;
    let
curTile = this.game.lastKnightTile;
    let
step = this.game.tiles[curTile].step;
    if
(step >= KT.knightTileOffsets.length) {
        step =
0;
        this
.game.undoMove();
       
madeMove = true;
   
} else {
       
let target = curTile + KT.knightTileOffsets[step];
       
++step;
        if
((target >= 0) && (target < 64)) {
           
if (this.game.tiles[target].isTileAPotentialMove()) {
               
this.game.addKnight(target);
               
madeMove = true;
           
}
        }
    }
   
this.game.tiles[curTile].step = step;
    if
( ! madeMove)
       
return this.nextMove();
}

 

Within the code the startSolver method simply is passed the instance of the solver that is to be used and sets it as the solver. The reset for the solver is called and we set a timeout to call our NextSolverStep method to start solving the game.

startSolver(solver) {
   
this.solver = solver;
   
solver.reset();
   
setTimeout(this.nextSolverStep.bind(this), 10);
    this
.solverMoves = 0;
}

The nextSolverStep is designed to be called periodically and only performing a single solver step per iteration so that we can have a nicely animated solution. To allow for a fast mode, the number of times that we call the solver’s nextMove method will be dependent on a solvCount variable who’s value will be either 1 or 1000 toggled by pressing the Fast/Normal button. The number of steps that have been tried is updated and displayed to the user so they have some idea of how fast a particular method is.

nextSolverStep() {
   
if (this.solver == null)
       
return;
    for
(let i = 0; i < this.solveCount; ++i) {
       
if (this.knightCount < 63) {
           
this.solver.nextMove();
           
++this.solverMoves;
        }
    }
   
this.moveCountText.setText("" + this.solverMoves);
    if
(this.knightCount < 63)
       
setTimeout(this.nextSolverStep.bind(this), 25);
   
draw();
}

 

The fact that I added a fast button is probably a good indicator that the backtrack solver’s performance was not what we were hoping for with it taking 6484065 for the corner tile and many of the tiles taking over 10-billion attempts. The problem is that if an invalid move is made, it can take quite a while to finally backtrack to the move that is causing all the problems. We know from Queen’s Challenge that forward checking can solve that problem so that is what we are going to do next.

The forward checking implementation takes advantage of our isGameStillWinnable method to verify that a move is feasible. This is not the proper way to implement this as the routine is very slow but as we are animating the game so there will be no noticeable difference we can get away with our brute force method. This lets us have a very simple class.

class KTForwardSolver extends KTSolver {
   
constructor(game) {
       
super(game);
   
}

   
nextMove() {
       
if (this.game.isGameStillWinnable())
           
return super.nextMove();
       
console.log("Unsolvable so early backtrack");
        this
.game.tiles[this.game.lastKnightTile].step = 0;
        this
.game.undoMove();
   
}

}

 

So, what is wrong with the way I am doing the winnable check? It is very costly to do as you are doing  up to 64*8 checks to see if the board is still in a winning state.  So what would be a better way of doing this? Attach a domain array to each tile which holds which possible moves are still available. Whenever a move is made, remove the appropriate moves from the 8 affected tiles. If any of those tiles no longer have a potential move, then you know you are in an unwinnable state and can backtrack. I am leaving the implementation of this as an exercise for my readers.

Forward checking definitely helped the performance as the top left tile now only took 1731697 and there were fewer (though still a significant number) of tiles that required over 10 billion steps to solve. The problem is that we are making a bad decision early and it costs us much later in the solution, so it takes a long time to backtrack. If only we had a way to make better choices. This will be looked at next time.


Tuesday, September 14, 2021

Making Knight’s Tour part 1 of 4

Part 1: A Game of Knights

Knight’s tour is another chess-puzzle. The idea is that you are given a chess board, not necessarily 8x8 but for this version we are using the standard chess board.  The player is given a knight at a random  starting location on the board and using just the valid L-shaped move mechanic of the knight you must move around the entire board touching each square of the board once without touching a square that has already been touched. For those, like me, who are not chess players, the image below shows the knight’s moves.



The game has been released on Spelchan.com, with the source code being in the BlazingPorts repository. In this series of articles I am going to just be highlighting key parts of the game but if you want to look at the code in it’s entirety, it is available.

While it is possible to represent a board as a 2-dimensional array, it is also possible to represent it as a single dimensional array of 64 tiles. This makes tracking the order of the moves a bit easier and the moves can be represented as an offset that makes finding the tile indexes easier but does require a sanity check. The board is simply an array of Knights with the knight class holding the move number (or -1 if the tile has not yet been stepped on) and the tile index of the previous tile. While the previous tile reference is not necessary, it makes drawing the path much easier which is why it ended up being added.

The Knight class not only holds information for which order it is in but has methods for helping determine if it is a valid move. The checkIfAllowedMove function is used to verify that the move that the knight is making is in an L shape. This can be done easily by taking advantage of the fact that one of the distances traveled will be one square while the other distance will be 2 squares which means the absolute value of the two numbers will be equal to 3.

checkIfAllowedMove(knight1, knight2) {
   
let knightXAdjust = Math.abs( (knight1 % 8) - (knight2 % 8) );
    let
knightYAdjust = Math.abs( Math.floor(knight1 / 8) - Math.floor(knight2 / 8) );

    return
(knightXAdjust+knightYAdjust) === 3;
}

 

To check if a move is a potential move we simply need to make sure that the tile being moved to is empty, and that the target destination is an L's distance away from the last valid move.

isTileAPotentialMove() {
   
if (this.moveNumber >=0)
       
return false;
    let
knight = this.game.getLastKnightTile();
    for
(let cntr = 0; cntr < KT.knightTileOffsets.length; ++cntr) {
       
if ((knight + KT.knightTileOffsets[cntr]) === this.id) {
           
return this.checkIfAllowedMove(knight, this.id);
       
}
    }
   
return false;
}

 

Part of the reason I created this game was to play around with solving methods, but having the game playable by humans is an important aspect. One of the biggest issues with this game is that it is easy to get to a point where you can no longer win the game yet not notice until later in the game requiring multiple levels of undo. To make this easier on the player I wanted to have a warning message appear when the game is no longer in a winnable state. This obviously requires that the computer is able to detect when the game is not in a winnable state. My method of detecting if a game is solveable is to simply make sure that every tile on the board either already has a night on it or is an L shape away from an empty tile. As you can see in the code below, this is simply a loop over all the tiles on the board with the empty ones being checked to see if they are an L shape away from another empty tile or the last move. This is not the most efficient way of doing this has it be possible to track this information and reduce the amount of calculations that we have to do but I will discuss that later when I am covering forward checking. Another problem with this method is that there may be an isolated patch of tiles that can connect with each other but not the main board but is good enough for our needs.

isGameStillWinnable() {
   
if (this.knightCount > 62) return true;

    for
(let t = 0; t < 64; ++t) {
       
if (this.tiles[t].moveNumber === KT.NO_MOVE) {
           
let hasValidMove = false;
            for
(let k = 0; k < KT.knightTileOffsets.length; ++k) {
               
let target = t + KT.knightTileOffsets[k];
                if
((target >= 0) && (target < 64)) {
                   
if (this.tiles[target].isValidMove(t)) {
                        hasValidMove =
true;
                        break;
                   
}
                   
if (target === this.lastKnightTile) {
                        hasValidMove =
true;
                        break;
                   
}
                }
            }
           
if ( ! hasValidMove) {
               
//console.log(`tile ${t} not valid`)
               
return false;
           
}
        }
    }

   
return true;
}

 

When I started working on this project the previous move information was not stored in the knight so to undo a move, I had to resort to doing a back look up. This is done by simply looking at all the possible moves from the current night and seeing if any of them have the ID of the previous move. Another way that this could have been done is simply loop over all the tiles in the board, but just searching 8 tiles is much quicker.

undoMove() {
   
if (this.knightCount <= 0)
       
return;
    let
previousTile = -1;
    for
(let i = 0; i < KT.knightTileOffsets.length; ++i) {
       
let target = this.lastKnightTile + KT.knightTileOffsets[i];
        if
((target>=0) && (target<64)) {
           
if (this.tiles[target].moveNumber === (this.knightCount-1) )
                previousTile = target
;
       
}
    }
   
this.tiles[this.lastKnightTile].setMoveNumber(-1, -1);
   
--this.knightCount;
    this
.lastKnightTile = previousTile;
}

 

Now that we have a basic game, lets see how a computer would solve it. The obvious starting point is with the backtracking and forward checking algorithms that we used for solving Queen’s Challenge. Those  methods worked very well with Queen’s Challenge so our work should be over quickly. It’s strange that this series has four parts instead of just two.