440,822 Members | 729 Online
Need help? Post your question and get tips & solutions from a community of 440,822 IT Pros & Developers. It's quick & easy.

# "Eight Queens" program

 P: n/a 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 #include 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 to continue."); scanf("%c", &c); } -- comp.lang.c.moderated - moderation address: cl**@plethora.net Nov 14 '05 #1
5 Replies