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
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