The eight queens problem

J

jblazi

In the book "Algortims and Data Structures" by Wirth there is a program in
Pascal to compute all 92 solutions of the above mentioned problem. I tried
to translate his program into C++, the only small problem being that he
uses array with a starting index other than zero. Here is my solution:


// Pascal like array with arbitrary indeces
class Array {
int *datum,start_index,end_index;

public:
Array(int s_index,int e_index) {start_index = s_index; end_index = e_index;datum = new int(end_index-start_index+1);}
#include "stdafx.h"
int& operator [](int i) {return *(datum-start_index+i);}
};

// x : row of queen in the i-th coloumn
// a : no queen is in the the i-th row
// b : no queen is in the the i-th diagonal
// which has positive slope
// c : no queen is in the the i-th diagonal
// which has negative slope


Array a(1,8),x(1,8),b(2,16),c(-7,7);

void print_queens()
{
static int cnt = 0;

printf("%2d: ",++cnt);
for(int k=1;k<=8;k++)
printf("%4d",x[k]);
printf("\n");
}

void set_queen(int i)
{
int j;
for(j=1;j<=8;j++)
if (a[j] && b[i+j] && c[i-j]) {
x = j;
a[j] = b[i+j] = c[i-j] = 0;
if (i < 8) set_queen(i+1); else print_queens();
a[j] = b[i+j] = c[i-j] = 1;
}
}

int _tmain(int argc, _TCHAR* argv[])
{
for(int i=1;i<=8;i++) a=1;
for(int i=2;i<=16;i++) b=1;
for(int i=-7;i<=7;i++) c=1;

set_queen(1);
return 0;
}

Now This only prints 82 solutions, so 10 solutions are missing. In the
book the first 12 solutions a printed and they are the same as my first 12
solutions, so something else goes wrong. I also did the same program in
Common Lisp which works fine (and prints all 92 solutions). (This is
strange as Cl is much more different from Pascal than C++.)

Does, by any chance, anybody sees something which could go wrong (maybe
when the indeces become higher)?

Obviously, you can invest a lot of time here, so eveything I am asking for
is to look at the implementation of the Pascal array class and to have a
glance at the program.

TIA,

jb
 
J

jblazi

On Mon, 30 Aug 2004 16:50:34 +0200, jblazi wrote:

Sorry, but something went wrong with the copying. Here is the program:

#include "stdafx.h"

// Pascal like array with arbitrary indeces
class Array {
int *datum,start_index,end_index;

public:
Array(int s_index,int e_index) {start_index = s_index; end_index = e_index;datum = new int(end_index-start_index+1);}
int& operator [](int i) {return *(datum-start_index+i);}
};

// x : row of queen in the i-th coloumn
// a : no queen is in the the i-th row
// b : no queen is in the the i-th diagonal
// which has positive slope
// c : no queen is in the the i-th diagonal
// which has negative slope


Array a(1,8),x(1,8),b(2,16),c(-7,7);

void print_queens()
{
static int cnt = 0;

printf("%2d: ",++cnt);
for(int k=1;k<=8;k++)
printf("%4d",x[k]);
printf("\n");
}

void set_queen(int i)
{
int j;
for(j=1;j<=8;j++)
if (a[j] && b[i+j] && c[i-j]) {
x = j;
a[j] = b[i+j] = c[i-j] = 0;
if (i < 8) set_queen(i+1); else print_queens();
a[j] = b[i+j] = c[i-j] = 1;
}
}

int _tmain(int argc, _TCHAR* argv[])
{
for(int i=1;i<=8;i++) a=1;
for(int i=2;i<=16;i++) b=1;
for(int i=-7;i<=7;i++) c=1;

set_queen(1);
return 0;
}
 
K

Karl Heinz Buchegger

Now This only prints 82 solutions, so 10 solutions are missing. In the
book the first 12 solutions a printed and they are the same as my first 12
solutions, so something else goes wrong.

So fire up your debugger, figure out how you can manage to break the
program after the 12 solution has been generated and continue
single stepping your program until you can see how and why the
13-th solution comes up. Compare that with the posted 13-th solution
in the book, note the differences and deduce why there are differences.
(You might want to repeat this breaking in and single stepping to verify
your deductions, etc)

Welcome to the wonderful world of debugging. You will spend lots of time
with your debugger. So get familiar with it.
 
V

Victor Bazarov

jblazi said:
In the book "Algortims and Data Structures" by Wirth there is a program in
Pascal to compute all 92 solutions of the above mentioned problem. I tried
to translate his program into C++, the only small problem being that he
uses array with a starting index other than zero. Here is my solution:
[...]

// Pascal like array with arbitrary indeces
class Array {
int *datum,start_index,end_index;

public:
Array(int s_index,int e_index) {start_index = s_index; end_index = e_index;datum = new int(end_index-start_index+1);}

new int(blah);

allocates a _single_ int and initialises it to 'blah'. To allocate
an array of blah ints you need to do

new int[blah];

Victor
 
V

Victor Bazarov

jblazi said:
On Mon, 30 Aug 2004 16:50:34 +0200, jblazi wrote:

Sorry, but something went wrong with the copying. Here is the program:

#include "stdafx.h"

// Pascal like array with arbitrary indeces
class Array {
int *datum,start_index,end_index;

public:
Array(int s_index,int e_index) {start_index = s_index; end_index = e_index;datum = new int(end_index-start_index+1);}

You have the same problem here. 'datum' is a pointer to a single int, not
an array of ints.

Victor
 
K

Karl Heinz Buchegger

jblazi said:
On Mon, 30 Aug 2004 16:50:34 +0200, jblazi wrote:

Sorry, but something went wrong with the copying. Here is the program:

This prints 92 solutions on VC++
(after some modifications such as replacing stdafx.h
with stdio.h, _tmain with main)
 
K

Karl Heinz Buchegger

Karl said:
So fire up your debugger, figure out how you can manage to break the
program after the 12 solution has been generated and continue
single stepping your program until you can see how and why the
13-th solution comes up. Compare that with the posted 13-th solution
in the book,

Sorry. I missed that you said: *only* 12 solutions are printed
 
V

Victor Bazarov

Karl said:
This prints 92 solutions on VC++
(after some modifications such as replacing stdafx.h
with stdio.h, _tmain with main)

Wow. Undefined behaviour will never cease to amaze me...
 
J

jblazi

You have the same problem here. 'datum' is a pointer to a single int, not
an array of ints.
Victor

Thx. What a silly mistake! And it is then completely understandable that
it *may* run on some compilers *by* *chance*, as somebody pointed out in
the thread.

jb
 
K

Karl Heinz Buchegger

Victor said:
Wow. Undefined behaviour will never cease to amaze me...

Me too.
I totally missed the 'non-allocation', yet the thing run
as expected. I even stepped through with the debugger and
noticed nothing. Well. Not exactly. There were access violations
deep inside the printf code. After some examination I decided
to drop that problem for later (I always use the same VC
project for compiling newsgroup code, so it could be that there
were some strange project settings left from a previous program).
 

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

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top