|
| 1 | +// C++ program for Knight Tour problem |
| 2 | +#include <bits/stdc++.h> |
| 3 | +using namespace std; |
| 4 | + |
| 5 | +#define N 8 |
| 6 | + |
| 7 | +int solveKTUtil(int x, int y, int movei, int sol[N][N], |
| 8 | + int xMove[], int yMove[]); |
| 9 | + |
| 10 | +/* A utility function to check if i,j are |
| 11 | +valid indexes for N*N chessboard */ |
| 12 | +int isSafe(int x, int y, int sol[N][N]) |
| 13 | +{ |
| 14 | + return (x >= 0 && x < N && y >= 0 && y < N |
| 15 | + && sol[x][y] == -1); |
| 16 | +} |
| 17 | + |
| 18 | +/* A utility function to print |
| 19 | +solution matrix sol[N][N] */ |
| 20 | +void printSolution(int sol[N][N]) |
| 21 | +{ |
| 22 | + for (int x = 0; x < N; x++) { |
| 23 | + for (int y = 0; y < N; y++) |
| 24 | + cout << " " << setw(2) << sol[x][y] << " "; |
| 25 | + cout << endl; |
| 26 | + } |
| 27 | +} |
| 28 | + |
| 29 | +/* This function solves the Knight Tour problem using |
| 30 | +Backtracking. This function mainly uses solveKTUtil() |
| 31 | +to solve the problem. It returns false if no complete |
| 32 | +tour is possible, otherwise return true and prints the |
| 33 | +tour. |
| 34 | +Please note that there may be more than one solutions, |
| 35 | +this function prints one of the feasible solutions. */ |
| 36 | +int solveKT() |
| 37 | +{ |
| 38 | + int sol[N][N]; |
| 39 | + |
| 40 | + /* Initialization of solution matrix */ |
| 41 | + for (int x = 0; x < N; x++) |
| 42 | + for (int y = 0; y < N; y++) |
| 43 | + sol[x][y] = -1; |
| 44 | + |
| 45 | + /* xMove[] and yMove[] define next move of Knight. |
| 46 | + xMove[] is for next value of x coordinate |
| 47 | + yMove[] is for next value of y coordinate */ |
| 48 | + int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }; |
| 49 | + int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }; |
| 50 | + |
| 51 | + // Since the Knight is initially at the first block |
| 52 | + sol[0][0] = 0; |
| 53 | + |
| 54 | + /* Start from 0,0 and explore all tours using |
| 55 | + solveKTUtil() */ |
| 56 | + if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == 0) { |
| 57 | + cout << "Solution does not exist"; |
| 58 | + return 0; |
| 59 | + } |
| 60 | + else |
| 61 | + printSolution(sol); |
| 62 | + |
| 63 | + return 1; |
| 64 | +} |
| 65 | + |
| 66 | +/* A recursive utility function to solve Knight Tour |
| 67 | +problem */ |
| 68 | +int solveKTUtil(int x, int y, int movei, int sol[N][N], |
| 69 | + int xMove[8], int yMove[8]) |
| 70 | +{ |
| 71 | + int k, next_x, next_y; |
| 72 | + if (movei == N * N) |
| 73 | + return 1; |
| 74 | + |
| 75 | + /* Try all next moves from |
| 76 | + the current coordinate x, y */ |
| 77 | + for (k = 0; k < 8; k++) { |
| 78 | + next_x = x + xMove[k]; |
| 79 | + next_y = y + yMove[k]; |
| 80 | + if (isSafe(next_x, next_y, sol)) { |
| 81 | + sol[next_x][next_y] = movei; |
| 82 | + if (solveKTUtil(next_x, next_y, movei + 1, sol, |
| 83 | + xMove, yMove) |
| 84 | + == 1) |
| 85 | + return 1; |
| 86 | + else |
| 87 | + |
| 88 | + // backtracking |
| 89 | + sol[next_x][next_y] = -1; |
| 90 | + } |
| 91 | + } |
| 92 | + return 0; |
| 93 | +} |
| 94 | + |
| 95 | +// Driver Code |
| 96 | +int main() |
| 97 | +{ |
| 98 | + // Function Call |
| 99 | + solveKT(); |
| 100 | + return 0; |
| 101 | +} |
| 102 | + |
0 commit comments