In 3 moves, where can the knight go?

[Bert]

This is a past question from a programming competition.

On a chess board (8 squares by 8 squares), there's is a knight sitting
on b1 (2 from the left of the bottom row). To cut the crap, find out
how a knight moves yourself, if you don't already know.

The knight is given 3 moves and programmers have to produce the output
of all possible positions the knight can be at in 3 moves (where none
of these final positions could also be achieved in 2 moves eg moving 2
up 1 left and finally 1 right 2 down) in the form:

O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
^

We use a hat to symbolise where the knight is and in my figure above,
that's where the knight ALWAYS starts.

Now I know that there are a maximum of 8 ways a knight can move.
If I call topleft() where the knight moves 2 up 1 left, upleft() where
the knight moves 1 up 2 left, downleft() where the knight moves 1 down
2 left and btmleft 2 down 1 left (intuitively figuring out the
corresponding four) there are 8 functions representing a knight's
possible movements.

Now I'm not gonna use letters and numbers for the coords of the
chessboard but rather x and y where the 1, 1 is the bottom left corner
of a chessboard. So I define a struct called co

struct co {
int x, y;
};

Each of the 'movement' functions returns a struct co eg:

struct co topleft(int x, int y)
{
struct co temp;
if ( (x-1) >= 1 && (y+2) <= 8) {
temp.x = x;
temp.y = y;
return temp;
} else {
temp.x = 0;
temp.y = 0;
return temp;
}
}

In the main function I plan to create a temporary struct co and a
struct co array called pos with 40 elements which is probably a little
much.

So:

struct co temp;
struct co pos[40];
temp.x = 2;
temp.y = 1; /* where every knight starts */
temp = topleft(temp.x, temp.y);
if ( (temp.x != 0) && (temp.y != 0) ) {
temp = topleft(temp.x, temp.y);
if ( (temp.x != 0) && (temp.y != 0) )
temp = topleft(temp.x, temp.y);
if ( (temp.x != 0) && (temp.y != 0) )
pos[0] = temp;
}
temp.x = 2;
temp.y = 1;
/* etc. */

So it goes on an on: topleft, topleft, topleft
topleft, topleft, topright
topleft, topleft, upleft

But I could be writing over 1000 lines of code just for this program!
The competition only allowed and only allows 2 hours to do what you
can and submit your source code and executable via email to wherever
they collect it!
How do I better do this program? Have I got the gist of it? Any of it?

Bert

 

[Bartc]

This is a past question from a programming competition.

On a chess board (8 squares by 8 squares), there's is a knight sitting
on b1 (2 from the left of the bottom row). To cut the crap, find out
how a knight moves yourself, if you don't already know.

But I could be writing over 1000 lines of code just for this program!
The competition only allowed and only allows 2 hours to do what you
can and submit your source code and executable via email to wherever
they collect it!
How do I better do this program? Have I got the gist of it? Any of it?

comp.programming might be better to post to (although less active than
here), as this is not specifically about C.

However, your approach doesn't seem quite right. You start at position P
then you need a function which scans through all legal moves from there (Q1,
Q2, ... Qn). For each of those, eg. Q1, you call the function again to get
R1, R2 etc.

So suggests a recursive solution. Once you've got the 3rd move, you output
the position.

If you can only visit each square once (so may have already been done on 1st
or 2nd move), use an array of 8x8 0's, and mark 1 when you visit a square
for the first time. Only continue with a square (calculate moves from there
or output that position) if this is the first visit.

 

[Bartc]

Oh, and I was going to say, I would be tempted to simply use an index 0..63
or 1..64, rather than (1..8,1..8) because it would simplify some things
(convert back to x,y on output). I might be wrong though.

 

[Johannes Bauer]

This is a past question from a programming competition.

http://nopaste.org/p/awHLzd1bP

Regards,
Johannes

 

[Johannes Bauer]

But I could be writing over 1000 lines of code just for this program!
The competition only allowed and only allows 2 hours to do what you
can and submit your source code and executable via email to wherever
they collect it!
How do I better do this program? Have I got the gist of it? Any of it?

Whoa - I just read that now. How the heck are you going to write 1000
LOC for this problem? I did like the problem and hacked it quickly in
about 15 minutes (and 60 LOC).

Regards,
Johannes

 

[Richard Bos]

http://nopaste.org/p/awHLzd1bP

http://nopaste.org/p/a0GtCw80E

Richard

 

[Johannes Bauer]

http://nopaste.org/p/a0GtCw80E

Posting code in Usenet is a pain because it gets wrapped and looks like
crap. But because of your oh-so-friendly statement, here you go:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MOVES 3

void movelgl(unsigned char new[8][8], int x, int y) {
if ((x < 0) || (x >= 8) || (y < 0) || (y >= 8)) return;
new[x][y] = 1;
}

