In 3 moves, where can the knight go?

**Bartc** · Jun 27 '08, 07:42 PM

Re: In 3 moves, where can the knight go?

"Bert" <albert.xtheunk nown0@gmail.com wrote in message
news:7ec332be-f960-4271-b2a9-62e61f47e737@q2 4g2000prf.googl egroups.com...

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.programmin g 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** · Jun 27 '08, 07:42 PM

Re: In 3 moves, where can the knight go?

"Bartc" <bc@freeuk.comw rote in message
news:UnL6k.1266 2$E41.4755@text .news.virginmed ia.com...

>
"Bert" <albert.xtheunk nown0@gmail.com wrote in message
news:7ec332be-f960-4271-b2a9-62e61f47e737@q2 4g2000prf.googl egroups.com...

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

--
Bartc

**Richard Heathfield** · Jun 27 '08, 07:42 PM

Re: In 3 moves, where can the knight go?

Bert said:

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

The caret points to c1. I'll assume you are pointing to the right place and
that you merely mistyped c1.

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 start with analysis. In one move, he can get to B:

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 B O B O O O O
B O O O B O O O
O O A O O O O O

In two moves, he can get to C (but we won't return to A or B):

O O O O O O O O
O O O O O O O O
O O O O O O O O
C O C O C O O O
O C O C O C O O
O B C B O O C O
B C O C B C O O
C O A O C O C O

In three moves, he can get to D (but we won't return to A, B, or C):

O O O O O O O O
O X O X O X O O
X O X O X O X O
C X C X C X O X
X C X C X C X O
O B C B O X C X
B C X C B C X O
C X A O C X C X

Replacing all X with 1 and non-X with 0 gives us:

O O O O O O O O
O 1 O 1 O 1 O O
1 O 1 O 1 O 1 O
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
O 0 0 0 0 1 0 1
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 1

The program is now easy to write: simply printf the above grid. The
performance should be impressive. If you really did mean b1 rather than
c1, adjust the solution accordingly.

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.

You'd find that 0, 0 works better with arrays.

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;

How does this actually move anything? Don't you mean temp.x = x-1, temp.y =
y+2?

<snip>

But I could be writing over 1000 lines of code just for this program!

1000 lines isn't all that many, really. But you don't need that many
anyway.

Look up loops and stuff. Oh, and recursion, in this case. (Always assuming
you don't want to do the quick and easy printf.)

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

**Johannes Bauer** · Jun 27 '08, 07:42 PM

Re: In 3 moves, where can the knight go?

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.electron ics <47fa8447$0$115 45$9b622d9e@new s.freenet.de>

**Johannes Bauer** · Jun 27 '08, 07:42 PM

Re: In 3 moves, where can the knight go?

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.electron ics <47fa8447$0$115 45$9b622d9e@new s.freenet.de>

**Richard Bos** · Jun 27 '08, 07:42 PM

Re: In 3 moves, where can the knight go?

Johannes Bauer <dfnsonfsduifb@ gmx.dewrote:

Bert schrieb:

This is a past question from a programming competition.

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

http://nopaste.org/p/a0GtCw80E

Richard

**Johannes Bauer** · Jun 27 '08, 07:42 PM

Re: In 3 moves, where can the knight go?

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(unsigne d 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[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.electron ics <47fa8447$0$115 45$9b622d9e@new s.freenet.de>

**Bartc** · Jun 27 '08, 07:42 PM

Re: In 3 moves, where can the knight go?

"Bartc" <bc@freeuk.comw rote in message
news:UnL6k.1266 2$E41.4755@text .news.virginmed ia.com...

>
"Bert" <albert.xtheunk nown0@gmail.com wrote in message
news:7ec332be-f960-4271-b2a9-62e61f47e737@q2 4g2000prf.googl egroups.com...

>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>8) return;

board[x][y]=1;

if (moveno==limit) return;

++moveno;
markboard(x-1,y+2,limit,mov eno);
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,mov eno);
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(start x,starty,2,0);

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

markboard(start x,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** · Jun 27 '08, 07:42 PM

Re: In 3 moves, where can the knight go?

Bert <albert.xtheunk nown0@gmail.com 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(boar d, moves + 1, n, x + 1, y + 2);
mark_moves(boar d, moves + 1, n, x - 1, y + 2);
mark_moves(boar d, moves + 1, n, x + 2, y + 1);
mark_moves(boar d, moves + 1, n, x - 2, y + 1);
mark_moves(boar d, moves + 1, n, x + 1, y - 2);
mark_moves(boar d, moves + 1, n, x - 1, y - 2);
mark_moves(boar d, moves + 1, n, x + 2, y - 1);
mark_moves(boar d, moves + 1, n, x - 2, y - 1);
}
}
}

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

mark_moves(boar d, 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** · Jun 27 '08, 07:42 PM

Re: In 3 moves, where can the knight go?

In article <7ec332be-f960-4271-b2a9-62e61f47e737@q2 4g2000prf.googl egroups.com>,
Bert <albert.xtheunk nown0@gmail.com 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

**CBFalconer** · Jun 27 '08, 07:42 PM

Re: In 3 moves, where can the knight go?

Richard Heathfield wrote:

Bert said:
>

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

>
The caret points to c1. I'll assume you are pointing to the right
place and that you merely mistyped c1.
>

>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 start with analysis. In one move, he can get to B:
>
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 B O B O O O O
B O O O B O O O
O O A O O O O O
>
In two moves, he can get to C (but we won't return to A or B):

However, he CAN return to A, which makes all the B positions
possible after three moves.

>
O O O O O O O O
O O O O O O O O
O O O O O O O O
C O C O C O O O
O C O C O C O O
O B C B O O C O
B C O C B C O O
C O A O C O C O
>
In three moves, he can get to D (but we won't return to A, B, or C):
>
O O O O O O O O
O X O X O X O O
X O X O X O X O
C X C X C X O X
X C X C X C X O
O B C B O X C X
B C X C B C X O
C X A O C X C X

And once more, he CAN return to a B position.

>
Replacing all X with 1 and non-X with 0 gives us:
>
O O O O O O O O
O 1 O 1 O 1 O O
1 O 1 O 1 O 1 O
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
O 0 0 0 0 1 0 1
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 1

So the above should also replace all B's with 1, leading to:

0 0 0 0 0 0 0 0
O 1 O 1 O 1 O O
1 O 1 O 1 O 1 O
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
O 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 0 0 1 0 1

Which exhibits a regular pattern, with an excluded area.

>
The program is now easy to write: simply printf the above grid.
The performance should be impressive. If you really did mean b1
rather than c1, adjust the solution accordingly.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.

** Posted from http://www.teranews.com **

**Dann Corbit** · Jun 27 '08, 07:42 PM

Re: In 3 moves, where can the knight go?

"Richard Heathfield" <rjh@see.sig.in validwrote in message
news:PZadnfcbn5 75GcbVRVnytAA@b t.com...

Bert said:
>

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

>
The caret points to c1. I'll assume you are pointing to the right place
and
that you merely mistyped c1.
>

>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 start with analysis. In one move, he can get to B:
>
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 B O B O O O O
B O O O B O O O
O O A O O O O O
>
In two moves, he can get to C (but we won't return to A or B):
>
O O O O O O O O
O O O O O O O O
O O O O O O O O
C O C O C O O O
O C O C O C O O
O B C B O O C O
B C O C B C O O
C O A O C O C O
>
In three moves, he can get to D (but we won't return to A, B, or C):
>
O O O O O O O O
O X O X O X O O
X O X O X O X O
C X C X C X O X
X C X C X C X O
O B C B O X C X
B C X C B C X O
C X A O C X C X
>
Replacing all X with 1 and non-X with 0 gives us:
>
O O O O O O O O
O 1 O 1 O 1 O O
1 O 1 O 1 O 1 O
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
O 0 0 0 0 1 0 1
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 1
>
The program is now easy to write: simply printf the above grid. The
performance should be impressive. If you really did mean b1 rather than
c1, adjust the solution accordingly.
>

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

>
You'd find that 0, 0 works better with arrays.
>

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

>
How does this actually move anything? Don't you mean temp.x = x-1, temp.y
=
y+2?
>
<snip>
>

>But I could be writing over 1000 lines of code just for this program!

>
1000 lines isn't all that many, really. But you don't need that many
anyway.
>
Look up loops and stuff. Oh, and recursion, in this case. (Always assuming
you don't want to do the quick and easy printf.)

#include <stdio.h>

static int board[8][8];

int isLegal(int row, int col)
{
if (row >= 0 && row <= 7)
if (col >= 0 && col <= 7)
return 1;
return 0;
}
void makeMoves(int startrow, int startcol, int depth)
{
board[startrow][startcol]++;

if (isLegal(startr ow + 2, startcol - 1) && depth)
makeMoves(start row + 2, startcol - 1, depth-1);
if (isLegal(startr ow + 2, startcol + 1) && depth)
makeMoves(start row + 2, startcol + 1, depth-1);
if (isLegal(startr ow - 2, startcol - 1) && depth)
makeMoves(start row - 2, startcol - 1, depth-1);
if (isLegal(startr ow - 2, startcol + 1) && depth)
makeMoves(start row - 2, startcol + 1, depth-1);
if (isLegal(startr ow + 1, startcol + 2) && depth)
makeMoves(start row + 1, startcol + 2, depth-1);
if (isLegal(startr ow + 1, startcol - 2) && depth)
makeMoves(start row + 1, startcol - 2, depth-1);
if (isLegal(startr ow - 1, startcol + 2) && depth)
makeMoves(start row - 1, startcol + 2, depth-1);
if (isLegal(startr ow - 1, startcol - 2) && depth)
makeMoves(start row - 1, startcol - 2, depth-1);

}

void printboard(void )
{
int i,
j;
for (i = 0; i <= 7; i++) {
for (j = 0; j <= 7; j++) {
printf("%02d ", board[i][j]);
}
putchar('\n');
putchar('\n');
}
putchar('\n');
}

int main(int argc, char **argv)
{
makeMoves(7, 1, 3);
printboard();
return 0;
}
/*
Starting at B1, I get this:

00 00 00 00 00 00 00 00

02 00 03 00 01 00 00 00

00 04 00 06 00 03 00 00

03 02 04 01 03 00 03 00

01 03 02 06 02 02 00 01

09 01 13 00 06 01 04 00

01 04 01 11 01 03 00 02

02 04 03 01 02 01 02 00
*/

** Posted from http://www.teranews.com **

**Dann Corbit** · Jun 27 '08, 07:42 PM

Re: In 3 moves, where can the knight go?

"Dann Corbit" <dcorbit@connx. comwrote in message
news:a8b2d$485c 1185$4790@news. teranews.com...

void makeMoves(int startrow, int startcol, int depth)
{
board[startrow][startcol]++;
>
if (isLegal(startr ow + 2, startcol - 1) && depth)
makeMoves(start row + 2, startcol - 1, depth-1);
if (isLegal(startr ow + 2, startcol + 1) && depth)
makeMoves(start row + 2, startcol + 1, depth-1);
if (isLegal(startr ow - 2, startcol - 1) && depth)
makeMoves(start row - 2, startcol - 1, depth-1);
if (isLegal(startr ow - 2, startcol + 1) && depth)
makeMoves(start row - 2, startcol + 1, depth-1);
if (isLegal(startr ow + 1, startcol + 2) && depth)
makeMoves(start row + 1, startcol + 2, depth-1);
if (isLegal(startr ow + 1, startcol - 2) && depth)
makeMoves(start row + 1, startcol - 2, depth-1);
if (isLegal(startr ow - 1, startcol + 2) && depth)
makeMoves(start row - 1, startcol + 2, depth-1);
if (isLegal(startr ow - 1, startcol - 2) && depth)
makeMoves(start row - 1, startcol - 2, depth-1);
>
}

Better:

void makeMoves(int startrow, int startcol, int depth)
{
int i,
j;
board[startrow][startcol]++;
for (i = -1; i <= 1; i += 2) {
for (j = -2; j <= 2; j += 4) {
if (isLegal(startr ow + i, startcol + j) && depth)
makeMoves(start row + i, startcol + j, depth - 1);
if (isLegal(startr ow + j, startcol + i) && depth)
makeMoves(start row + j, startcol + i, depth - 1);
}
}
}

** Posted from http://www.teranews.com **

**Bert** · Jun 27 '08, 07:42 PM

Re: In 3 moves, where can the knight go?

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.

In 3 moves, where can the knight go?

In 3 moves, where can the knight go?

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment