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