Velocity Reviews > In 3 moves, where can the knight go?

# In 3 moves, where can the knight go?

Bert
Guest
Posts: n/a

 06-20-2008
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) <= {
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
Guest
Posts: n/a

 06-20-2008

"Bert" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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

Bartc
Guest
Posts: n/a

 06-20-2008

"Bartc" <(E-Mail Removed)> wrote in message
news:UnL6k.12662\$(E-Mail Removed) m...
>
> "Bert" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>> 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?

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.. because it would simplify some things
(convert back to x,y on output). I might be wrong though.

--
Bartc

Johannes Bauer
Guest
Posts: n/a

 06-20-2008
Bert schrieb:
> This is a past question from a programming competition.

http://nopaste.org/p/awHLzd1bP

Regards,
Johannes

--
"Wer etwas kritisiert muss es noch lange nicht selber besser können. Es
reicht zu wissen, daß andere es besser können und andere es auch
besser machen um einen Vergleich zu bringen." - Wolfgang Gerber
in de.sci.electronics <47fa8447\$0\$11545\$(E-Mail Removed)>

Johannes Bauer
Guest
Posts: n/a

 06-20-2008
Bert schrieb:

> 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

--
"Wer etwas kritisiert muss es noch lange nicht selber besser können. Es
reicht zu wissen, daß andere es besser können und andere es auch
besser machen um einen Vergleich zu bringen." - Wolfgang Gerber
in de.sci.electronics <47fa8447\$0\$11545\$(E-Mail Removed)>

Richard Bos
Guest
Posts: n/a

 06-20-2008
Johannes Bauer <(E-Mail Removed)> wrote:

> Bert schrieb:
> > This is a past question from a programming competition.

>
> http://nopaste.org/p/awHLzd1bP

http://nopaste.org/p/a0GtCw80E

Richard

Johannes Bauer
Guest
Posts: n/a

 06-20-2008
Richard Bos schrieb:

> 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 >= || (y < 0) || (y >= ) 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[i][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[i][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

--
"Wer etwas kritisiert muss es noch lange nicht selber besser können. Es
reicht zu wissen, daß andere es besser können und andere es auch
besser machen um einen Vergleich zu bringen." - Wolfgang Gerber
in de.sci.electronics <47fa8447\$0\$11545\$(E-Mail Removed)>

Bartc
Guest
Posts: n/a

 06-20-2008
"Bartc" <(E-Mail Removed)> wrote in message
news:UnL6k.12662\$(E-Mail Removed) m...
>
> "Bert" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>> 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?

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> 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");
}

}

--
Bartc

Ben Bacarisse
Guest
Posts: n/a

 06-20-2008
Bert <(E-Mail Removed)> writes:

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

--
Ben.

Walter Roberson
Guest
Posts: n/a

 06-20-2008
In article <(E-Mail Removed)>,
Bert <(E-Mail Removed)> wrote:

>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.
--
"When we all think alike no one is thinking very much."
-- Walter Lippmann