home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / BIPL.ZIP / PROGS.ZIP / QUEENS.ICN < prev    next >
Encoding:
Text File  |  1992-09-28  |  2.8 KB  |  100 lines
  1. ############################################################################
  2. #
  3. #    File:     queens.icn
  4. #
  5. #    Subject:  Program to generate solutions to the n-queens problem
  6. #
  7. #    Author:   Stephen B. Wampler
  8. #
  9. #    Date:     June 10, 1988
  10. #
  11. ###########################################################################
  12. #  
  13. #     This program displays the solutions to the non-attacking n-
  14. #  queens problem: the ways in which n queens can be placed on an
  15. #  n-by-n chessboard so that no queen can attack another. A positive
  16. #  integer can be given as a command line argument to specify the
  17. #  number of queens. For example,
  18. #  
  19. #          iconx queens -n8
  20. #  
  21. #  displays the solutions for 8 queens on an 8-by-8 chessboard.  The
  22. #  default value in the absence of an argument is 6.  One solution
  23. #  for six queens is:
  24. #  
  25. #         -------------------------
  26. #         |   | Q |   |   |   |   |
  27. #         -------------------------
  28. #         |   |   |   | Q |   |   |
  29. #         -------------------------
  30. #         |   |   |   |   |   | Q |
  31. #         -------------------------
  32. #         | Q |   |   |   |   |   |
  33. #         -------------------------
  34. #         |   |   | Q |   |   |   |
  35. #         -------------------------
  36. #         |   |   |   |   | Q |   |
  37. #         -------------------------
  38. #  
  39. #  Comments: There are many approaches to programming solutions to
  40. #  the n-queens problem.  This program is worth reading for
  41. #  its programming techniques.
  42. #  
  43. ############################################################################
  44. #
  45. #  Links: options
  46. #
  47. ############################################################################
  48.  
  49. link options
  50.  
  51. global n, solution
  52.  
  53. procedure main(args)
  54.    local i, opts
  55.  
  56.    opts := options(args,"n+")
  57.    n := \opts["n"] | 6
  58.    if n <= 0 then stop("-n needs a positive numeric parameter")
  59.  
  60.    solution := list(n)        # ... and a list of column solutions
  61.    write(n,"-Queens:")
  62.    every q(1)            # start by placing queen in first column
  63. end
  64.  
  65. # q(c) - place a queen in column c.
  66. #
  67. procedure q(c)
  68.    local r
  69.    static up, down, rows
  70.    initial {
  71.       up := list(2*n-1,0)
  72.       down := list(2*n-1,0)
  73.       rows := list(n,0)
  74.       }
  75.    every 0 = rows[r := 1 to n] = up[n+r-c] = down[r+c-1] &
  76.       rows[r] <- up[n+r-c] <- down[r+c-1] <- 1        do {
  77.          solution[c] := r    # record placement.
  78.          if c = n then show()
  79.          else q(c + 1)        # try to place next queen.
  80.          }
  81. end
  82.  
  83. # show the solution on a chess board.
  84. #
  85. procedure show()
  86.    static count, line, border
  87.    initial {
  88.       count := 0
  89.       line := repl("|   ",n) || "|"
  90.       border := repl("----",n) || "-"
  91.       }
  92.    write("solution: ", count+:=1)
  93.    write("  ", border)
  94.    every line[4*(!solution - 1) + 3] <- "Q" do {
  95.       write("  ", line)
  96.       write("  ", border)
  97.       }
  98.    write()
  99. end
  100.