python 如何实现N皇后问题的Sosic和Gu线性算法

zf2sa74q  于 2024-01-05  发布在  Python
关注(0)|答案(1)|浏览(134)

我正在尝试为n皇后问题实现Sosic和Gu算法-它提供了一个称为initial_search()的初始化阶段。
该算法首先在有限的尝试次数内将皇后分配到棋盘上的随机位置(由int(3.08 * n)迭代的循环控制)。对于每次皇后放置尝试,它使用partial_collision函数检查是否存在与先前放置的皇后的任何立即冲突。如果检测到冲突,算法会在不同的随机位置重新尝试放置,直到找到一个有效的放置。这一步的目的是在最小化初始冲突的同时将皇后分布在整个板上。我发现partial_collision()的实现存在问题:在文章中,他们说它应该花费O(1),但是我找不到一种方法来使用对角数组只检查左边的列(实际上函数total_collision()是O(1))。

  1. import random
  2. def queen_search(queens):
  3. while True:
  4. nd, pd = initialize_diagonal_arrays(len(queens))
  5. k = initial_search(queens, nd, pd)
  6. if len(queens) > 200:
  7. final_search(queens, k, nd, pd)
  8. break
  9. else:
  10. final_search_reduced(queens, k, nd, pd)
  11. if board_collision(queens) == 0:
  12. break
  13. def initial_search(queens, nd, pd):
  14. n = len(queens)
  15. queens[:] = list(range(n))
  16. update_diagonal_arrays(queens, nd, pd)
  17. j = 0
  18. # place queens without collisions
  19. for i in range(int(3.08 * n)):
  20. if j == n:
  21. break
  22. m = random.randint(j, n - 1)
  23. swap(queens, j, m, nd, pd)
  24. if partial_collision(queens, j) == 0:
  25. j += 1
  26. else:
  27. swap(queens, j, m, nd, pd)
  28. # place queens with possible collisions
  29. for i in range(j, n):
  30. m = random.randint(i, n - 1)
  31. swap(queens, i, m, nd, pd)
  32. # return the number of queens with possible collisions
  33. return n - j
  34. def final_search(queens, k, nd, pd):
  35. n = len(queens)
  36. it = 0
  37. for i in range(n - k, n):
  38. if total_collisions(queens, i, nd, pd) > 0:
  39. while it < 7000:
  40. j = random.randint(0, n - 1)
  41. swap(queens, i, j, nd, pd)
  42. b = (total_collisions(queens, i, nd, pd) > 0) or (total_collisions(queens, j, nd, pd) > 0)
  43. if b:
  44. swap(queens, i, j, nd, pd)
  45. it += 1
  46. else:
  47. break
  48. def final_search_reduced(queens, k, nd, pd):
  49. n = len(queens)
  50. for i in range(n - k, n):
  51. if total_collisions(queens, i, nd, pd) > 0:
  52. for j in range(n):
  53. swap(queens, i, j, nd, pd)
  54. b = (total_collisions(queens, i, nd, pd) > 0) or (total_collisions(queens, j, nd, pd) > 0)
  55. if b:
  56. swap(queens, i, j, nd, pd)
  57. else:
  58. break
  59. # auxiliary functions
  60. def initialize_diagonal_arrays(n):
  61. neg_diagonal = [0] * (2 * n - 1)
  62. pos_diagonal = [0] * (2 * n - 1)
  63. return neg_diagonal, pos_diagonal
  64. def update_diagonal_arrays(queens, neg_diagonal, pos_diagonal):
  65. n = len(queens)
  66. for i in range(len(queens)):
  67. neg_diagonal[i + queens[i]] += 1
  68. pos_diagonal[i - queens[i] + n - 1] += 1
  69. def swap(queens, a, b, neg_diagonal, pos_diagonal):
  70. original_a, original_b = queens[a], queens[b]
  71. queens[a], queens[b] = queens[b], queens[a]
  72. neg_diagonal[a + original_a] -= 1
  73. neg_diagonal[b + original_b] -= 1
  74. pos_diagonal[a - original_a + len(queens) - 1] -= 1
  75. pos_diagonal[b - original_b + len(queens) - 1] -= 1
  76. neg_diagonal[a + queens[a]] += 1
  77. neg_diagonal[b + queens[b]] += 1
  78. pos_diagonal[a - queens[a] + len(queens) - 1] += 1
  79. pos_diagonal[b - queens[b] + len(queens) - 1] += 1
  80. def partial_collision(queens, i):
  81. return sum(1 for j in range(i) if (i - j) == abs(queens[i] - queens[j]))
  82. def total_collisions(queens, i, neg_diagonal, pos_diagonal):
  83. n = len(queens)
  84. return neg_diagonal[i + queens[i]] + pos_diagonal[i - queens[i] + n - 1] - 2 # Exclude self-collision
  85. def board_collision(queens):
  86. return sum(partial_collision(queens, i) for i in range(len(queens)))

字符串

ff29svar

ff29svar1#

你不需要一个单独的partial_collision实现,因为你可以依赖total_collisions。后者将查看对角线上的占领,当你还没有放置所有皇后时也有效。
board_collisions中,我甚至会直接查看对角计数器,看看是否有任何计数器大于1。

相关问题