## Adobe Interview Question

MTSs**Country:**India

**Interview Type:**In-Person

pseudo code:

board is 8x8 bitmap

moves is dlink list of moves so far

pos is current position

```
bool find (board, pos, moves) {
if (check_finish(board)) { // checks if board bit map is filled
return true;
}
possible_moves = get_possible_moves(pos); // get possible moves from current pos
if ( not_empty (possible_moves) ) {
for_each (possible_moves) {
new_pos = get_new_pos(pos, move); // get new position after move;
mark_board(board, new_pos); // mark board bitmap;
add_move(move); // add current move to moves;
if ( find (board, new_pos, moves)) {
break; // found optimal path so stop searching rest of the possible moves.
}
else {
unmark_board(board, new_pos);
del_move(); // remove the last added move.
}
}
}
else {
return false;
}
}
```

Backtracking Algorithm for Knight’s tour

- cmos October 22, 2012Following is the Backtracking algorithm for Knight’s tour problem.

If all squares are visited

print the solution

Else

a) Add one of the next moves to solution vector and recursively

check if this move leads to a solution. (A Knight can make maximum

eight moves. We choose one of the 8 moves in this step).

b) If the move chosen in the above step doesn't lead to a solution

then remove this move from the solution vector and try other

alternative moves.

c) If none of the alternatives work then return false (Returning false

will remove the previously added item in recursion and if false is

returned by the initial call of recursion then "no solution exists" )

Following is C implementation for Knight’s tour problem. It prints one of the possible solutions in 2D matrix form. Basically, the output is a 2D 8*8 matrix with numbers from 0 to 63 and these numbers show steps made by Knight.

#include<stdio.h>

#define N 8

int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[],

int yMove[]);

/* A utility function to check if i,j are valid indexes for N*N chessboard */

int isSafe(int x, int y, int sol[N][N])

{

if ( x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1)

return 1;

return 0;

}

/* A utility function to print solution matrix sol[N][N] */

void printSolution(int sol[N][N])

{

for (int x = 0; x < N; x++)

{

for (int y = 0; y < N; y++)

printf(" %2d ", sol[x][y]);

printf("\n");

}

}

/* 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. */

bool solveKT()

{

int sol[N][N];

/* Initialization of solution matrix */

for (int x = 0; x < N; x++)

for (int 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 */

int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };

int yMove[8] = { 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) == false)

{

printf("Solution does not exist");

return false;

}

else

printSolution(sol);

return true;

}

/* A recursive utility function to solve Knight Tour problem */

int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[N],

int yMove[N])

{

int 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) == true)

return true;

else

sol[next_x][next_y] = -1;// backtracking

}

}

return false;

}

/* Driver program to test above functions */

int main()

{

solveKT();

getchar();

return 0;

}

Output:

0 59 38 33 30 17 8 63

37 34 31 60 9 62 29 16

58 1 36 39 32 27 18 7

35 48 41 26 61 10 15 28

42 57 2 49 40 23 6 19

47 50 45 54 25 20 11 14

56 43 52 3 22 13 24 5

51 46 55 44 53 4 21 12