Solved

4x4 Knight's tour C program

Posted on 2004-03-25
2,324 Views
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]).
0
Question by:bashaer
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 17
• 14
• 3
• +1

LVL 45

Expert Comment

ID: 10677911
homework ?
0

Author Comment

ID: 10678486
yes
0

Author Comment

ID: 10680015
I've written the following code. But it only does one step. What's wrong??

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))&&((j=n+2)||(j=n-2)))||(((i=m+2)||(i=m-2))&&((j=n+1)||(j=n-1)))){
if(x[i][j] ==0){
x[i][j] =1;
y[i][j] =++k;
m =i;
n =j;
}}}}}

0

Author Comment

ID: 10680031
i forgot there is a
d++;
before exiting the while loop
0

LVL 11

Expert Comment

ID: 10680537
"It only does one step"? What does this mean? It only finds one solution or it finds no solutions? What do you end up with in x?

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.

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
0

LVL 45

Expert Comment

ID: 10684597
1.
>if((((i=m+1)||(i=m-1))&&((j=n+2)||(j=n-2)))

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 ?
0

Author Comment

ID: 10687357
#include<stdio.h>

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))&&((j=n+2)||(j=n-2)))||(((i=m+2)||(i=m-2))&&((j=n+1)||(j=n-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.
0

LVL 45

Expert Comment

ID: 10687417
Actually I too came across this algorithm a couple of months ago while solving another asker's problem which began with A* ;o)

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
0

Author Comment

ID: 10688091
Ignoring the iterative deepening DFS part..
What's wrong with my code?? why does it stop at the second move??
0

Author Comment

ID: 10688093
Ignoring the iterative deepening DFS part..
What's wrong with my code?? why does it stop at the second move??
0

LVL 11

Expert Comment

ID: 10688491
The if statemet (about line 42) uses = when you want ==.

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
0

Author Comment

ID: 10688624
but if i start the loops with 0's then it will only do one step as well.. ???
0

LVL 11

Expert Comment

ID: 10688687
I fixed the if statement (==) and the initialization and reset them to 0. It stil fails to solve the problem but it does run past the first iteration.

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
0

Author Comment

ID: 10688725
How do i implement back-tracking??
0

LVL 11

Expert Comment

ID: 10688794
sunnycoder's simple example suggests using recursion rather than iteration.

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
0

Author Comment

ID: 10688869
how do i determine the total depth??
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??
0

LVL 11

Expert Comment

ID: 10688946
You are searching a "state space". So the root is the initial state. Each node contains a state (meaning a setting of x (and y though that is just bookkeeping)).  So, (x, m, n) (the board with visted spots marked and the position of the last placed knight) makes up a state/node. A child is a state that can be reached from the current state. That is, a state with one more 1 in x and that 1 being a knights move from m, n.

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
0

Author Comment

ID: 10689045
ok, i understand what you're saying but how do i implement this in my code??
0

LVL 11

Expert Comment

ID: 10689159
No code from me since this is homework. Pseudocode follows. Note that I am writing C++ (I want references to boards); you can make it C by passing and dereferencing pointers

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, nextKnightRow, nextKnightCol)) // <-- this is the recursion; need to place remaining knights moves
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
0

Author Comment

ID: 10689435
how do i loop through the 8 possible knight moves??
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][nextknightcol] == 1 ??
and remove by x[nextknightrow][nextknightcol] == 0 ??

0

LVL 11

Expert Comment

ID: 10689520
(1) What ARE the eight possible knights moves? If we express them in relative terms, they are ((-2, -1), (-2, 1), (-1, -2), (-1, 2), ...) so if you had an aray with these eight values in it you can use them to calculate nextKnightRow and nextKnightColumn (from lastKnightRow and lastKnightColumn).

(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
0

Author Comment

ID: 10689649
i don't understand the first point!!!
let's say i have an array
legalmoves[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
how do i calculate the next row and col from this array??
0

LVL 11

Expert Comment

ID: 10689738
Assume the array elements are change in row and change in column. Then, given the last knight's move was to position 0,2, where could the knight move next?:

-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
0

Author Comment

ID: 10690050
i wrote a function.. but i don't know where to use it in the main program..

#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},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{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], newrow, newcol))
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))&&((j==n+2)||(j==n-2)))||(((i==m+2)||(i==m-2))&&((j==n+1)||(j==n-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;
}
0

LVL 11

Expert Comment

ID: 10690146
(1) The solving takes place at the same spot in main: Where you now have your while d <= 16 you will replace that with a call to your function indicating that the last move is at 0, 1.

(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},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{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], newrow, newcol))
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;
}
0

LVL 11

Expert Comment

ID: 10690194
Sorry about putting my signature in the middle of the function. Hope the intent was still clear.
-bcl
0

Author Comment

ID: 10690260

#include<stdio.h>

int visit[4][4], rout[4][4];
int step=1;
int legalmoves[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{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;
}
0

LVL 11

Expert Comment

ID: 10690363
(1) Check your = and your ==; one means compare, the other means assign. You seem to be misusing them.

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

-bcl
0

Author Comment

ID: 10690637
the board doesn't change what's wrong???
it's all 0's????

#include<stdio.h>

int visit[4][4], rout[4][4];
int legalmoves[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{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;
}

0

LVL 11

Expert Comment

ID: 10690803
Suggestion: Inside of the recursive function, just after you change visit, print out newrow, newcol, d, and visit (the whole array). Make sure you have a blank line after the array to make the output easier to follow.

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

-bcl
0

Author Comment

ID: 10690967
you know what?
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..
0

LVL 11

Accepted Solution

ID: 10691087
Well, you're almost there (I found the remaining bug, I think). But I understand about needing to punt at some point.

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

-bcl
0

Author Comment

ID: 10691092
ok
Thank You.
0

Expert Comment

ID: 10794341

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

0

LVL 11

Expert Comment

ID: 10794408
BlaqDeth--

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
0

Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Artificial Intelligence comes in many forms, and for game developers, Path-Finding is an important ability for making an NPC (Non-Playable Character) maneuver through terrain.  A* is a particularly easy way to approach it.  Iâ€™ll start with the algorâ€¦
Recently, in one of the tech-blogs I usually read, I saw a post about the best-selling video games through history. The first place in the list is for the classic, extremely addictive Tetris. Well, a long time ago, in a galaxy far far away, I wasâ€¦
In a recent question (https://www.experts-exchange.com/questions/29004105/Run-AutoHotkey-script-directly-from-Notepad.html) here at Experts Exchange, a member asked how to run an AutoHotkey script (.AHK) directly from Notepad++ (aka NPP). This videoâ€¦
How to Install VMware Tools in Red Hat Enterprise Linux 6.4 (RHEL 6.4) Step-by-Step Tutorial
Suggested Courses
Course of the Month4 days, 5 hours left to enroll