## Adobe Interview Question for MTSs

• -2
of 2 votes

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

Backtracking Algorithm for Knight’s tour
Following 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

Comment hidden because of low score. Click to expand.
0
of 0 vote

use depth first search with previously visited spots marked.

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can use BackTracking to solve this problem.

Comment hidden because of low score. Click to expand.
0
of 0 vote

based on the step that knight takes, it can get cornered... what is the expectation in that scenario? track back (and erase the steps while tracking back) and continue ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure I have interpreted the question correctly, by filling up the board you mean all 64 cells are visited by the knight?
Do we have start position?

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Explain a bit more

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More