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 / ipl / progs / vnq.icn < prev    next >
Text File  |  2000-07-29  |  4KB  |  166 lines
  1. ############################################################################
  2. #
  3. #    File:     vnq.icn
  4. #
  5. #    Subject:  Program to display solutions to n-queens problem
  6. #
  7. #    Author:   Stephen B. Wampler
  8. #
  9. #    Date:     August 14, 1996
  10. #
  11. ############################################################################
  12. #
  13. #   This file is in the public domain.
  14. #
  15. ############################################################################
  16. #
  17. #  This program displays solutions to the n-queens problem.
  18. #
  19. ############################################################################
  20. #
  21. #  Links: options
  22. #
  23. ############################################################################
  24.  
  25. link options
  26.  
  27. global n, nthq, solution, goslow, showall, line, border
  28.  
  29. procedure main(args)
  30. local i, opts
  31.  
  32.    opts := options(args, "sah")  
  33.    n := integer(get(args)) | 8    # default is 8 queens
  34.    if \opts["s"] then goslow := "yes"
  35.    if \opts["a"] then showall := "yes"
  36.    if \opts["h"] then helpmesg()
  37.  
  38.    line := repl("|   ", n) || "|"
  39.    border := repl("----", n) || "-"
  40.    clearscreen()
  41.    movexy(1, 1)
  42.    write()
  43.    write("  ", border)
  44.    every 1 to n do {
  45.       write("  ", line)
  46.       write("  ", border)
  47.       }
  48.  
  49.    nthq := list(n+2)    # need list of queen placement routines
  50.    solution := list(n)    # ... and a list of column solutions
  51.  
  52.    nthq[1] := &main    # 1st queen is main routine.
  53.    every i := 1 to n do    # 2 to n+1 are real queen placement
  54.       nthq[i+1] := create q(i)    #    routines, one per column.
  55.    nthq[n+2] := create show()    # n+2nd queen is display routine.
  56.  
  57.    write(n, "-Queens:")
  58.    @nthq[2]    # start by placing queen in first colm.
  59.  
  60.    movexy(1, 2 * n + 5)
  61. end
  62.  
  63. # q(c) - place a queen in column c (this is c+1st routine).
  64. procedure q(c)
  65. local r 
  66. static up, down, rows
  67.  
  68.    initial {
  69.       up := list(2 * n -1, 0)
  70.       down := list(2 * n -1, 0)
  71.       rows := list(n, 0)
  72.       }
  73.  
  74.    repeat {
  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 \showall then {
  79.             movexy(4 * (r - 1) + 5, 2 * c + 1)
  80.             writes("@")
  81.             }
  82.          @nthq[c + 2]    # try to place next queen.
  83.          if \showall then {
  84.             movexy(4  * (r - 1) + 5, 2 * c + 1)
  85.             writes(" ")
  86.             }
  87.          }
  88.       @nthq[c]    # tell last queen placer 'try again'
  89.       }
  90.  
  91. end
  92.  
  93. # show the solution on a chess board.
  94.  
  95. procedure show()
  96.    local c
  97.    static count, lastsol
  98.  
  99.    initial {
  100.       count := 0
  101.       }
  102.  
  103.    repeat {
  104.       if /showall & \lastsol then {
  105.          every c := 1 to n do {
  106.             movexy(4 * (lastsol[c] - 1) + 5, 2 * c + 1)
  107.             writes(" ")
  108.             }
  109.          }
  110.       movexy(1, 1)
  111.       write("solution: ", right(count +:= 1, 10))
  112.       if /showall then {
  113.          every c := 1 to n do {
  114.             movexy(4 * (solution[c] - 1) + 5, 2 * c + 1)
  115.             writes("Q")
  116.             }
  117.          lastsol := copy(solution)
  118.          }
  119.       if \goslow then {
  120.          movexy(1, 2 * n + 4)
  121.          writes("Press return to see next solution:")
  122.          read() | {
  123.             movexy(1, 2 * n + 5)
  124.             stop("Aborted.")
  125.          }
  126.          movexy(1, 2 * n + 4)
  127.          clearline()
  128.          }
  129.  
  130.       @nthq[n+1]                          # tell last queen placer to try again
  131.       }
  132.  
  133. end
  134.  
  135. procedure helpmesg()
  136.    write(&errout, "Usage: vnq [-s] [-a] [n]")
  137.    write(&errout, "    where -s means to stop after each solution, ")
  138.    write(&errout, "          -a means to show placement of every queen")
  139.    write(&errout, "              while trying to find a solution")
  140.    write(&errout, "      and  n is the size of the board (defaults to 8)")
  141.    stop()
  142. end
  143.  
  144. # Move cursor to x, y
  145. #
  146. procedure movexy (x, y)
  147.    writes("\^[[", y, ";", x, "H")
  148.    return
  149. end
  150.  
  151. #
  152. # Clear the text screen
  153. #
  154. procedure clearscreen()
  155.    writes("\^[[2J")
  156.    return
  157. end
  158.  
  159. #
  160. # Clear the rest of the line
  161. #
  162. procedure clearline()
  163.    writes("\^[[2K")
  164.    return
  165. end
  166.