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[i] = TRUE;
for (i = 0; i < 15; i++) {
upfree[i] = TRUE;
downfree[i] = 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[i]; 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: cl**@plethora.net