In 3 moves, where can the knight go?

Discussion in 'C Programming' started by Bert, Jun 20, 2008.

  1. Bert

    Bert Guest

    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
     
    Bert, Jun 20, 2008
    #1
    1. Advertising

  2. Bert

    Bartc Guest

    "Bert" <> wrote in message
    news:...
    > 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, Jun 20, 2008
    #2
    1. Advertising

  3. Bert

    Bartc Guest

    "Bartc" <> wrote in message
    news:UnL6k.12662$...
    >
    > "Bert" <> wrote in message
    > news:...
    >> 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
     
    Bartc, Jun 20, 2008
    #3
  4. 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$>
     
    Johannes Bauer, Jun 20, 2008
    #4
  5. 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$>
     
    Johannes Bauer, Jun 20, 2008
    #5
  6. Bert

    Richard Bos Guest

    Richard Bos, Jun 20, 2008
    #6
  7. 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 >= 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

    --
    "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$>
     
    Johannes Bauer, Jun 20, 2008
    #7
  8. Bert

    Bartc Guest

    "Bartc" <> wrote in message
    news:UnL6k.12662$...
    >
    > "Bert" <> wrote in message
    > news:...
    >> 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,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
     
    Bartc, Jun 20, 2008
    #8
  9. Bert <> 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.
     
    Ben Bacarisse, Jun 20, 2008
    #9
  10. In article <>,
    Bert <> 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
     
    Walter Roberson, Jun 20, 2008
    #10
  11. Bert

    Bert Guest

    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.
     
    Bert, Jun 21, 2008
    #11
  12. Bert

    santosh Guest

    Bert wrote:

    > 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;
    }
     
    santosh, Jun 21, 2008
    #12
  13. Bert <> writes:
    [...]
    > 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 (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Jun 25, 2008
    #13
  14. CBFalconer <> writes:
    > Keith Thompson wrote:
    > > Bert <> writes:
    > > [...]
    > >> 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.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Jun 26, 2008
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    9
    Views:
    531
    Kai-Uwe Bux
    Jan 30, 2006
  2. Robin Rytich
    Replies:
    0
    Views:
    693
    Robin Rytich
    Mar 10, 2010
  3. Gabriel Genellina

    Knight's tour Warndorff's algorithm problem

    Gabriel Genellina, Mar 10, 2010, in forum: Python
    Replies:
    4
    Views:
    1,122
    Terry Reedy
    Mar 11, 2010
  4. Ruby Quiz

    [QUIZ] Knight's Travails (#27)

    Ruby Quiz, Apr 8, 2005, in forum: Ruby
    Replies:
    14
    Views:
    471
    Brian Schröder
    May 10, 2005
  5. Ruby Quiz

    [SUMMARY] Knight's Travails (#27)

    Ruby Quiz, Apr 14, 2005, in forum: Ruby
    Replies:
    3
    Views:
    199
    James Edward Gray II
    Apr 15, 2005
Loading...

Share This Page