void moveto(unsigned char new[8][8], int x, int y) {
movelgl(new, x + 1, y + 2);
movelgl(new, x + 2, y + 1);
movelgl(new, x - 1, y + 2);
movelgl(new, x - 2, y + 1);
movelgl(new, x + 1, y - 2);
movelgl(new, x + 2, y - 1);
movelgl(new, x - 1, y - 2);
movelgl(new, x - 2, y - 1);
}

int main(int argc, char **argv) {
unsigned char pos[MOVES + 1][8][8];
int i;

memset(pos, 0, sizeof(pos));
pos[0][2][0] = 1;
for (i = 0; i < MOVES; i++) {
int x, y;
for (x = 0; x < 8; x++) {
for (y = 0; y < 8; y++) {
if (pos[x][y]) {
moveto(pos[i + 1], x, y);
}
}
}
}

{
unsigned char final[8][8];
int x, y;
int i;
for (x = 0; x < 8; x++) {
for (y = 0; y < 8; y++) {
final[x][y] = pos[MOVES][x][y];
for (i = 0; i < MOVES; i++) final[x][y] &= ~pos[x][y];
}
}
for (y = 7; y >= 0; y--) {
for (x = 0; x < 8; x++) {
printf("%d ", final[x][y]);
}
printf("\n");
}
}

return 0;
}

Regards,
Johannes

 

[Bartc]

Sorry I misunderstood the rules about visiting cells.

Your 2-hour deadline is up so here is a solution in C, using recursion as
suggested. But not using 1..64 as also suggested which wasn't such a good
idea.

#include <stdio.h>
#include <string.h>

char board[9][9]={0};
char oldboard[9][9]={0};

void markboard(int x,int y,int limit,int moveno) {

if (x<1 || x>8 || y<1 || y>8) return;

board[x][y]=1;

if (moveno==limit) return;

++moveno;
markboard(x-1,y+2,limit,moveno);
markboard(x-1,y-2,limit,moveno);
markboard(x+1,y+2,limit,moveno);
markboard(x+1,y-2,limit,moveno);
markboard(x-2,y+1,limit,moveno);
markboard(x-2,y-1,limit,moveno);
markboard(x+2,y+1,limit,moveno);
markboard(x+2,y-1,limit,moveno);
}

int main(void) {
#define startx 3
#define starty 1
int x,y;

markboard(startx,starty,2,0);

memcpy(oldboard,board,sizeof(board));

markboard(startx,starty,3,0);

for(y=8; y>=1; --y) {
for (x=1; x<=8; ++x)
printf (" %s",(board[x][y]!=oldboard[x][y])?"1":"0");
printf("\n");
}

}

 

[Ben Bacarisse]

This is a past question from a programming competition.

On a chess board (8 squares by 8 squares), there's is a knight sitting
on b1 (2 from the left of the bottom row). To cut the crap, find out
how a knight moves yourself, if you don't already know.

The knight is given 3 moves and programmers have to produce the output
of all possible positions the knight can be at in 3 moves (where none
of these final positions could also be achieved in 2 moves eg moving 2
up 1 left and finally 1 right 2 down) in the form:

O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
^

We use a hat to symbolise where the knight is and in my figure above,
that's where the knight ALWAYS starts.

It is more fun to generalise to any start position and any number of
moves. If you don't, as Richard H. has said, it is just a printf.

Anyway, I was holding off since this smells of homework, but I see a
solution has been posted. Here, then, is mine.

To get exactly your solution, run it like this:

./knight 3 0 2 | tr +ABCD 0001

This version keeps track of the minimum number of moves needed to
reach a square, despite using depth-first search. That is the only
mildly notable feature of it.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool on_board(int s)
{
return s >= 0 && s <= 7;
}

void mark_moves(int board[8][8], int moves, int n, int x, int y)
{
if (on_board(x) && on_board(y)) {
if (board[x][y] == 0 || board[x][y] > moves)
board[x][y] = moves;
if (moves <= n) {
mark_moves(board, moves + 1, n, x + 1, y + 2);
mark_moves(board, moves + 1, n, x - 1, y + 2);
mark_moves(board, moves + 1, n, x + 2, y + 1);
mark_moves(board, moves + 1, n, x - 2, y + 1);
mark_moves(board, moves + 1, n, x + 1, y - 2);
mark_moves(board, moves + 1, n, x - 1, y - 2);
mark_moves(board, moves + 1, n, x + 2, y - 1);
mark_moves(board, moves + 1, n, x - 2, y - 1);
}
}
}

int main(int argc, char **argv)
{
const char marks[] = "+ABCDEFG";
int board[8][8] = {0};

mark_moves(board, 1,
(argc > 1 ? atoi(argv[1]) : 6),
(argc > 2 ? atoi(argv[2]) : 0),
(argc > 3 ? atoi(argv[3]) : 0));

for (int r = 7; r >= 0; r--) {
for (int c = 0; c < 8; c++) {
int moves = board[r][c];
printf(" %c", moves < sizeof marks - 1 ? marks[moves] : '?');
}
printf("\n");
}
return 0;
}

 

