设为首页收藏本站CAD论坛CAD教程CAD下载明经币充值
切换到宽版

明经CAD社区

 找回密码
 注册

QQ登录

只需一步，快速开始

搜索
明经CAD社区»社区 › 开发篇 › AutoLISP/Visual LISP 编程技术 › [风之影][Lisp大挑战第四季]皇后
12下一页
返回列表 发新帖
查看: 5952|回复: 18

[【风之影】] [风之影][Lisp大挑战第四季]皇后

  [复制链接]
cabinsummer
发表于 2011-11-25 19:51 | 显示全部楼层 |阅读模式
LISP大挑战已经发布过三季了，第一季圆周率受到大家的热捧，第二季光路计算也吸引了不少人的关注。本打算将八皇后作为第三季的，临时决定启用了个高难度的完美正方形，现在估计是很少人挑战第三季了。这次将八皇后问题作为第四季大挑战，应该能吸引不少高手参与，这次希望能见到高效率的算法。
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。下图是八皇后问题的一个解：
八皇后问题一共有 92 个互不相同的解。如果将旋转和对称的解归为一种的话，则一共有12个独立解。很奇怪吧？为什么不是12×8＝96个解。
本期LISP大挑战就是求出八皇后问题的12个独立解。
风为什么不挑战92个互不相同的解而要挑战独立解？就是因为判断旋转和对称也需要有效率的算法。
由于八皇后问题的解法很多，大家可以到网上查找其它语言的算法。本次大挑战的优胜者将是LISP程序效率最高的那位。
旋转, 如何, 国际象棋

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？注册

x
"觉得好，就打赏"
打赏
还没有人打赏，支持一下

相关帖子
回复

使用道具 举报

fanpaulm
发表于 2017-8-3 10:47 | 显示全部楼层
飞诗(fsxm) 发表于 2011-11-29 23:56
补上皇后去重计算！做一个简单的优化，速度非常快了哦！
去重模块引用的是qjchen的代码，谢了！并针对性做 ...

飞诗太牛了！
回复 支持 反对

使用道具 举报

fanpaulm
发表于 2017-8-3 10:44 | 显示全部楼层
xianaihua 发表于 2011-11-29 19:24
皇后问题完整版

楼主很给力！
回复 支持 反对

使用道具 举报

cabinsummer
 楼主| 发表于 2011-11-25 22:26 | 显示全部楼层
