let successCount = 0;
const boardSizeHoriz=8;
const boardSizeVert=8;
const maxAttempts = 5;
const attemptTheImpossible = true; // if true, attempt to complete tour starting from white square on 'odd' board (not possible to complete)
for (let i=0; i<boardSizeHoriz; i++){
for (let j=0; j<boardSizeVert; j++) {
if (attemptTheImpossible || (boardSizeHoriz & 1) === 0 || ((i ^ j) & 1) === 0 ) {
for (let attempt = 1; attempt <= maxAttempts; attempt++){
let res=knightsTour(boardSizeHoriz, boardSizeVert, i, j, attempt === 1);
console.log('attempt: ', attempt, 'result: ', res);
if(res.success) {
successCount++;
break;
}
}
}
}
}
console.log('success count ',successCount);
////
// knightsTour(): attempt a single Knight's tour, using Warnsdorff's rule
// M = width of board, N = height of board in squares
// startFile and StartRank represent starting square, (0 to M-1, 0 to N-1 respectively)
// shuffleMoveOrder: if true, randomize the order of Knight's moves searched
function knightsTour(M, N, startFile, startRank, shuffleMoveOrder = false) {
let [centerHoriz, centerVert] = [M / 2, N / 2]; // geometric center of board
// create a collection of unvisited squares:
let unvisitedSquares=[];
for(let m=0; m < M; m++) {
for(let n=0; n < N; n++) {
unvisitedSquares.push({file: m, rank: n});
}
}
let knightsPath = '';
let [currentFile, currentRank] = [startFile, startRank];
do {
/* jshint loopfunc: true */ // stfu, linter !!
knightsPath += fileRankToSquare(currentFile,currentRank) + ' ';
unvisitedSquares = unvisitedSquares.filter(sq => currentFile !== sq.file || currentRank !== sq.rank); // visit (remove current square from unvistedSquares)
let neighbors=getNeighbors(currentFile, currentRank, unvisitedSquares, shuffleMoveOrder);
if(neighbors.length === 0) {
break;
}
// select neighbors who themselves have the smallest number of neighbors:
let neighborsOfNeighbors = neighbors.map((n) => getNeighbors(n.file, n.rank, unvisitedSquares.filter(unv => unv.file !== n.file || unv.rank !== n.rank)));
let minDegree = neighborsOfNeighbors.reduce((a, n) => Math.min(a, n.length),8);
let bestNeighbors = neighbors.filter((n, i) => neighborsOfNeighbors[i].length === minDegree);
if(bestNeighbors.length > 1) { // tie-breaker
bestNeighbors = bestNeighbors.sort((a,b)=>
distanceTocenterSquared(b.file, b.rank, centerHoriz, centerVert) -
distanceTocenterSquared(a.file, a.rank, centerHoriz, centerVert)
); // sort by distance to center
}
currentFile=bestNeighbors[0].file;
currentRank=bestNeighbors[0].rank;
} while(unvisitedSquares.length);
return {
knightsPath: knightsPath,
unvisitedSquareCount: unvisitedSquares.length,
success: !unvisitedSquares.length
};
}
function getNeighbors(file, rank, unvisitedSquares, shuffleMoveOrder = false) {
const knightMoves = [
[1,2],
[2,1],
[2,-1],
[1,-2],
[-1,-2],
[-2,-1],
[-2,1],
[-1,2]
];
if (shuffleMoveOrder) { // randomly shuffle move-order
let i = knightMoves.length, r;
while (i > 1) {
i -= 1;
r = Math.floor(Math.random() * i);
[knightMoves[i], knightMoves[r]] = [knightMoves[r], knightMoves[i]]; // exchange
}
}
let neighbors = [];
knightMoves.forEach((move)=> {
let newSquare = {file: file + move[0], rank: rank + move[1]};
if(unvisitedSquares.filter(unvisited => newSquare.file === unvisited.file && newSquare.rank === unvisited.rank).length) {
neighbors.push(newSquare);
}
});
return neighbors;
}
function distanceTocenterSquared(file, rank, centerHoriz, centerVert) {
return Math.pow(0.5 + file - centerHoriz, 2) + Math.pow(0.5 + rank - centerVert, 2); // note: add 0.5 to get geometric center of each square
}
// utility functions:
// squareToFileRank() : convert a square name (eg 'c4') to [file, rank]
// note: beyond 26 columns, we run out of alpha characters, which are followed by '{', '|', '}', '~', DEL , and then we need to use weird utf-16 characters ...
// (I suppose we could implement a system like Excel's column numbering, going to 'aa' after 'z' ...)
function squareToFileRank (square) {
let alphaNumSplit = square.match(/(\d+|[^\d]+)/g);
let file = alphaNumSplit[0].toLowerCase().charCodeAt(0)-97;
let rank = Number(alphaNumSplit[1])-1;
return([file, rank]);
}
// fileRankToSquare() : convert file, rank to a square name
function fileRankToSquare (file, rank) {
return String.fromCharCode(97 + file) + (1+rank);
}
export default knightsTour;
Playing around with knight's tours using Warnsdorff's rule with the added heuristic of choosing the square most distant from the center as a tie-break.
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.