The Knight’s tour problem | Backtracking | DFS | Love Babbar DSA sheet

[@yuvraj0047]

the way knight move was wrong but position is correct😅😂😂

[@iEntertainmentFunShorts]

Code is incorrect not printing the correct answer showing all 0's in matrix

[@hemant-0364]

Well done brother 👍

[@adityarajiv6346]

Thank you so much 😀

[@prajwalsable7586]

We can do it with 1 2d array also

[@yakshmahawer5434]

Bro I thought the whole logic without breaking any rule of the question and code was going quite well but at one point it had no option to go anywhere as it was at bottom right and on left and right side the boxes were visited so got MAXIMUM STACK error and it had no where to go

[@yakshmahawer5434]

Sorry left and up

[@sonuchaudhary5479]

thank you bro

[@adityarajiv6346]

Welcome 😀. Please share with friends 🙏.

[@pranjaygoyal6139]

bro i am not satisfied with your code

[@pranjaygoyal6139]

shreya what do u think?

[@shreyaagarwal5614]

bro i copied your code but its not showing the correct output

[@pranjaygoyal6139]

@@shreyaagarwal5614 yeh ladki sahi bol rhi hai sir ji

[@victorvondoom2350]

@@shreyaagarwal5614 // Javascript program for Knight Tour problem let N = 8; // A utility function to check if i,j are // valid indexes for N*N chessboard function isSafe(x, y, sol) { return(x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1); } // A utility function to print solution // matrix sol[N][N] function printSolution(sol) { for(let x = 0; x < N; x++) { for(let y = 0; y < N; y++) console.log(sol[x][y] + " "); console.log("\t"); } } // This function solves the Knight Tour problem // using Backtracking. This function mainly // uses solveKTUtil() to solve the problem. It // returns false if no complete tour is possible, // otherwise return true and prints the tour. // Please note that there may be more than one // solutions, this function prints one of the // feasible solutions. function solveKT() { let sol = new Array(8); for(var i = 0; i < sol.length; i++) { sol[i] = new Array(2); } // Initialization of solution matrix for(let x = 0; x < N; x++) for(let y = 0; y < N; y++) sol[x][y] = -1; // xMove[] and yMove[] define next move of Knight. // xMove[] is for next value of x coordinate // yMove[] is for next value of y coordinate let xMove = [ 2, 1, -1, -2, -2, -1, 1, 2 ]; let yMove = [ 1, 2, 2, 1, -1, -2, -2, -1 ]; // Since the Knight is initially at the first block sol[0][0] = 0; // Start from 0,0 and explore all tours using // solveKTUtil() if (!solveKTUtil(0, 0, 1, sol, xMove, yMove)) { console.log(" solution does not exist"); return false; } else printSolution(sol); return true; } // A recursive utility function to solve Knight // Tour problem function solveKTUtil(x, y, movei, sol, xMove, yMove) { let k, next_x, next_y; if (movei == N * N) return true; // Try all next moves from the // current coordinate x, y for(k = 0; k < 8; k++) { next_x = x + xMove[k]; next_y = y + yMove[k]; if (isSafe(next_x, next_y, sol)) { sol[next_x][next_y] = movei; if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove)) return true; else sol[next_x][next_y] = -1; // backtracking } } return false; } // Driver code // Function Call solveKT(); // This code is geeksForGeeks