"Eight Queens" program

Discussion in 'C Programming' started by Matt, Aug 18, 2004.

  1. Matt

    Matt Guest

    I will be grateful if someone explians this part

    colfree[c] = FALSE;
    upfree[row+c] = FALSE;
    downfree[row-c+7] = FALSE;

    of the code below. I don't understand how this marks the downward and
    upward diagonals. How does downfree[row-c+7] mark the diagonal?


    Regards,
    Matt



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

    typedef enum boolean_tag
    { FALSE, TRUE } Boolean_type;

    void WriteBoard(void);
    void AddQueen(void);

    int col[8]; /* column with the queen*/
    Boolean_type colfree[8]; /* is the column free? */
    Boolean_type upfree[15]; /*is the upward diagonal
    free?*/
    Boolean_type downfree[15];/*is the downward diagonal
    free?*/

    int row = -1;/*row whose queen is currently placed*/
    int boards = 0; /*number of positions investigated*/
    int sol = 0; /* number of solutions found */

    /* solve Eight Queens problem */
    void main(void) {
    int i;

    for (i = 0; i < 8; i++)
    colfree = TRUE;
    for (i = 0; i < 15; i++) {
    upfree = TRUE;
    downfree = TRUE;
    }
    AddQueen();

    printf("%d positions investigated.\n", boards);
    printf("%d solutions found.\n", sol);
    }

    /* AddQueen: attempt to place a queen */
    void AddQueen(void)
    {
    int c; /* column being tried for the queen */

    boards++;
    row++;
    for (c = 0; c < 8; c++)
    if (colfree[c] && upfree[row+c] && downfree[row-c+7]) {
    col[row] = c; /* put a queen in (row,c)*/
    colfree[c] = FALSE;
    upfree[row+c] = FALSE;
    downfree[row-c+7] = FALSE;

    if (row == 7) /* termination condition*/
    WriteBoard();
    else
    AddQueen(); /* proceed recursively */

    colfree[c] = TRUE; /* now backtrack by
    removing the queen */
    upfree[row+c] = TRUE;
    downfree[row-c+7] = TRUE;
    }
    row--;
    }

    /* WriteBoard: print a solution */
    void WriteBoard(void) {
    int c;
    int i, j;

    sol++;
    printf("solution %d\n", sol);
    printf("-----------------\n");
    for (i = 0; i < 8; i++) {
    for (j = 0; j < col; j++)
    printf(" -");
    printf(" Q");
    for (j++; j < 8; j++)
    printf(" -");
    printf("\n");
    }
    printf("-----------------\n");
    printf("Press <enter> to continue.");
    scanf("%c", &c);
    }
    --
    comp.lang.c.moderated - moderation address:
    Matt, Aug 18, 2004
    #1
    1. Advertising

  2. Matt

    John Smith Guest

    "Matt" <> wrote in message
    news:...
    > I will be grateful if someone explians this part
    >
    > colfree[c] = FALSE;
    > upfree[row+c] = FALSE;
    > downfree[row-c+7] = FALSE;
    >
    > of the code below. I don't understand how this marks the downward and
    > upward diagonals. How does downfree[row-c+7] mark the diagonal?
    >
    >
    > Regards,
    > Matt
    >
    >
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    >
    > typedef enum boolean_tag
    > { FALSE, TRUE } Boolean_type;
    >
    > void WriteBoard(void);
    > void AddQueen(void);
    >
    > int col[8]; /* column with the queen*/
    > Boolean_type colfree[8]; /* is the column free? */
    > Boolean_type upfree[15]; /*is the upward diagonal
    > free?*/
    > Boolean_type downfree[15];/*is the downward diagonal
    > free?*/
    >
    > int row = -1;/*row whose queen is currently placed*/
    > int boards = 0; /*number of positions investigated*/
    > int sol = 0; /* number of solutions found */
    >
    > /* solve Eight Queens problem */
    > void main(void) {
    > int i;
    >
    > for (i = 0; i < 8; i++)
    > colfree = TRUE;
    > for (i = 0; i < 15; i++) {
    > upfree = TRUE;
    > downfree = TRUE;
    > }
    > AddQueen();
    >
    > printf("%d positions investigated.\n", boards);
    > printf("%d solutions found.\n", sol);
    > }
    >
    > /* AddQueen: attempt to place a queen */
    > void AddQueen(void)
    > {
    > int c; /* column being tried for the queen */
    >
    > boards++;
    > row++;
    > for (c = 0; c < 8; c++)
    > if (colfree[c] && upfree[row+c] && downfree[row-c+7]) {
    > col[row] = c; /* put a queen in (row,c)*/
    > colfree[c] = FALSE;
    > upfree[row+c] = FALSE;
    > downfree[row-c+7] = FALSE;
    >
    > if (row == 7) /* termination condition*/
    > WriteBoard();
    > else
    > AddQueen(); /* proceed recursively */
    >
    > colfree[c] = TRUE; /* now backtrack by
    > removing the queen */
    > upfree[row+c] = TRUE;
    > downfree[row-c+7] = TRUE;
    > }
    > row--;
    > }
    >
    > /* WriteBoard: print a solution */
    > void WriteBoard(void) {
    > int c;
    > int i, j;
    >
    > sol++;
    > printf("solution %d\n", sol);
    > printf("-----------------\n");
    > for (i = 0; i < 8; i++) {
    > for (j = 0; j < col; j++)
    > printf(" -");
    > printf(" Q");
    > for (j++; j < 8; j++)
    > printf(" -");
    > printf("\n");
    > }
    > printf("-----------------\n");
    > printf("Press <enter> to continue.");
    > scanf("%c", &c);
    > }
    > --
    > comp.lang.c.moderated - moderation address:


    I sat down, with a piece of paper and pencil. Draw out a chess board (eight
    by eight squares obviously, colour doesn't matter, so all white :) ). Also
    draw out three columns of squares: one eight deep, and two fifteen deep. The
    three columns will represent colfree, upfree and downfree. Assume if their
    entries are blank, they are true.

    Mentally, step through the program. So, entering AddQueen, row++ makes
    row=0.
    For col=0...
    If... all statements initially are TRUE, so we execute the contents of the
    if statement: colfree[0] = FALSE (mark this in the colfree column).
    upfree[0+0] = FALSE (mark this), downfree [0 + 0 + 7] = FALSE (mark).
    Recurse into AddQueen
    row++ makes row=1
    For col=0...
    If... colfree[0] is FALSE, skip the if statement.
    For statement makes col=1.
    If ... Here we start to see what upfree and downfree represent: upfree[1+1]
    is TRUE but downfree[1-1+7] is FALSE.

    So, upfree seems to represent the diagonals going from bottom right to top
    left, and downfree represents thos going from bottom left to top right.
    (Note that the drawing produced by the program is upside down to me). Each
    diagonal is numbered.
    Upfree numbers them as 0 being the single square at the bottom left corner;
    1 is the diagonal formed by two squares (row,column) (0,1) and (1,0); 2
    formed by (0,2), (1,1), (2,0) etc. The largest diagonal in upfree is
    (0,7),(1,6)...(7,0) i.e. bottom right corner to top left corner.
    Downfree is similar: its numbering is
    0 is formed by the single square (7,0)
    1 by (6,0), (7,1)
    and its largest diagonal is bottom left to top right.
    In both cases there are fifteen diagonals.

    So, the very first square tested is on upfree[0] and downfree[7] (downfree's
    largest diagonal).
    The next square tested (row=1, column=0) is on upfree[1] and downfree[6]
    (but the column is occupied).
    The next tested (row=1, column=1) is on upfree[2] and downfree[7]
    (occupied).
    The next (row=1, column=2) is on upfree[3] and downfree[8], so a queen is
    placed here.

    I hope this rambling helps a bit. All you need is to sit down and think
    about it, you don't even need a computer (except of course to read this
    posting).

    Cheers
    JS
    --
    comp.lang.c.moderated - moderation address:
    John Smith, Aug 21, 2004
    #2
    1. Advertising

  3. Matt

    Brian Inglis Guest

    On 18 Aug 2004 03:32:17 GMT in comp.lang.c.moderated,
    (Matt) wrote:

    >I will be grateful if someone explians this part
    >
    > colfree[c] = FALSE;
    > upfree[row+c] = FALSE;
    > downfree[row-c+7] = FALSE;
    >
    >of the code below. I don't understand how this marks the downward and
    >upward diagonals. How does downfree[row-c+7] mark the diagonal?


    Those two expressions generate indexes to the diagonals from the row
    and column indexes, best illustrated by a couple of tables:

    r+c r+7-c
    c 0 1 2 3 4 5 6 7 c 0 1 2 3 4 5 6 7
    r r
    0 0 1 2 3 4 5 6 7 0 7 6 5 4 3 2 1 0
    1 1 2 3 4 5 6 7 8 1 8 7 6 5 4 3 2 1
    2 2 3 4 5 6 7 8 9 2 9 8 7 6 5 4 3 2
    3 3 4 5 6 7 8 9 10 3 10 9 8 7 6 5 4 3
    4 4 5 6 7 8 9 10 11 4 11 10 9 8 7 6 5 4
    5 5 6 7 8 9 10 11 12 5 12 11 10 9 8 7 6 5
    6 6 7 8 9 10 11 12 13 6 13 12 11 10 9 8 7 6
    7 7 8 9 10 11 12 13 14 7 14 13 12 11 10 9 8 7

    The terms upward and downward are misleading as diagonals could by
    definition be considered up and down or right and left.
    Calling them something like indexes from upper left to bottom right
    i_ul_br and indexes from upper right to bottom left i_ur_bl would be
    more accurate, or the opposite for the directions the diagonals run:
    d_ur_bl and d_ul_br.

    As the expressions appear in a few places, using a couple of macros
    may make things cleaner and clearer:

    #define I_UL_BR(r,c) ((r)+(c))
    #define I_UR_BL(r,c) ((r)+7-(c))

    and it would be better to name the variables more consistently
    as r and c, or row and col, rather than mixing row and c.

    --
    Thanks. Take care, Brian Inglis Calgary, Alberta, Canada

    (Brian dot Inglis at SystematicSw dot ab dot ca)
    fake address use address above to reply
    --
    comp.lang.c.moderated - moderation address:
    Brian Inglis, Aug 21, 2004
    #3
  4. Matt

    Dag Viken Guest

    "Matt" <> wrote in message
    news:...
    > I will be grateful if someone explians this part
    >
    > colfree[c] = FALSE;
    > upfree[row+c] = FALSE;
    > downfree[row-c+7] = FALSE;
    >
    > of the code below. I don't understand how this marks the downward and
    > upward diagonals. How does downfree[row-c+7] mark the diagonal?


    There are 15 diagonals going from lower left to upper right and 15 diagonals
    going from upper left to lower right. For any row and column, the formulas
    'row+c' and 'row-c+7' computes the diagonal number for each direction as
    shown below.

    The 15 'upward' diagonals, in direction lower left to upper right corner,
    are defined like this (in [row,col] format):

    Diagonal 0 (row+col = 0): [0,0]
    Diagonal 1 (row+col = 1): [0,1] [1,0]
    Diagonal 2 (row+col = 2): [0,2] [1,1] [2,0]
    Diagonal 3 (row+col = 3): [0,3] [1,2] [2,1] [3,0]
    Diagonal 4 (row+col = 4): [0,4] [1,3] [2,2] [3,1] [4,0]
    Diagonal 5 (row+col = 5): [0,5] [1,4] [2,3] [3,2] [4,1] [5,0]
    Diagonal 6 (row+col = 6): [0,6] [1,5] [2,4] [3,3] [4,2] [5,1] [6,0]
    Diagonal 7 (row+col = 7): [0,7] [1,6] [2,5] [3,4] [4,3] [5,2] [6,1]
    [7,0]
    Diagonal 8 (row+col = 8): [1,7] [2,6] [3,5] [4,4] [5,3] [6,2] [7,1]
    Diagonal 9 (row+col = 9): [2,7] [3,6] [4,5] [5,4] [6,3] [7,2]
    Diagonal 10 (row+col = 10): [3,7] [4,6] [5,5] [6,4] [7,3]
    Diagonal 11 (row+col = 11): [4,7] [5,6] [6,5] [7,4]
    Diagonal 12 (row+col = 12): [5,7] [6,6] [7,5]
    Diagonal 13 (row+col = 13): [6,7] [7,6]
    Diagonal 14 (row+col = 14): [7,7]

    These are the 15 'downward' diagonals, in direction upper left to lowerer
    right corner:

    Diagonal 0 (row-col+7 = 0): [0,7]
    Diagonal 1 (row-col+7 = 1): [0,6] [1,7]
    Diagonal 2 (row-col+7 = 2): [0,5] [1,6] [2,7]
    Diagonal 3 (row-col+7 = 3): [0,4] [1,5] [2,6] [3,7]
    Diagonal 4 (row-col+7 = 4): [0,3] [1,4] [2,5] [3,6] [4,7]
    Diagonal 5 (row-col+7 = 5): [0,2] [1,3] [2,4] [3,5] [4,6] [5,7]
    Diagonal 6 (row-col+7 = 6): [0,1] [1,2] [2,3] [3,4] [4,5] [5,6] [6,7]
    Diagonal 7 (row-col+7 = 7): [0,0] [1,1] [2,2] [3,3] [4,4] [5,5] [6,6]
    [7,7]
    Diagonal 8 (row-col+7 = 8): [1,0] [2,1] [3,2] [4,3] [5,4] [6,5] [7,6]
    Diagonal 9 (row-col+7 = 9): [2,0] [3,1] [4,2] [5,3] [6,4] [7,5]
    Diagonal 10 (row-col+7 = 10): [3,0] [4,1] [5,2] [6,3] [7,4]
    Diagonal 11 (row-col+7 = 11): [4,0] [5,1] [6,2] [7,3]
    Diagonal 12 (row-col+7 = 12): [5,0] [6,1] [7,2]
    Diagonal 13 (row-col+7 = 13): [6,0] [7,1]
    Diagonal 14 (row-col+7 = 14): [7,0]

    Thanks for the program. I remember doing this a long time ago.

    Dag
    --
    comp.lang.c.moderated - moderation address:
    Dag Viken, Aug 21, 2004
    #4
  5. Matt

    sathya_me Guest

    Matt wrote:

    >I will be grateful if someone explians this part
    >
    > colfree[c] = FALSE;
    > upfree[row+c] = FALSE;
    > downfree[row-c+7] = FALSE;
    >
    >of the code below. I don't understand how this marks the downward and
    >upward diagonals. How does downfree[row-c+7] mark the diagonal?
    >
    >
    >Regards,
    >Matt
    >
    >
    >


    As a beginner I just made a try to replay.

    >
    >#include <stdio.h>
    >#include <stdlib.h>
    >
    >typedef enum boolean_tag
    > { FALSE, TRUE } Boolean_type;
    >
    >void WriteBoard(void);
    >void AddQueen(void);
    >
    >int col[8]; /* column with the queen*/
    >Boolean_type colfree[8]; /* is the column free? */
    >Boolean_type upfree[15]; /*is the upward diagonal
    > free?*/
    >Boolean_type downfree[15];/*is the downward diagonal
    > free?*/
    >
    >int row = -1;/*row whose queen is currently placed*/
    >int boards = 0; /*number of positions investigated*/
    >int sol = 0; /* number of solutions found */
    >
    >/* solve Eight Queens problem */
    >void main(void) {
    > int i;
    >
    > for (i = 0; i < 8; i++)
    > colfree = TRUE;
    > for (i = 0; i < 15; i++) {
    > upfree = TRUE;
    > downfree = TRUE;
    > }
    > AddQueen();
    >
    > printf("%d positions investigated.\n", boards);
    > printf("%d solutions found.\n", sol);
    >}
    >
    >/* AddQueen: attempt to place a queen */
    >void AddQueen(void)
    >{
    > int c; /* column being tried for the queen */
    >
    > boards++;
    > row++;
    > for (c = 0; c < 8; c++)
    > if (colfree[c] && upfree[row+c] && downfree[row-c+7]) {
    > col[row] = c; /* put a queen in (row,c)*/
    > colfree[c] = FALSE;
    > upfree[row+c] = FALSE;
    > downfree[row-c+7] = FALSE;
    >
    > if (row == 7) /* termination condition*/
    > WriteBoard();
    > else
    > AddQueen(); /* proceed recursively */
    >
    > colfree[c] = TRUE; /* now backtrack by
    > removing the queen */
    > upfree[row+c] = TRUE;
    > downfree[row-c+7] = TRUE;
    > }
    > row--;
    >}
    >
    >

    <OT>
    I think that this is the way the bit board works in chess engine. The
    whole array is
    made up of *imagination* (Virtual space). That is why the

    colfree[c] = TRUE; /* now backtrack by
    removing the queen */
    upfree[row+c] = TRUE;
    downfree[row-c+7] = TRUE;

    is said to be back tracking. That means the squares given space to
    hold the Queen.
    I cannot understand why there is a recursive call for AddQueen() function.
    I can say that the arrays are squares which traverse through each
    square during
    the for loop. But I cannot understand about the 92 different solutions.
    If you either try the newsgroups such as comp.programming or
    rec.games.chess.computers would
    be a correct place. You can also get good replays in

    www.talkchess.com

    (under the message board computer-chess club. But you have to
    register yourself which is free of cost).

    If you get the correct replay please don't forget to give a summary in
    the clc.
    BTW where did you get this code from?

    </OT>

    >/* WriteBoard: print a solution */
    >void WriteBoard(void) {
    > int c;
    > int i, j;
    >
    > sol++;
    > printf("solution %d\n", sol);
    > printf("-----------------\n");
    > for (i = 0; i < 8; i++) {
    > for (j = 0; j < col; j++)
    > printf(" -");
    > printf(" Q");
    > for (j++; j < 8; j++)
    > printf(" -");
    > printf("\n");
    > }
    > printf("-----------------\n");
    > printf("Press <enter> to continue.");
    > scanf("%c", &c);
    >}
    >
    >

    Thanks,
    N.Sathyashrayan

    --
    "Combination is the heart of chess"
    A.Alekhine
    Mail to:
    sathyashrayan25 AT yahoo DOT com
    (remove the AT and DOT)
    --
    comp.lang.c.moderated - moderation address:
    sathya_me, Aug 21, 2004
    #5
  6. Matt

    -berlin.de Guest

    In comp.lang.c Matt <> wrote:
    > I will be grateful if someone explians this part
    >
    > colfree[c] = FALSE;
    > upfree[row+c] = FALSE;
    > downfree[row-c+7] = FALSE;


    > of the code below. I don't understand how this marks the downward and
    > upward diagonals. How does downfree[row-c+7] mark the diagonal?


    Just draw yourself a chess board and draw all diagonals. Then label
    the diagonals that go upwards with the number that you get when you
    add the row and column number (each going from 0 to 7) of a field the
    diagonal is going through. You will see that you get the same number
    (one between 0 an 14) for each field the diagonal crosses. So it's a
    useful scheme to label the upward diagonals. Now do the same for the
    downward diagonals, but label them with the difference between the
    row number and the column number, incremented by seven. Again, each
    diagonal gets a number that is the same for each field it crosses
    and all numbers are in the range from 0 to 14. So, again, you have
    a useful scheme for labeling the downward diagonals. And finding a
    labeling scheme is the only tricky part about the algorithm.

    Now in your program you have an array for free columns and two for
    free diagonals. If you place a queen on a certain field you must
    mark the column where you put it in the array of free columns as
    used up (that's the first line, "colfree[c] = FALSE;") as well as
    the upward and downward going diagonals crossing that field (that's
    the next two lines). Now you can in further iterations check if
    a certain field can be used for another queen or not just from
    the fields coordinates.

    BTW, main() is a function that must return an int. And if you have

    int c;
    scanf("%c", &c);

    then you need "%d" as the format specifier, "%c" is for chars.

    Regards, Jens
    --
    \ Jens Thoms Toerring ___ -berlin.de
    \__________________________ http://www.toerring.de
    --
    comp.lang.c.moderated - moderation address:
    -berlin.de, Aug 21, 2004
    #6
    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. cfanatic
    Replies:
    3
    Views:
    543
    cfanatic
    Oct 16, 2003
  2. jblazi

    The eight queens problem

    jblazi, Aug 30, 2004, in forum: C++
    Replies:
    9
    Views:
    2,538
    Karl Heinz Buchegger
    Aug 30, 2004
  3. Jeff Epler
    Replies:
    10
    Views:
    651
    Anton Vredegoor
    Aug 20, 2003
  4. sathya_me

    Is this OT(was:Re: "Eight Queens" program)

    sathya_me, Aug 20, 2004, in forum: C Programming
    Replies:
    5
    Views:
    302
    sathya_me
    Aug 20, 2004
  5. SM Ryan

    Re: "Eight Queens" program

    SM Ryan, Aug 21, 2004, in forum: C Programming
    Replies:
    0
    Views:
    360
    SM Ryan
    Aug 21, 2004
Loading...

Share This Page