[Walter Roberson]

The knight is given 3 moves and programmers have to produce the output
of all possible positions the knight can be at in 3 moves

Hint: No matter what the starting position is, after 3 moves, the knight
will still be on the board.

 

[Bert]

Here's the original problem:

KNIGHT'S REACH

The diagram to the right illustrates the possible moves for a chess
knight placed at the centre of a 5 by 5 grid of squares. By following
the paths indicated by the arrows the knight can reach any of the
squares marked with a circle in a single move. Since the knight does
not land on the squares it passes over its movement is unimpeded by
other pieces on those squares.



Suppose we represent a chess board as an 8 by 8 grid with an "O"
representing each square as shown below. If a knight begins at the
position marked with an "^" below it then it can reach any of the
positions marked "X" in one move.
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
X O X O O O O O
O O O X O O O O
O O O O O O O O
^

Write a computer program which will determine every square on which a
knight which began from the same position as shown in the diagram
could rest after three moves. Note carefully that some squares on
which the knight landed on its first or second move may not be marked
after the third move since they may be impossible to reach in exactly
three moves.

Your output should begin with the statement:

There are n locations where the knight may rest.

where "n" is the number of possible final locations after three moves
and should include a diagram similar to the example in which an 8 by 8
grid of "O" characters has an "^" to mark the starting position of the
knight and an "X" at each of the positions where it may legally rest
after three moves.

 

[santosh]

Here's the original problem:

[ ... ]

Suppose we represent a chess board as an 8 by 8 grid with an "O"
representing each square as shown below. If a knight begins at the
position marked with an "^" below it then it can reach any of the
positions marked "X" in one move.
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
X O X O O O O O
O O O X O O O O
O O O O O O O O
^

Write a computer program which will determine every square on which a
knight which began from the same position as shown in the diagram
could rest after three moves. Note carefully that some squares on
which the knight landed on its first or second move may not be marked
after the third move since they may be impossible to reach in exactly
three moves.

Your output should begin with the statement:

There are n locations where the knight may rest.

where "n" is the number of possible final locations after three moves
and should include a diagram similar to the example in which an 8 by 8
grid of "O" characters has an "^" to mark the starting position of the
knight and an "X" at each of the positions where it may legally rest
after three moves.

Here you go:

#include <stdio.h>
int main(void) {
puts("There are 26 locations where the knight may rest.\n"
"O O O O O O O O\nX O X O X O O O\nO X O X O X O O\n"
"X O X O X O X O\nO X O X O X O X\nX O X O X O X O\n"
"O X O X O X O X\nX O X O X O X O\n ^");
return 0;
}

 

[Keith Thompson]

Write a computer program which will determine every square on which a
knight which began from the same position as shown in the diagram
could rest after three moves. Note carefully that some squares on
which the knight landed on its first or second move may not be marked
after the third move since they may be impossible to reach in exactly
three moves.

[...]

Note that any position reached after 1 move can also be reached after
3 move; simply make the first move, then make an arbitrary second move
and reverse it.

Any position reachable in 2 moves *cannot* be reached in 3 moves.
Given a board marked with alternating black and white squares, any
move from a white square lands on a black square, and vice versa. If
you start on black, all squares reachable in exactly 1 move are white,
all squares reachable in exactly 2 moves are black, and all squares
reachable in exactly 3 moves are white.

This information, though interesting, is not helpful in programming a
solution to the problem.

 

[Keith Thompson]

Write a computer program which will determine every square on which a
knight which began from the same position as shown in the diagram
could rest after three moves. Note carefully that some squares on
which the knight landed on its first or second move may not be marked
after the third move since they may be impossible to reach in exactly
three moves.

[...]

Note that any position reached after 1 move can also be reached after
3 move; simply make the first move, then make an arbitrary second move
and reverse it.

Any position reachable in 2 moves *cannot* be reached in 3 moves.
Given a board marked with alternating black and white squares, any
move from a white square lands on a black square, and vice versa. If
you start on black, all squares reachable in exactly 1 move are white,
all squares reachable in exactly 2 moves are black, and all squares
reachable in exactly 3 moves are white.

This information, though interesting, is not helpful in programming a
solution to the problem.

It can be. If the required number of moves is N, then for any n
moves if N-n is divisible by two that position is a member of the
solution. Speaking knights, of course.

Sure, that gives you a subset of the set of reachable positions, but I
don't think it does much to help solve the problem as stated.

In this case, all positions reachable in 1 move are in the solution
set for 3 moves, but you still have to check all 3-move positions.
For each sequence of 3 moves, I think that checking whether it's
reachable in 1 move, or even whether you've already reached it in a
different sequence of 3 moves, is a waste of time; just set the flag
for that position and move on.