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]).
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
"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.
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.
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 ?
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.
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.
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
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.
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.
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.
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??
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
Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline
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.
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 ??
(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.
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??
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.
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;
(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;
}
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;
}
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;
}
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.
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..
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
Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline
As game developers, we quickly learn that Artificial Intelligence (AI) doesn’t need to be so tough. To reference Space Ghost: “Moltar, I have a giant brain that is able to reduce any complex machine into a simple yes or no answer. (http://www.youtu…
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…
This demo shows you how to set up the containerized NetScaler CPX with NetScaler Management and Analytics System in a non-routable Mesos/Marathon environment for use with Micro-Services applications.