home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Environments / Clean 1.2.4 / Small Demos / squeen.icl < prev    next >
Encoding:
Text File  |  1996-01-17  |  2.0 KB  |  59 lines  |  [TEXT/3PRM]
  1. module squeen
  2.  
  3. /*
  4. The Queens Problem.
  5.  
  6. Or: How to put n queens on a n*n chessboard in such a way that they
  7. cannot attack each other.
  8.     
  9. The result of this program is the number of possible solutions for
  10. the queens problem for a certain boardsize together with one solution.
  11. When BoardSize is 8 the result will be: (92,[4,2,7,3,6,8,5,1]),
  12. which means the queens are on a4, b2, c7, d3, e6, f8, g5 and h1.
  13.  
  14. Strictness annotations are used at certain points, because that makes
  15. this program more than twice as fast (the strictness analyzer is not
  16. able to deduce this strictness information). However, other Clean programs
  17. for the Queens problem exist without strictness annotations added by the 
  18. programmer that are only 40% slower than this solution (lqueen.icl).
  19.  
  20. */
  21.  
  22. import StdEnv
  23.  
  24. BoardSize :== 8 // The size of the chessboard.
  25.  
  26. //    Finding all solutions for the queens problem.
  27.     
  28. Queens::Int [Int] [[Int]] -> [[Int]]
  29. Queens row board boards
  30.     | row>BoardSize    =  [board : boards]
  31.     | otherwise        =  TryCols BoardSize row board boards
  32.  
  33. TryCols::Int Int [Int] [[Int]] -> [[Int]]
  34. TryCols 0 row board boards =  boards
  35. TryCols col row board boards
  36.     | Save col 1 board    =    TryCols (col-1) row board queens
  37.     | otherwise            =     TryCols (col-1) row board boards
  38. where    queens    = Queens (row+1) [col : board] boards
  39.  
  40. /*    The strictness analyzer can't derive strictness for the first and second
  41.     argument of Save, because they are not used in the first alternative
  42.     of that function. However, Save is strict in these arguments (in the
  43.     context of this program) and adding the strictness annotations speeds
  44.     up this program considerably. */
  45.  
  46. Save::!Int !Int [Int] -> Bool
  47. Save  c1 rdiff [] =  True
  48. Save  c1 rdiff [c2:cols]
  49.     | cdiff==0 || cdiff==rdiff || cdiff==0-rdiff    =    False
  50.     | otherwise                                        =    Save c1 (rdiff+1) cols
  51. where    cdiff    = c1 - c2
  52.  
  53. /*    The Start Rule: Calculate the list of solutions, show the first
  54.     solution and the length of that list. */
  55.     
  56. Start::(Int,[Int])
  57. Start     =     (length solutions, hd solutions)
  58. where    solutions    = Queens 1 [] []
  59.