"Eight Queens" program

[Matt]

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

 

[John Smith]

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

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

 

[Brian Inglis]

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

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.

 

[Dag Viken]

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

 

[sathya_me]

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?

/* 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)

 

[Jens.Toerring]

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