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