Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

given a 4x4 chess board with the knight initially on row 0, column 1 (i.e. second block from left), construct a depth-first iterative deepining algorithm (C language) to solve the following: The Knight has to visit all the blocks except the top left corner (i.e. [0][0]).

int x[4][4], y[4][4];

int i, j, k=1, d=1, m=0, n=1;

for(i=0; i<4; i++){

for(j=0; j<4; j++)

x[i][j] =0;

y[i][j] =0;

}

x[0][1] =1;

y[0][1] =1;

while(d<16){

for(i=m; i<4; i++){

for(j=n; j<4; j++){

if(i==0 && j==0)

continue;

if((((i=m+1)||(i=m-1))&&((

if(x[i][j] ==0){

x[i][j] =1;

y[i][j] =++k;

m =i;

n =j;

}}}}}

please answer asap.. Thank You :)

What happens when you choose poorly? This needs to include backtracking: Any given move will need to be "undoable" if it leads to a dead end.

I will make two comments, one about your design and one about your code. They are not intended to be insulting.

What is your code supposed to be doing? A few comments illustrating your design (what are x and y? What about m and n?) and how your nested loops should solve the problem would make your code easier for you and others to evaluate. I think your design is flawed in that for any given knight's position there are at most 8 possible follow-on moves; why check the entire board? Why not just look at the eight moves (and see if any is a backward move (check for a 1 in the board x) rather than have a big check whether a given board position is a knights move away from m, n.

About the code: Use more descriptive variable names. single character variable names make it easy to make typos and make it difficult to tell what a variable is for (what is k used for? How about d? Names like currentMove and ... how exactly do k and d differ? With more descriptive names I would know and so would you and your grader). I know, you JUST have to get it to work and all that typing will slow you down. Don't belive that for a minute. Some good variable name choices will speed your coding because it makes it easier to reason about the code. Okay, no more soapboxing.

-bcl

>if((((i=m+1)||(i=m-1))&&(

You just set i = m in a count UP loop .... how can i be ever equal to m-1

ditto for j = n -2

2.

>while(d<16){

d is not changed in this loop and since d is initialized to 1, it is an infinite loop

3. your assignment requires you to use depth first iterative deepening .... I cant see depth first approach nor do I find iterative deepening !!! Are you familiar with the algorithm that you are supposed to program here ?

int main()

{

int x[4][4], y[4][4];

int i, j, k=1;

int d=1, m=0, n=1;

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

x[i][j]=0;

y[i][j]=0;

}

x[0][1]=1;

y[0][1]=1;

printf("Initially the visitation matrix will look like this:\n0 is for not yet visited\n1 is for visited\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", x[i][j]);

printf("\n");

}

printf("\n");

printf("Initially the time matrix will look like this:\n1 is for first block visited\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", y[i][j]);

printf("\n");

}

while(d<=16)

{

for(i=m; i<4 ; i++)

{

for(j=n; j<4 ; j++)

{

if(i==0 && j==0)

continue;

if((((i=m+1)||(i=m-1))&&((

{

if(x[i][j] ==0)

{

x[i][j] = 1;

y[i][j] = ++k;

m=i;

n=j;

}

}

}

}

d++;

}

printf("\nThe Knight has completed its tour, and these are the results:\n");

printf("This matrix shows that it visited all blocks\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", x[i][j]);

printf("\n");

}

printf("\nThis matrix shows the rout it took\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", y[i][j]);

printf("\n");

}

return 0;

}

This is the whole code.

x has 0's and 1's for not-visited and visited.

y has numbers from 0 to 15 for the steps.

k is the step variable

d is for the iterations from 1 to 16

The code only does one move. It just goes from the initial block (0,1) to another block.

The proffesor didn't explain depth-first iterative deepining, so i have no idea on how to implement it.

Iterative deepening is a graph search algorithm. It combines properties of depth first searching and breadth first searching. The basic idea is to implement a depth first search up to the Nth level. N should start at either 0 or 1 and be incremented after each search up to N is complete. This searching technique is complete and is guaranteed to return the desired node.

Starting with N=1 the nodes in a tree are searched as far as level N, N is then incremented (unless the desired node has been found) and the next level is searched. So with N=1 only three (if a binary tree is used) nodes will be searched. Assuming a balanced tree and more than 5 nodes, if N=2 the first three will be searched and then the immediate children of those (to a maximum depth of 2) this continues until the whole tree has been searched or time runs out.

also see http://ai.squeakydolphin.com/wiki.php?pagename=AIAWiki.IterativeDeepeningSearch

A good graphical explanation can be found at

http://www.stanford.edu/~msirota/soco/inter.html

In the most basic implementation, you can make it like this

i=1

while ( i <= total depth )

{

iterative deeping (i,root)

i++

}

iterative deepening ( int i, root )

{

if ( found at root )

return success

if ( i == 0 )

return failure

for each child

iterative deepening ( i-1, child )

}

ofcourse you need to add in appropriate response to success or failures .... here we decrement i for each level of search/recursive call ... this keeps track of how many levels we are going to search

If you need ay futher clarifications, post back

What's wrong with my code?? why does it stop at the second move??

What's wrong with my code?? why does it stop at the second move??

When initializing x and y you fail to use {} in the inner loop (so only x is actually initialized)

Those are not the cause of your problem; they are just additional problems.

Your if statement (inside the two if statements) is never true after the first time through. Consider that you start j at n and the first time you set n it is set to 3. That means you only check the last column for a knights move from a position in the last column. No such move exists so you keep looping.

Hope this helps, -bcl

It only finds 13 steps because one of the chosen steps leads to a dead end. Your code doesn't handle that (no way to back up) and you increment d regardless of whether or not a new position is found so the loop always ends after 16 tries, not 16 moves.

-bcl

Recursion privides you with an execution stack, a snap-shot of the algorithm at any given moment and if you recur after placing each knight you will have a record (in the local variables of each function call) of all of the decisions you have made. When it is impossible to place a new knight from a given board position, you can return (with a failure code) from the function. The calling instance of the function can then see if IT can place the knight it placed in a different spot. If not, it, too, fails. If so, it changes where it placed the knight and recurs. If that choice leads to a tour, the lowest level call can return a success code that is passed back up eventually to the original caller of the solver.

If you don't use recursion, you need some manner of keeping track of what choices were made in placing each knight currently on the board. You need your own stack. Recursion is much easier to use.

Look at sunnycoder's suggested site. Ask more questions.

Hope this helps, -bcl

what's the root?? is it the initial location (i.e x[0][1])??

"found at root" what does it mean?? the solution?? or a neighbor??

and what's the child??

Since we know the knight's tour will be 15 (when it is complete), it strikes me that searching to a given depth less than 15 is pointless. So we will probably use a DFS rather than repeated application of the DFS.

Does this begin to make sense?

-bcl

bool placeAKnight(Board & currentBoard, int lastKnightRow, int lastKnightCol)

{

if (number of knights is 15)

return true (for success)

for each of the 8 possible knights moves

nextKnightRow is set

nextKnightCol is set

if move is not valid // could be already visited, could be off of the board, could be 0,0, the forbidden square

continue;

put a knight on the board

if (placeAKnight(currentBoard

return true

remove knight from board // got here if somewhere down the line it failed; we'll see if there is another position available in the for loop

}

Now I didn't do anything with y; you might want to pass in the depth as a 4th parameter and pass depth+1 to the recursive call and fill in y as part of the placing the knight (oops, need to pass in a reference to y, too).

Does the design make sense? You will want a function outside of main that takes a board and a knight position (and y and depth, perhaps), and returns true if it can find a knights tour that meets your specifications.

-bcl

Note that f

and why do we set the next row and column??

one more thing, what do u mean put and remove knight from board??

can i put by : x[nextknightrow][nextknigh

and remove by x[nextknightrow][nextknigh

(2) Why do we keep local variables with where we moved? Because if the knight's tour below us fails we must be able to UNDO our move. I found it easier to calculate the board position rather than keep resuing the previous position and current move to recalculate them.

(3) Yes, to move is to put a mark on the board, to unmove is to remove that mark. Note that you will want to update y as well.

-bcl

let's say i have an array

legalmoves[8][2]={{-2,-1},

how do i calculate the next row and col from this array??

-2, 1

-2, 2

-1, 0

-1, 4

1, 0

1, 4

2, 1

2, 2

(I just added each of the element in your array to the previous move position).

Note that (a) One of those moves is where the knight moved FROM so it already has a 1 in x (not a valid move) and (b) Five out of the eigth possible moves are off of the board (not valid moves). So, this state actually only has two children (assuming both of the movable squares have not been visited previously).

So you can loop through the little array you have and check whether a move is vaild, recurring only if it is.

-bcl

#include<stdio.h>

int visit[4][4], rout[4][4];

int step=1;

int placeKnight(int lastRow, int lastCol, int d)

{

int legalmoves[8][2]={{-2,-1},

int i, j;

int newrow, newcol;

if (d == 15)

return 1;

for(i=0; i<8; i++){

for(j=0; j<2; j++){

newrow= lastrow + legalmoves[i];

newcol= lastcol + legalmoves[j];

if(visit[newrow][newcol] == 1)

continue;

visit[newrow][newcol] == 1;

rout[newrow][newcol] = ++step;

if(placeKnight(visit[4][4]

return 1;

}

}

visit[newrow][newcol]==0;

rout[newrow][newcol] = ++step;

}

int main()

{

int i, j;

int depth=1, m=0, n=1;

for(i=0; i<4; i++)

{

for(j=0; j<4; j++){

visit[i][j]=0;

rout[i][j]=0;

}

}

visit[0][1]=1;

rout[0][1]=1;

printf("Initially the visit matrix will look like this:\n0 is for not yet visited\n1 is for visited\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", visit[i][j]);

printf("\n");

}

printf("\n");

printf("Initially the time matrix will look like this:\n1 is for first block visited\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", rout[i][j]);

printf("\n");

}

while(depth <=16)

{

for(i=0; i<4 ; i++)

{

for(j=0; j<4 ; j++)

{

if(i==0 && j==0)

continue;

if((((i==m+1)||(i==m-1))&&

{

if(visit[i][j] ==0)

{

visit[i][j] = 1;

rout[i][j] = ++step;

m=i;

n=j;

}

}

}

}

depth++;

}

printf("\nThe Knight has completed its tour, and these are the results:\n");

printf("This matrix shows that it visited all blocks\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", visit[i][j]);

printf("\n");

}

printf("\nThis matrix shows the rout it took\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", rout[i][j]);

printf("\n");

}

return 0;

}

(2) I am going to comment on your code (since I am betting it doesn't compile for you):

int placeKnight(int lastRow, int lastCol, int d)

{

// legalmoves is a good candidate for a global constant value since it doesn't change

int legalmoves[8][2]={{-2,-1},

int i, j;

int newrow, newcol;

if (d == 15)

return 1;

for(i=0; i<8; i++){

/* Okay, why do we want to cycle across the element INSIDE each move? Just set newrow to lastrow + legalmoves[i][0] and

nextcol to lastcol + legalmoves[i][1]

*/

for(j=0; j<2; j++){

newrow= lastrow + legalmoves[i];

newcol= lastcol + legalmoves[j];

if(visit[newrow][newcol] == 1)

continue;

visit[newrow][newcol] == 1;

// Don't use step, use d (the reason to pass it as a parameter is that you can make the "same" move

// more than once (by unmaking it and then making a different move at the same point in the route)

rout[newrow][newcol] = ++step;

// Need to work on YOUR parameters, not the parameters I used in the pseudocode.

// If visit is global, don't pass it as a parameter. You need to pass newrow, newcol and the new depth...what is the new depth?

if(placeKnight(visit[4][4]

return 1;

}

}

Hope this helps,

-bcl

visit[newrow][newcol]==0;

// I would guess that rout should be set to 0 here

rout[newrow][newcol] = ++step;

}

-bcl

#include<stdio.h>

int visit[4][4], rout[4][4];

int step=1;

int legalmoves[8][2]={{-2,-1},

int placeKnight(int lastRow, int lastCol, int d)

{

int i, j, newrow, newcol;

if (d == 15)

return 1;

for(i=0; i<8; i++){

newrow= lastrow + legalmoves[i][0];

newcol= lastcol + legalmoves[i][1];

if(visit[newrow][newcol] == 1)

continue;

visit[newrow][newcol] == 1;

rout[newrow][newcol] = ++step;

d++;

if(placeKnight(newrow, newcol, d))

return 1;

}

visit[newrow][newcol]==0;

rout[newrow][newcol] == 0;

}

int main()

{

int i, j, eval;

int depth=1, m=0, n=1;

for(i=0; i<4; i++)

{

for(j=0; j<4; j++){

visit[i][j]=0;

rout[i][j]=0;

}

}

visit[0][1]=1;

rout[0][1]=1;

printf("Initially the visit matrix will look like this:\n0 is for not yet visited\n1 is for visited\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", visit[i][j]);

printf("\n");

}

printf("\n");

printf("Initially the time matrix will look like this:\n1 is for first block visited\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", rout[i][j]);

printf("\n");

}

eval= placeknight(m, n, depth);

printf("\nThe Knight has completed its tour, and these are the results:\n");

printf("This matrix shows that it visited all blocks\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", visit[i][j]);

printf("\n");

}

printf("\nThis matrix shows the rout it took\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", rout[i][j]);

printf("\n");

}

return 0;

}

(2) Still don't like step as the assignment into rout...you have to reduce it by 1 when ever you fail.

-bcl

it's all 0's????

#include<stdio.h>

int visit[4][4], rout[4][4];

int legalmoves[8][2]={{-2,-1},

int placeKnight(int lastRow, int lastCol, int d)

{

int i, newrow, newcol;

if (d == 15)

return 1;

for(i=0; i<8; i++){

newrow= lastRow + legalmoves[i][0];

newcol= lastCol + legalmoves[i][1];

if(visit[newrow][newcol] == 1)

continue;

visit[newrow][newcol] = 1;

rout[newrow][newcol] = d;

d++;

if(placeKnight(newrow, newcol, d)==1)

return 1;

}

visit[newrow][newcol]= 0;

rout[newrow][newcol] = 0;

return 0;

}

int main()

{

int i, j, eval;

int depth=1, m=0, n=1;

for(i=0; i<4; i++)

{

for(j=0; j<4; j++){

visit[i][j]=0;

rout[i][j]=0;

}

}

visit[0][1]=1;

rout[0][1]=1;

printf("Initially the visit matrix will look like this:\n0 is for not yet visited\n1 is for visited\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", visit[i][j]);

printf("\n");

}

printf("\n");

printf("Initially the time matrix will look like this:\n1 is for first block visited\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", rout[i][j]);

printf("\n");

}

eval= placeKnight(m, n, depth);

if(eval ==1){

printf("\nThe Knight has completed its tour, and these are the results:\n");

printf("This matrix shows that it visited all blocks\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", visit[i][j]);

printf("\n");

}

printf("\nThis matrix shows the rout it took\n\n");

for(i=0; i<4; i++)

{

for(j=0; j<4; j++)

printf("%d ", rout[i][j]);

printf("\n");

}

}

return 0;

}

I think you will find something interesting with the values of newrow and newcol, in particular.

-bcl

Thank you for everything you did.. but i will stick with the first code where i had 13steps..

i can't seem to make this one work.. it's midnight and i have to submit this tomorrow.. so i'll just stick with the first code..

thank you very much..

First, the Knight has to visit all of the blocks except 0,0 - but can the Knight still move there anyway?

Secondly, the Knight has to move to all places on the board at least once, but can he hit the same posistion more than once?

I could never refuse a challenge..

The knights tour usually requires the knight to visit each square exactly once. The reason the upper corner is excluded in this example is there is no 4x4 solution without repeats . If you permit repeats then there is a problem: When do you know that you are done? The tour in the no-repeat case has a fixed length and if you cannot complete the tour in that amount of time you know it will not come later. Harder to tell if cycles are permitted.

Good luck, -bcl

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.

Next week if you want to see the fixed up code just drop a note here.

-bcl