八个皇后问题 [英] The eight queens problem
问题描述
在Algortims and Data Structures一书中。通过Wirth，有一个程序在
Pascal中计算上述问题的所有92个解决方案。我尝试将
转换成C ++，唯一的小问题就是他使用了一个非零的起始索引的数组。这是我的解决方案：
// Pascal类似于具有任意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 [i]：行在第i个coloumn的女王
// a [i]：没有女王在第i行
// b [i]：没有女王是在第i个对角线上
//有正斜率
// c [i]：没有女王在第i个对角线上
//具有负斜率
数组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 [ij]）{
x [i] = j;
a [j] = b [i + j] = c [ij] = 0;
if（i <8）set_queen（i + 1）; else print_queens（）;
a [j] = b [i + j] = c [ij] = 1;
}
}
int _tmain（int argc，_TCHAR * argv []）
{
for（int i = 1; i< = 8; i ++）a [i] = 1;
for（int i = 2; i< = 16; i ++）b [i] = 1;
for（ int i = -7; i< = 7; i ++）c [i] = 1;
set_queen（1）;
返回0;
}
现在这只打印82个解决方案，因此缺少10个解决方案。在
书中，前12个解决方案打印出来，它们与我的前12个解决方案相同，所以出现了其他问题。我也在
Common Lisp中做了相同的程序，它工作正常（并打印所有92个解决方案）。 （这是很奇怪的，因为Cl与Pascal的区别远远超过C ++。）
无论如何，任何人都会看到可能出错的东西（也许
当空白变得更高时）？
显然，你可以在这里投入大量时间，所以我要求的东西是
是看看Pascal数组类的实现，并且对程序有一个
。
TIA，
jb
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[i] : row of queen in the i-th coloumn
// a[i] : no queen is in the the i-th row
// b[i] : no queen is in the the i-th diagonal
// which has positive slope
// c[i] : 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[i] = 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[i]=1;
for(int i=2;i<=16;i++) b[i]=1;
for(int i=-7;i<=7;i++) c[i]=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
推荐答案
2004年8月30日星期一16:50:34 + 0200，jblazi写道：
对不起，但复制出了问题。这是程序：
#include" stdafx.h"
//具有任意权限的Pascal类数据
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 [i]：行在第i个coloumn的女王
// a [i]：没有女王在第i行
// b [i]：没有女王是在第i个对角线上
//有正斜率
// c [i]：没有女王在第i个对角线上
//具有负斜率
数组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 [ij]）{
x [i] = j;
a [j] = b [i + j] = c [ij] = 0;
if（i <8）set_queen（i + 1）; else print_queens（）;
a [j] = b [i + j] = c [ij] = 1;
}
}
int _tmain（int argc，_TCHAR * argv []）
{
for（int i = 1; i< = 8; i ++）a [i] = 1;
for（int i = 2; i< = 16; i ++）b [i] = 1;
for（ int i = -7; i< = 7; i ++）c [i] = 1;
set_queen（1）;
返回0;
}
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[i] : row of queen in the i-th coloumn
// a[i] : no queen is in the the i-th row
// b[i] : no queen is in the the i-th diagonal
// which has positive slope
// c[i] : 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[i] = 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[i]=1;
for(int i=2;i<=16;i++) b[i]=1;
for(int i=-7;i<=7;i++) c[i]=1;
set_queen(1);
return 0;
}
jblazi写道：
现在这只打印82个解决方案，因此缺少10个解决方案。在
预订的前12个解决方案中，它们与我的前12个解决方案相同，所以出现了其他问题。
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.
所以启动你的调试器，弄清楚如何在12个解决方案生成之后设法打破
程序并继续
单步执行程序，直到你看到如何以及为什么
第13个解决方案出现了。与书中发布的第13个解决方案
相比较，请注意差异并推断出存在差异的原因。
（你可能想重复这个突破和单一步进验证
你的扣除等等）
欢迎来到精彩的调试世界。您将花费大量时间和调试器一起使用
。所以要熟悉它。
-
Karl Heinz Buchegger
kb ****** @ gascad.at
jblazi写道：
在书中; Algortims和数据结构通过Wirth，有一个程序在Pascal中计算上述问题的所有92个解决方案。我尝试将他的程序翻译成C ++，唯一的小问题是他使用的数组的起始索引不是零。这是我的解决方案：
[...]
// Pascal类似于具有任意indeces的数组
class Array {
int * datum，start_index，end_index; <公共：
数组（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）;
分配_single_ int并将其初始化为''blah''。分配
你需要做的一系列的in
new int [blah];
[...]
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
Victor
这篇关于八个皇后问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