先贴一个计算92个不同解的，运算速度超快，92个解不到一秒钟
  1. (defun c:queen(/ QP Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8)
  2.   (setq QP '(1 2 3 4 5 6 7 8))
  3.   (foreach Q1 QP
  4.     (foreach Q2 QP
  5.       (if
  6.         (and (/= Q1 Q2)(/= (+ Q1 1) Q2)(/= (- Q1 1) Q2))
  7.         (foreach Q3 QP
  8.           (if
  9.             (and
  10.               (/= Q1 Q3)(/= (+ Q1 2) Q3)(/= (- Q1 2) Q3)
  11.               (/= Q2 Q3)(/= (+ Q2 1) Q3)(/= (- Q2 1) Q3)
  12.             )
  13.             (foreach Q4 QP
  14.               (if
  15.                 (and
  16.                   (/= Q1 Q4)(/= (+ Q1 3) Q4)(/= (- Q1 3) Q4)
  17.                   (/= Q2 Q4)(/= (+ Q2 2) Q4)(/= (- Q2 2) Q4)
  18.                   (/= Q3 Q4)(/= (+ Q3 1) Q4)(/= (- Q3 1) Q4)
  19.                 )
  20.                 (foreach Q5 QP
  21.                   (if
  22.                     (and
  23.                       (/= Q1 Q5)(/= (+ Q1 4) Q5)(/= (- Q1 4) Q5)
  24.                       (/= Q2 Q5)(/= (+ Q2 3) Q5)(/= (- Q2 3) Q5)
  25.                       (/= Q3 Q5)(/= (+ Q3 2) Q5)(/= (- Q3 2) Q5)
  26.                       (/= Q4 Q5)(/= (+ Q4 1) Q5)(/= (- Q4 1) Q5)
  27.                     )
  28.                     (foreach Q6 QP
  29.                       (if
  30.                         (and
  31.                           (/= Q1 Q6)(/= (+ Q1 5) Q6)(/= (- Q1 5) Q6)
  32.                           (/= Q2 Q6)(/= (+ Q2 4) Q6)(/= (- Q2 4) Q6)
  33.                           (/= Q3 Q6)(/= (+ Q3 3) Q6)(/= (- Q3 3) Q6)
  34.                           (/= Q4 Q6)(/= (+ Q4 2) Q6)(/= (- Q4 2) Q6)
  35.                           (/= Q5 Q6)(/= (+ Q5 1) Q6)(/= (- Q5 1) Q6)
  36.                         )
  37.                         (foreach Q7 QP
  38.                           (if
  39.                             (and
  40.                               (/= Q1 Q7)(/= (+ Q1 6) Q7)(/= (- Q1 6) Q7)
  41.                               (/= Q2 Q7)(/= (+ Q2 5) Q7)(/= (- Q2 5) Q7)
  42.                               (/= Q3 Q7)(/= (+ Q3 4) Q7)(/= (- Q3 4) Q7)
  43.                               (/= Q4 Q7)(/= (+ Q4 3) Q7)(/= (- Q4 3) Q7)
  44.                               (/= Q5 Q7)(/= (+ Q5 2) Q7)(/= (- Q5 2) Q7)
  45.                               (/= Q6 Q7)(/= (+ Q6 1) Q7)(/= (- Q6 1) Q7)
  46.                             )
  47.                             (foreach Q8 QP
  48.                               (if
  49.                                 (and
  50.                                   (/= Q1 Q8)(/= (+ Q1 7) Q8)(/= (- Q1 7) Q8)
  51.                                   (/= Q2 Q8)(/= (+ Q2 6) Q8)(/= (- Q2 6) Q8)
  52.                                   (/= Q3 Q8)(/= (+ Q3 5) Q8)(/= (- Q3 5) Q8)
  53.                                   (/= Q4 Q8)(/= (+ Q4 4) Q8)(/= (- Q4 4) Q8)
  54.                                   (/= Q5 Q8)(/= (+ Q5 3) Q8)(/= (- Q5 3) Q8)
  55.                                   (/= Q6 Q8)(/= (+ Q6 2) Q8)(/= (- Q6 2) Q8)
  56.                                   (/= Q7 Q8)(/= (+ Q7 1) Q8)(/= (- Q7 1) Q8)
  57.                                 )
  58.                                 (print (list Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8))
  59.   ) ) ) ) ) ) ) ) ) ) ) ) ) ) )
  60.   (princ)
  61. )

以下是92个不同解，独立解要从这92个解中排除同类的，caoyin的表中删除指定项的挑战在此重现。
  1. (1 5 8 6 3 7 2 4)
  2. (1 6 8 3 7 4 2 5)
  3. (1 7 4 6 8 2 5 3)
  4. (1 7 5 8 2 4 6 3)
  5. (2 4 6 8 3 1 7 5)
  6. (2 5 7 1 3 8 6 4)
  7. (2 5 7 4 1 8 6 3)
  8. (2 6 1 7 4 8 3 5)
  9. (2 6 8 3 1 4 7 5)
  10. (2 7 3 6 8 5 1 4)
  11. (2 7 5 8 1 4 6 3)
  12. (2 8 6 1 3 5 7 4)
  13. (3 1 7 5 8 2 4 6)
  14. (3 5 2 8 1 7 4 6)
  15. (3 5 2 8 6 4 7 1)
  16. (3 5 7 1 4 2 8 6)
  17. (3 5 8 4 1 7 2 6)
  18. (3 6 2 5 8 1 7 4)
  19. (3 6 2 7 1 4 8 5)
  20. (3 6 2 7 5 1 8 4)
  21. (3 6 4 1 8 5 7 2)
  22. (3 6 4 2 8 5 7 1)
  23. (3 6 8 1 4 7 5 2)
  24. (3 6 8 1 5 7 2 4)
  25. (3 6 8 2 4 1 7 5)
  26. (3 7 2 8 5 1 4 6)
  27. (3 7 2 8 6 4 1 5)
  28. (3 8 4 7 1 6 2 5)
  29. (4 1 5 8 2 7 3 6)
  30. (4 1 5 8 6 3 7 2)
  31. (4 2 5 8 6 1 3 7)
  32. (4 2 7 3 6 8 1 5)
  33. (4 2 7 3 6 8 5 1)
  34. (4 2 7 5 1 8 6 3)
  35. (4 2 8 5 7 1 3 6)
  36. (4 2 8 6 1 3 5 7)
  37. (4 6 1 5 2 8 3 7)
  38. (4 6 8 2 7 1 3 5)
  39. (4 6 8 3 1 7 5 2)
  40. (4 7 1 8 5 2 6 3)
  41. (4 7 3 8 2 5 1 6)
  42. (4 7 5 2 6 1 3 8)
  43. (4 7 5 3 1 6 8 2)
  44. (4 8 1 3 6 2 7 5)
  45. (4 8 1 5 7 2 6 3)
  46. (4 8 5 3 1 7 2 6)
  47. (5 1 4 6 8 2 7 3)
  48. (5 1 8 4 2 7 3 6)
  49. (5 1 8 6 3 7 2 4)
  50. (5 2 4 6 8 3 1 7)
  51. (5 2 4 7 3 8 6 1)
  52. (5 2 6 1 7 4 8 3)
  53. (5 2 8 1 4 7 3 6)
  54. (5 3 1 6 8 2 4 7)
  55. (5 3 1 7 2 8 6 4)
  56. (5 3 8 4 7 1 6 2)
  57. (5 7 1 3 8 6 4 2)
  58. (5 7 1 4 2 8 6 3)
  59. (5 7 2 4 8 1 3 6)
  60. (5 7 2 6 3 1 4 8)
  61. (5 7 2 6 3 1 8 4)
  62. (5 7 4 1 3 8 6 2)
  63. (5 8 4 1 3 6 2 7)
  64. (5 8 4 1 7 2 6 3)
  65. (6 1 5 2 8 3 7 4)
  66. (6 2 7 1 3 5 8 4)
  67. (6 2 7 1 4 8 5 3)
  68. (6 3 1 7 5 8 2 4)
  69. (6 3 1 8 4 2 7 5)
  70. (6 3 1 8 5 2 4 7)
  71. (6 3 5 7 1 4 2 8)
  72. (6 3 5 8 1 4 2 7)
  73. (6 3 7 2 4 8 1 5)
  74. (6 3 7 2 8 5 1 4)
  75. (6 3 7 4 1 8 2 5)
  76. (6 4 1 5 8 2 7 3)
  77. (6 4 2 8 5 7 1 3)
  78. (6 4 7 1 3 5 2 8)
  79. (6 4 7 1 8 2 5 3)
  80. (6 8 2 4 1 7 5 3)
  81. (7 1 3 8 6 4 2 5)
  82. (7 2 4 1 8 5 3 6)
  83. (7 2 6 3 1 4 8 5)
  84. (7 3 1 6 8 5 2 4)
  85. (7 3 8 2 5 1 6 4)
  86. (7 4 2 5 8 1 3 6)
  87. (7 4 2 8 6 1 3 5)
  88. (7 5 3 1 6 8 2 4)
  89. (8 2 4 1 7 5 3 6)
  90. (8 2 5 3 1 7 4 6)
  91. (8 3 1 6 2 5 7 4)
  92. (8 4 1 3 6 2 7 5)
回复 支持 反对

使用道具 举报

cabinsummer
 楼主| 发表于 2011-11-26 04:49 | 显示全部楼层
忽然发现论坛代码的着色有问题。看上面代码中有括号不是红色。

点评

mccad
有些代码没有找到识别着色的关键字，所以也就不能着色，你需要手动选择  发表于 2011-11-26 21:56
回复 支持 反对

使用道具 举报

我的生活
发表于 2011-11-26 10:12 | 显示全部楼层
图书编辑太高了
回复 支持 反对

使用道具 举报

cabinsummer
 楼主| 发表于 2011-11-26 16:23 | 显示全部楼层
12个独立解出来了。不过还有一点点疑问。
  1. ;;;逆时针旋转90度
  2. (defun RT90(elist / n temp x elst)
  3.   (setq n 1 temp nil)
  4.   (foreach x elist
  5.     (setq temp (append temp (list (cons (- 9 x) n))) n (1+ n))
  6.   )
  7.   (setq temp (vl-sort temp (function (lambda (x y)(< (car x)(car y))))))
  8.   (setq elst nil)
  9.   (foreach x temp
  10.     (setq elst (append elst (list (cdr x))))
  11.   )
  12.   elst
  13. )
  14. ;;;水平镜像
  15. (defun MHOR(elist)
  16.   (reverse elist)
  17. )
  18. ;;;垂直镜像
  19. (defun MVER(elist / x)
  20.   (mapcar (function (lambda (x)(- 9 x))) elist)
  21. )
  22. ;;;左上右下镜像
  23. (defun M135(elist / n temp x elst)
  24.   (setq n 1 temp nil)
  25.   (foreach x elist
  26.     (setq temp (append temp (list (cons x n))) n (1+ n))
  27.   )
  28.   (setq temp (vl-sort temp (function (lambda (x y)(< (car x)(car y))))))
  29.   (setq elst nil)
  30.   (foreach x temp
  31.     (setq elst (append elst (list (cdr x))))
  32.   )
  33.   elst
  34. )
  35. ;;;左下右上镜像
  36. (defun M045(elist / n temp x elst)
  37.   (setq n 1 temp nil)
  38.   (foreach x elist
  39.     (setq temp (append temp (list (cons (- 9 x) (- 9 n)))) n (1+ n))
  40.   )
  41.   (setq temp (vl-sort temp (function (lambda (x y)(< (car x)(car y))))))
  42.   (setq elst nil)
  43.   (foreach x temp
  44.     (setq elst (append elst (list (cdr x))))
  45.   )
  46.   elst
  47. )
  48. (defun c:queen(/ QP Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8
  49.                  elist elst n
  50.                  list00 list01 list02 list03 list04
  51.                  list05 list06 list07 list08 list09
  52.                  list10 list11 list12 list13 list14
  53.                  list15 list16 list17 list18 list19
  54.               )
  55.   (setq QP '(1 2 3 4 5 6 7 8))
  56.   (foreach Q1 QP
  57.     (foreach Q2 QP
  58.       (if
  59.         (and (/= Q1 Q2)(/= (+ Q1 1) Q2)(/= (- Q1 1) Q2))
  60.         (foreach Q3 QP
  61.           (if
  62.             (and
  63.               (/= Q1 Q3)(/= (+ Q1 2) Q3)(/= (- Q1 2) Q3)
  64.               (/= Q2 Q3)(/= (+ Q2 1) Q3)(/= (- Q2 1) Q3)
  65.             )
  66.             (foreach Q4 QP
  67.               (if
  68.                 (and
  69.                   (/= Q1 Q4)(/= (+ Q1 3) Q4)(/= (- Q1 3) Q4)
  70.                   (/= Q2 Q4)(/= (+ Q2 2) Q4)(/= (- Q2 2) Q4)
  71.                   (/= Q3 Q4)(/= (+ Q3 1) Q4)(/= (- Q3 1) Q4)
  72.                 )
  73.                 (foreach Q5 QP
  74.                   (if
  75.                     (and
  76.                       (/= Q1 Q5)(/= (+ Q1 4) Q5)(/= (- Q1 4) Q5)
  77.                       (/= Q2 Q5)(/= (+ Q2 3) Q5)(/= (- Q2 3) Q5)
  78.                       (/= Q3 Q5)(/= (+ Q3 2) Q5)(/= (- Q3 2) Q5)
  79.                       (/= Q4 Q5)(/= (+ Q4 1) Q5)(/= (- Q4 1) Q5)
  80.                     )
  81.                     (foreach Q6 QP
  82.                       (if
  83.                         (and
  84.                           (/= Q1 Q6)(/= (+ Q1 5) Q6)(/= (- Q1 5) Q6)
  85.                           (/= Q2 Q6)(/= (+ Q2 4) Q6)(/= (- Q2 4) Q6)
  86.                           (/= Q3 Q6)(/= (+ Q3 3) Q6)(/= (- Q3 3) Q6)
  87.                           (/= Q4 Q6)(/= (+ Q4 2) Q6)(/= (- Q4 2) Q6)
  88.                           (/= Q5 Q6)(/= (+ Q5 1) Q6)(/= (- Q5 1) Q6)
  89.                         )
  90.                         (foreach Q7 QP
  91.                           (if
  92.                             (and
  93.                               (/= Q1 Q7)(/= (+ Q1 6) Q7)(/= (- Q1 6) Q7)
  94.                               (/= Q2 Q7)(/= (+ Q2 5) Q7)(/= (- Q2 5) Q7)
  95.                               (/= Q3 Q7)(/= (+ Q3 4) Q7)(/= (- Q3 4) Q7)
  96.                               (/= Q4 Q7)(/= (+ Q4 3) Q7)(/= (- Q4 3) Q7)
  97.                               (/= Q5 Q7)(/= (+ Q5 2) Q7)(/= (- Q5 2) Q7)
  98.                               (/= Q6 Q7)(/= (+ Q6 1) Q7)(/= (- Q6 1) Q7)
  99.                             )
  100.                             (foreach Q8 QP
  101.                               (if
  102.                                 (and
  103.                                   (/= Q1 Q8)(/= (+ Q1 7) Q8)(/= (- Q1 7) Q8)
  104.                                   (/= Q2 Q8)(/= (+ Q2 6) Q8)(/= (- Q2 6) Q8)
  105.                                   (/= Q3 Q8)(/= (+ Q3 5) Q8)(/= (- Q3 5) Q8)
  106.                                   (/= Q4 Q8)(/= (+ Q4 4) Q8)(/= (- Q4 4) Q8)
  107.                                   (/= Q5 Q8)(/= (+ Q5 3) Q8)(/= (- Q5 3) Q8)
  108.                                   (/= Q6 Q8)(/= (+ Q6 2) Q8)(/= (- Q6 2) Q8)
  109.                                   (/= Q7 Q8)(/= (+ Q7 1) Q8)(/= (- Q7 1) Q8)
  110.                                 )
  111.                                 (setq elist (append elist (list (list Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8))))
  112.   ) ) ) ) ) ) ) ) ) ) ) ) ) ) )
  113.   (setq n 0)
  114.   (while (setq list00 (nth n elist))
  115.     (setq list01 (MHOR list00))(if (not (eq list00 list01))(setq elist (vl-remove list01 elist)))
  116.     (setq list02 (MVER list00))(if (not (eq list00 list02))(setq elist (vl-remove list02 elist)))
  117.     (setq list03 (M135 list00))(if (not (eq list00 list03))(setq elist (vl-remove list03 elist)))
  118.     (setq list04 (M045 list00))(if (not (eq list00 list04))(setq elist (vl-remove list04 elist)))
  119.     (setq list05 (RT90 list00))(if (not (eq list00 list05))(setq elist (vl-remove list05 elist)))
  120.     (setq list06 (MHOR list05))(if (not (eq list00 list06))(setq elist (vl-remove list06 elist)))
  121.     (setq list07 (MVER list05))(if (not (eq list00 list07))(setq elist (vl-remove list07 elist)))
  122.     (setq list08 (M135 list05))(if (not (eq list00 list08))(setq elist (vl-remove list08 elist)))
  123.     (setq list09 (M045 list05))(if (not (eq list00 list09))(setq elist (vl-remove list09 elist)))
  124.     (setq list10 (RT90 list05))(if (not (eq list00 list10))(setq elist (vl-remove list10 elist)))
  125.     (setq list11 (MHOR list10))(if (not (eq list00 list11))(setq elist (vl-remove list11 elist)))
  126.     (setq list12 (MVER list10))(if (not (eq list00 list12))(setq elist (vl-remove list12 elist)))
  127.     (setq list13 (M135 list10))(if (not (eq list00 list13))(setq elist (vl-remove list13 elist)))
  128.     (setq list14 (M045 list10))(if (not (eq list00 list14))(setq elist (vl-remove list14 elist)))
  129.     (setq list15 (RT90 list10))(if (not (eq list00 list15))(setq elist (vl-remove list15 elist)))
  130.     (setq list16 (MHOR list15))(if (not (eq list00 list16))(setq elist (vl-remove list16 elist)))
  131.     (setq list17 (MVER list15))(if (not (eq list00 list17))(setq elist (vl-remove list17 elist)))
  132.     (setq list18 (M135 list15))(if (not (eq list00 list18))(setq elist (vl-remove list18 elist)))
  133.     (setq list19 (M045 list15))(if (not (eq list00 list19))(setq elist (vl-remove list19 elist)))
  134.     (setq n (1+ n))
  135.     (setq elst (append elst (list list00)))
  136.   )
  137.   elst
  138. )

  1. (1 5 8 6 3 7 2 4)
  2. (1 6 8 3 7 4 2 5)
  3. (2 4 6 8 3 1 7 5)
  4. (2 5 7 1 3 8 6 4)
  5. (2 5 7 4 1 8 6 3)
  6. (2 6 1 7 4 8 3 5)
  7. (2 6 8 3 1 4 7 5)
  8. (2 7 3 6 8 5 1 4)
  9. (2 7 5 8 1 4 6 3)
  10. (3 5 2 8 1 7 4 6)
  11. (3 6 2 5 8 1 7 4)
  12. (3 6 8 2 4 1 7 5)

点评

xianaihua
cabinsummer 的最后一组数值好像有点问题（随便说，没仔细验证）  发表于 2011-11-29 19:30
回复 支持 反对

使用道具 举报

cabinsummer
 楼主| 发表于 2011-11-26 16:29 | 显示全部楼层
本帖最后由 cabinsummer 于 2011-11-28 19:50 编辑

　　在求十二个独立解时有一点疑问。
　　思路是在92个不同解组成的表中逐一提取一个表，将提取的表进行各种镜像和旋转，以及旋转后的镜像，再将镜像和旋转的表从92个解中一一去除。奇怪的是，如果输出结果是从92个解的表中去除的，结果就是11个，前一帖子的第10个解没了。风琢磨了一下午也没琢磨个所以然来，因为表太长了，难以调试。所以采用另组新表的方式输出12个独立解。大侠们可以帮我看看到底哪里出问题了，还是算法本身就不完善？
回复 支持 反对

使用道具 举报

qjchen
发表于 2011-11-27 00:40 | 显示全部楼层
:) 先写一个所有解的，可以不止8阶，用的是回溯法，8阶还是速度挺快。
不过到11阶以上，速度就比较慢了
后面再来修改为12解的

  3. ;;;;八皇后法的回溯法解法
  4. (defun q:queen (n lst / i)
  5.   (setq i 0)
  6.   (repeat qn
  7.     (if (not (q:queen:check i lst))
  8.       (if (= n (1- qn))
  9.           (setq final (cons (reverse (cons i lst)) final))
  10.           (q:queen (1+ n) (cons i lst)))
  11.     )
  12.     (setq i (1+ i))
  13.   )
  14. )
  15. ;;;;八皇后的位置检验
  16. (defun q:queen:check (n1 lst1 / res x j)
  17.   (setq j 1)
  18.   (foreach x lst1
  19.     (setq res (append res (list (- x j) x (+ x j)))j (1+ j))
  20.   )
  21.   (member n1 (vl-sort res '<))
  22. )
  23. ;;;;主程序
  24. (defun c:test(/ final qn)
  25.   (setq qn 8)
  26.   (q:queen 0 nil)
  27.   (foreach x (reverse final) (princ "\n") (princ x))
  28.   (princ)
  29. )
  30. (princ "\n By qjchen@gmail.com, 八皇后问题，命令test")
  31. (princ)

评分

参与人数 1明经币 +1 收起 理由
cabinsummer + 1 很给力!

查看全部评分

回复 支持 反对

使用道具 举报

qjchen
发表于 2011-11-27 09:09 | 显示全部楼层
:) 修改了一个是属于12解的

  3. ;;;;八皇后法的回溯法解法
  4. (defun q:queen (n lst / i)
  5.   (setq i 0)
  6.   (repeat qn
  7.     (if (not (q:queen:check i lst))
  8.       (if (= n (1- qn))
  9.           (setq final (cons (reverse (cons i lst)) final))
  10.           (q:queen (1+ n) (cons i lst)))
  11.     )
  12.     (setq i (1+ i))
  13.   )
  14. )
  15. ;;;;八皇后的位置检验
  16. (defun q:queen:check (n1 lst1 / res x j)
  17.   (setq j 1)
  18.   (foreach x lst1
  19.     (setq res (append res (list (- x j) x (+ x j)))j (1+ j))
  20.   )
  21.   (member n1 (vl-sort res '<))
  22. )
  23. ;;;;表的转置
  24. (defun q:queen:inv(lst / res)
  25. (setq i 0)
  26. (repeat (length lst) (setq res (cons (vl-position i lst) res) i (1+ i)))
  27. (reverse res)
  28. )
  29. ;;;;表的y轴翻转
  30. (defun q:queen:mirrory(lst)
  31. (mapcar '(lambda(x) (- (length lst) 1 x)) lst)
  32. )
  33. ;;;;表的x轴翻转
  34. (defun q:queen:mirrorx(lst) (reverse lst))
  35. ;;;;表的90度转置
  36. (defun q:queen:rot90(lst) (q:queen:mirrory (q:queen:inv lst)))
  37. ;;;;所有9种同构的情况
  38. (defun q:queen:allsame(lst / res l1 l2 l3)
  39. (setq l1 (q:queen:rot90 lst) res (cons (q:queen:mirrorx l1) (cons (q:queen:mirrory l1) (cons l1 res))))
  40. (setq l2 (q:queen:rot90 l1) res (cons (q:queen:mirrorx l2) (cons (q:queen:mirrory l2) (cons l2 res))))
  41. (setq l3 (q:queen:rot90 l2) res (cons (q:queen:mirrorx l1) (cons (q:queen:mirrory l3) (cons l3 res))))
  42. res
  43. )
  44. ;;;;处理8皇后解中的重复情况
  45. (defun q:queen:removeallsame(lst / res a1)
  46. (while (car lst)
  47.    (setq res (cons (setq a1 (car lst)) res)
  48.          lst (q:list:removebfroma (cdr lst) (q:queen:allsame a1)))
  49. )
  50. res
  51. )
  52. ;;;;把lsta中有lstb的元素删除
  53. (defun q:list:removebfroma(lsta lstb / x)
  54. (foreach x lstb (setq lsta (vl-remove x lsta)))
  55. )
  56. ;;;;主程序
  57. (defun c:test(/ final qn)
  58.   (setq qn (getint "\n 请输入皇后阶数(建议小于或等于8):"))
  59.   (if (not qn) (setq qn 8))
  60.   (q:queen 0 nil)
  61.   (setq final (q:queen:removeallsame (reverse final)))
  62.   (foreach x (reverse final) (princ "\n") (princ x))
  63.   (princ)
  64. )
  65. (princ "\n By qjchen@gmail.com, 八皇后问题，命令test")
  66. (princ)

评分

参与人数 1明经币 +1 收起 理由
cabinsummer + 1 比我设计的简单得多，大师就是大师

查看全部评分

回复 支持 反对

使用道具 举报

qjchen
发表于 2011-11-27 18:09 | 显示全部楼层
To cabinsummer，您过奖了，我的水平还很普通，离大师有n光年。
在这里
http://www.theswamp.org/index.php?topic=39213.0
Lee Mac和Evgeniy都写了很漂亮的8皇后解法。
回复 支持 反对

使用道具 举报

cabinsummer
 楼主| 发表于 2011-11-27 18:52 | 显示全部楼层
qjchen 发表于 2011-11-27 18:09
To cabinsummer，您过奖了，我的水平还很普通，离大师有n光年。
在这里
http://www.theswamp.org/ ...

你把我的大挑战都放到国外网站上了。
这是我第一次走出国门，呵呵
回复 支持 反对

使用道具 举报

12下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

小黑屋|手机版|CAD论坛|CAD教程|CAD下载|联系我们|关于明经|明经通道 ( 粤ICP备05003914号 )  
©2000-2023 明经通道 版权所有 本站代码，在未取得本站及作者授权的情况下，不得用于商业用途

GMT+8, 2024-4-25 14:54 , Processed in 0.334933 second(s), 34 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表