Knights Tours on an arbitrary chess board size

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.