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

S

sathya_me

No body answered for the below question. Though i ma not the OP i wast
to know weather it is a OT
and guid me to the correct NG. (may be comp.programming ?)
--------------------------------------------------message
starts--------------------------------------
Subject:
"Eight Queens" program
From:
(e-mail address removed) (Matt)
Date:
18 Aug 2004 03:32:17 GMT
Newsgroups:
comp.lang.c,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?


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

--------------------------------------------------------------message
ends---------------------------------------

--
"Combination is the heart of chess"
A.Alekhine
Mail to:
sathyashrayan25 AT yahoo DOT com
(remove the AT and DOT)
 
J

Jens.Toerring

sathya_me said:
No body answered for the below question. Though i ma not the OP i wast
to know weather it is a OT
and guid me to the correct NG. (may be comp.programming ?)
Click to expand...

Probably yes, since it's not a question about C but some algorithmic
problem (and a rather simple one which the OP could have solved by
a bit of trying himself;-). But as you will see I just posted a
reply.
Regards, Jens
 
J

Jens.Toerring

Probably yes, since it's not a question about C but some algorithmic
problem (and a rather simple one which the OP could have solved by
a bit of trying himself;-). But as you will see I just posted a
reply.
Click to expand...

A reason for replies not showing uo could be that the the OP
crossposted to comp.lang.c.moderated and that it seems like
replies appearing here only after they have been allowed for
that other group (which seems to take quite a lot of time).
I only noticed that after my reply didn't appear here and I
wrote another one, assuming I had hit the wrong key when
sending the first one and the second one also not appeared;-)

Regards, Jens
 
J

John Smith

sathya_me said:
No body answered for the below question. Though i ma not the OP i wast
to know weather it is a OT
and guid me to the correct NG. (may be comp.programming ?)
--------------------------------------------------message
starts--------------------------------------
Subject:
"Eight Queens" program
From:
(e-mail address removed) (Matt)
Date:
18 Aug 2004 03:32:17 GMT
Newsgroups:
comp.lang.c,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?


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

--------------------------------------------------------------message
ends---------------------------------------

--
"Combination is the heart of chess"
A.Alekhine
Mail to:
sathyashrayan25 AT yahoo DOT com
(remove the AT and DOT)
Click to expand...


I did answer, it didn't seem to make it to the server. Let's try again...


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).
 
J

John Smith

A reason for replies not showing uo could be that the the OP
crossposted to comp.lang.c.moderated and that it seems like
replies appearing here only after they have been allowed for
that other group (which seems to take quite a lot of time).
I only noticed that after my reply didn't appear here and I
wrote another one, assuming I had hit the wrong key when
sending the first one and the second one also not appeared;-)

Regards, Jens
Click to expand...

Ah. I didn't notice the cross-posting. Thanks for pointing it out, I was
wondering what happened to my reply too.

JS
 
S

sathya_me

John said:
No body answered for the below question. Though i ma not the OP i wast
to know weather it is a OT
and guid me to the correct NG. (may be comp.programming ?)
--------------------------------------------------message
starts--------------------------------------
Subject:
"Eight Queens" program
From:
(e-mail address removed) (Matt)
Date:
18 Aug 2004 03:32:17 GMT
Newsgroups:
comp.lang.c,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?


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

--------------------------------------------------------------message
ends---------------------------------------

--
"Combination is the heart of chess"
A.Alekhine
Mail to:
sathyashrayan25 AT yahoo DOT com
(remove the AT and DOT)
Click to expand...


I did answer, it didn't seem to make it to the server. Let's try again...


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.
Click to expand...

Helped a lot and thanks for your replay.

Thanks,
N.Sathyashrayan

--
"Combination is the heart of chess"
A.Alekhine
Mail to:
sathyashrayan25 AT yahoo DOT com
(remove the AT and DOT)
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

"Eight Queens" program 5
Help in this program. 2
Need help in debugging tic tac toe (Beginner) 0
C program: memory leak/ segmentation fault/ memory limit exceeded 0
Adding adressing of IPv6 to program 1
Comparison of Integer and Pointer (that's supposed to be an Integer). Where did I go wrong? 0
Could you fix my code please? (i get no output after inputing the number) 1
program not working properly. book example. program included. 6

Members online

Total: 34 (members: 1, guests: 33)
Robots: 379

Forum statistics

Threads
473,755
Messages
2,569,536
Members
45,007
Latest member
obedient dusk

Latest Threads

Top