java中n皇后问题解的个数算法

vsmadaxz  于 2021-06-29  发布在  Java
关注(0)|答案(0)|浏览(200)

我试图实现下面的伪代码,但不是n皇后的解,我想打印出n皇后问题的解的个数,其中1<=n<=12。但是,我的输出与正确的输出不匹配。你们能帮我找出我的代码哪里做错了吗?
p、 教科书中的伪代码使用c++语言,但我的代码是java语言。
更新:在打印出前六个n-queens解决方案后(如ole v.v.所建议的,谢谢!),我发现在我的代码中的问题是一些解决方案被发现了两次,因此它们的计数被计算了两次。还在想办法解决这个问题吗
更新2:我在代码中发现了问题并指出了问题所在。非常感谢你的帮助。

  1. The pseudo code:
  2. Inputs: positive integer *n*.
  3. 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.
  4. void queens (index i) {
  5. index j;
  6. if ( promising(i) ) {
  7. if ( i == n ) {
  8. cout << col[1] through col[n];
  9. } else {
  10. for ( j = 1; j <= n; j++) {
  11. col[i + 1] = j;
  12. queens(i + 1);
  13. }
  14. }
  15. }
  16. }
  17. bool promising (index i) {
  18. index k;
  19. bool switch;
  20. k = 1;
  21. switch = true;
  22. while ( k < i && switch ) {
  23. if ( col[i] == col[k] || abs(col[i] - col[k]) == i-k ) {
  24. switch = false;
  25. }
  26. k++;
  27. }
  28. return switch;
  29. }

这是我的密码:

  1. class Queens {
  2. public static int n = 1, count = 0;
  3. public static int[] col;
  4. public static void main(String[] args) {
  5. int index = 0;
  6. while (n <= 12) {
  7. col = new int[n + 1];
  8. while (index <= n) { // just use the function once for each n
  9. queens(index); // i.e. just use queens(0);
  10. index++;
  11. }
  12. System.out.println("n = " + n + " # of solution(s) = " + count);
  13. count = 0;
  14. index = 0;
  15. n++;
  16. }
  17. }
  18. public static void queens(int i) {
  19. int index;
  20. if (promising(i)) {
  21. if (i == n) {
  22. count++;
  23. } else {
  24. for (index = 1; index <= n; index++) {
  25. col[i + 1] = index;
  26. queens(i + 1);
  27. }
  28. }
  29. }
  30. }
  31. static boolean promising(int i) {
  32. int index;
  33. boolean _switch;
  34. index = 1;
  35. _switch = true;
  36. while (index < i && _switch) {
  37. if (col[i] == col[index] || Math.abs(col[i] - col[index]) == (i - index)) {
  38. _switch = false;
  39. }
  40. index++;
  41. }
  42. return _switch;
  43. }
  44. }

下面是我从代码中得到的输出和正确的输出:

  1. My outputs:
  2. n = 1 # of solution(s) = 2
  3. n = 2 # of solution(s) = 0
  4. n = 3 # of solution(s) = 0
  5. n = 4 # of solution(s) = 2
  6. n = 5 # of solution(s) = 12
  7. n = 6 # of solution(s) = 4
  8. n = 7 # of solution(s) = 44
  9. n = 8 # of solution(s) = 96
  10. n = 9 # of solution(s) = 380
  11. n = 10 # of solution(s) = 788
  12. n = 11 # of solution(s) = 2776
  13. n = 12 # of solution(s) = 14700
  14. the correct outputs:
  15. n=1 # of solutions = 1
  16. n=2 # of solutions = 0
  17. n=3 # of solutions = 0
  18. n=4 # of solutions = 2
  19. n=5 # of solutions = 10
  20. n=6 # of solutions = 4
  21. n=7 # of solutions = 40
  22. n=8 # of solutions = 92
  23. n=9 # of solutions = 352
  24. n=10 # of solutions = 724
  25. n=11 # of solutions = 2680
  26. n=12 # of solutions = 14200

前六种解决方案:

  1. 1
  2. 1 // counted twice!
  3. n = 1 # of solution(s) = 2
  4. n = 2 # of solution(s) = 0
  5. n = 3 # of solution(s) = 0
  6. 2 4 1 3
  7. 3 1 4 2
  8. n = 4 # of solution(s) = 2
  9. 1 3 5 2 4
  10. 1 4 2 5 3
  11. 2 4 1 3 5
  12. 2 5 3 1 4
  13. 3 1 4 2 5
  14. 3 5 2 4 1
  15. 4 1 3 5 2
  16. 4 2 5 3 1
  17. 5 2 4 1 3 //
  18. 5 3 1 4 2 //
  19. 5 2 4 1 3 // counted twice!
  20. 5 3 1 4 2 // counted twice!
  21. n = 5 # of solution(s) = 12
  22. 2 4 6 1 3 5
  23. 3 6 2 5 1 4
  24. 4 1 5 2 6 3
  25. 5 3 1 6 4 2
  26. n = 6 # of solution(s) = 4

暂无答案!

目前还没有任何答案,快来回答吧!

相关问题