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