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 / genqueen.icn < prev    next >
Text File  |  2000-07-29  |  3KB  |  102 lines
  1. ############################################################################
  2. #
  3. #    File:     genqueen.icn
  4. #
  5. #    Subject:  Program to solve arbitrary-size n-queens problem
  6. #
  7. #    Author:   Peter A. Bigot
  8. #
  9. #    Date:     October 25, 1990
  10. #
  11. ############################################################################
  12. #
  13. #   This file is in the public domain.
  14. #
  15. ############################################################################
  16. #
  17. # This program solve the non-attacking n-queens problem for (square) boards
  18. # of arbitrary size.  The problem consists of placing chess queens on an
  19. # n-by-n grid such that no queen is in the same row, column, or diagonal as
  20. # any other queen.  The output is each of the solution boards; rotations
  21. # not considered equal.  An example of the output for n:
  22. #
  23. #     -----------------
  24. #     |Q| | | | | | | |
  25. #     -----------------
  26. #     | | | | | | |Q| |
  27. #     -----------------
  28. #     | | | | |Q| | | |
  29. #     -----------------
  30. #     | | | | | | | |Q|
  31. #     -----------------
  32. #     | |Q| | | | | | |
  33. #     -----------------
  34. #     | | | |Q| | | | |
  35. #     -----------------
  36. #     | | | | | |Q| | |
  37. #     -----------------
  38. #     | | |Q| | | | | |
  39. #     -----------------
  40. #     
  41. # Usage: genqueen n
  42. # where n is the number of rows / columns in the board.  The default for n
  43. # is 6.
  44. #
  45. ############################################################################
  46.  
  47. global
  48.    n,                           # Number of rows/columns
  49.    rw,                          # List of queens in each row
  50.    dd,                          # List of queens in each down diagonal
  51.    ud                           # List of queens in each up diagonal
  52.  
  53. procedure main (args)           # Program arguments
  54.    n := integer (args [1]) | 6
  55.    rw := list (n)
  56.    dd := list (2*n-1)
  57.    ud := list (2*n-1)
  58.    solvequeen (1)
  59.    return
  60.    end # procedure main
  61.  
  62. # placequeen(c) -- Place a queen in every permissible position in column c.
  63. # Suspend with each result.
  64. procedure placequeen (c)        # Column at which to place queen
  65.    local r                      # Possible placement row
  66.    
  67.    every r := 1 to n do
  68.       suspend (/rw [r] <- /dd [r+c-1] <- /ud [n+r-c] <- c)
  69.    fail
  70.    end # procedure placequeen
  71.  
  72. # solvequeen(c) -- Place the c'th and following column queens on the board.
  73. # Write board if have completed it.  Suspends all viable results
  74. procedure solvequeen (c)        # Column for next queen placement
  75.    if (c > n) then {
  76.       # Have placed all required queens.  Write the board, and resume search.
  77.       writeboard ()
  78.       fail
  79.       }
  80.    suspend placequeen (c) & solvequeen (c+1)
  81.    fail
  82.    end # procedure solvequeen
  83.  
  84. # writeboard() -- Write an image of the board with the queen positions
  85. # represented by Qs.
  86. procedure writeboard ()
  87.    local
  88.       r,                        # Index over rows during print
  89.       c,                        # Column of queen in row r
  90.       row                       # Depiction of row as its created
  91.  
  92.    write (repl ("--", n), "-")
  93.    every r := 1 to n do {
  94.       c := rw [r]
  95.       row := repl ("| ", n) || "|"
  96.       row [2*c] := "Q"
  97.       write (row)
  98.       write (repl ("--", n), "-")
  99.       }
  100.    write ()
  101.    end # procedure writeboard
  102.