GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — JavaScript/Backtracking/KnightTour.js at master · Randomlyclueless/JavaScript Expand file tree/ Copy pathKnightTour.jsMore file actions 72 lines (63 loc) · 1.88 KB / Copy pathKnightTour.jsFile metadata and controls72 lines (63 loc) · 1.88 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 // Wikipedia: https://en.wikipedia.org/wiki/Knight%27s_tour class OpenKnightTour { constructor(size) { // Constructor to initialize the chessboard and size this.board = new Array(size).fill(0).map(() => new Array(size).fill(0)) this.size = size } getMoves([i, j]) { // Helper function to get the valid moves of the knight from the current position const moves = [ [i + 2, j - 1], [i + 2, j + 1], [i - 2, j - 1], [i - 2, j + 1], [i + 1, j - 2], [i + 1, j + 2], [i - 1, j - 2], [i - 1, j + 2] ] // Filter out moves that are within the board boundaries return moves.filter( ([y, x]) => y >= 0 && y < this.size && x >= 0 && x < this.size ) } isComplete() { // Helper function to check if the board is complete return !this.board.map((row) => row.includes(0)).includes(true) } solve() { // Function to find the solution for the given board for (let i = 0; i < this.size; i++) { for (let j = 0; j < this.size; j++) { if (this.solveHelper([i, j], 0)) return true } } return false } solveHelper([i, j], curr) { // Helper function for the main computation if (this.isComplete()) return true // Iterate through possible moves and attempt to fill the board for (const [y, x] of this.getMoves([i, j])) { if (this.board[y][x] === 0) { this.board[y][x] = curr + 1 if (this.solveHelper([y, x], curr + 1)) return true // Backtracking: If the solution is not found, reset the cell to 0 this.board[y][x] = 0 } } return false } printBoard(output = (value) => console.log(value)) { // Utility function to display the board for (const row of this.board) { let string = '' for (const elem of row) { string += elem + '\t' } output(string) } } } export { OpenKnightTour } |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |