我试图实现下面的伪代码,但不是n皇后的解,我想打印出n皇后问题的解的个数,其中1<=n<=12。但是,我的输出与正确的输出不匹配。你们能帮我找出我的代码哪里做错了吗?
p、 教科书中的伪代码使用c++语言,但我的代码是java语言。
更新:在打印出前六个n-queens解决方案后(如ole v.v.所建议的,谢谢!),我发现在我的代码中的问题是一些解决方案被发现了两次,因此它们的计数被计算了两次。还在想办法解决这个问题吗
更新2:我在代码中发现了问题并指出了问题所在。非常感谢你的帮助。
The pseudo code:
Inputs: positive integer *n*.
Outputs: all possible ways *n* queens can be placed on an *n x n* chessboard so that no two queens threaten each other. Each output consists of an array of integers *col* indexed from 1 to n, where *col[i]* is the column where the queen in the *i*th row is placed.
void queens (index i) {
index j;
if ( promising(i) ) {
if ( i == n ) {
cout << col[1] through col[n];
} else {
for ( j = 1; j <= n; j++) {
col[i + 1] = j;
queens(i + 1);
}
}
}
}
bool promising (index i) {
index k;
bool switch;
k = 1;
switch = true;
while ( k < i && switch ) {
if ( col[i] == col[k] || abs(col[i] - col[k]) == i-k ) {
switch = false;
}
k++;
}
return switch;
}
这是我的密码:
class Queens {
public static int n = 1, count = 0;
public static int[] col;
public static void main(String[] args) {
int index = 0;
while (n <= 12) {
col = new int[n + 1];
while (index <= n) { // just use the function once for each n
queens(index); // i.e. just use queens(0);
index++;
}
System.out.println("n = " + n + " # of solution(s) = " + count);
count = 0;
index = 0;
n++;
}
}
public static void queens(int i) {
int index;
if (promising(i)) {
if (i == n) {
count++;
} else {
for (index = 1; index <= n; index++) {
col[i + 1] = index;
queens(i + 1);
}
}
}
}
static boolean promising(int i) {
int index;
boolean _switch;
index = 1;
_switch = true;
while (index < i && _switch) {
if (col[i] == col[index] || Math.abs(col[i] - col[index]) == (i - index)) {
_switch = false;
}
index++;
}
return _switch;
}
}
下面是我从代码中得到的输出和正确的输出:
My outputs:
n = 1 # of solution(s) = 2
n = 2 # of solution(s) = 0
n = 3 # of solution(s) = 0
n = 4 # of solution(s) = 2
n = 5 # of solution(s) = 12
n = 6 # of solution(s) = 4
n = 7 # of solution(s) = 44
n = 8 # of solution(s) = 96
n = 9 # of solution(s) = 380
n = 10 # of solution(s) = 788
n = 11 # of solution(s) = 2776
n = 12 # of solution(s) = 14700
the correct outputs:
n=1 # of solutions = 1
n=2 # of solutions = 0
n=3 # of solutions = 0
n=4 # of solutions = 2
n=5 # of solutions = 10
n=6 # of solutions = 4
n=7 # of solutions = 40
n=8 # of solutions = 92
n=9 # of solutions = 352
n=10 # of solutions = 724
n=11 # of solutions = 2680
n=12 # of solutions = 14200
前六种解决方案:
1
1 // counted twice!
n = 1 # of solution(s) = 2
n = 2 # of solution(s) = 0
n = 3 # of solution(s) = 0
2 4 1 3
3 1 4 2
n = 4 # of solution(s) = 2
1 3 5 2 4
1 4 2 5 3
2 4 1 3 5
2 5 3 1 4
3 1 4 2 5
3 5 2 4 1
4 1 3 5 2
4 2 5 3 1
5 2 4 1 3 //
5 3 1 4 2 //
5 2 4 1 3 // counted twice!
5 3 1 4 2 // counted twice!
n = 5 # of solution(s) = 12
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
5 3 1 6 4 2
n = 6 # of solution(s) = 4
暂无答案!
目前还没有任何答案,快来回答吧!