On 10/4/13 8:21 PM, Stephen Thompson wrote:
Anyone else tried GA on the 8-queens?
I'd suggest using a Satisfiability Modulo Theory solver. Z3 is one
(gratis source code available).
http://z3.codeplex.com
There are nice wrappers like SBV in Haskell (scroll down to see the
different puzzles, N-Queens, Suduko, etc.)
http://hackage.haskell.org/package/sbv
This is basically all that code that's needed to specify N Queens (a
single predicate).
-- | Checks that a given solution of @n@-queens is valid, i.e., no queen
-- captures any other.
isValid :: Int -> Solution -> SBool
isValid n s = bAll rangeFine s &&& allDifferent s &&& bAll checkDiag ijs
where rangeFine x = x .>= 1 &&& x .<= fromIntegral n
ijs = [(i, j) | i <- [1..n], j <- [i+1..n]]
checkDiag (i, j) = diffR ./= diffC
where qi = s !! (i-1)
qj = s !! (j-1)
diffR = ite (qi .>= qj) (qi-qj) (qj-qi)
diffC = fromIntegral (j-i)
A few seconds of runtime to get:
Finding all 8-queens solutions..
Solution #1: [4,8,1,5,7,2,6,3] (Valid: True)
Solution #2: [6,2,7,1,3,5,8,4] (Valid: True)
Solution #3: [3,6,2,7,1,4,8,5] (Valid: True)
Solution #4: [5,2,4,7,3,8,6,1] (Valid: True)
Solution #5: [6,3,7,2,8,5,1,4] (Valid: True)
Solution #6: [7,1,3,8,6,4,2,5] (Valid: True)
Solution #7: [6,3,5,7,1,4,2,8] (Valid: True)
Solution #8: [3,6,8,1,4,7,5,2] (Valid: True)
Solution #9: [4,2,7,5,1,8,6,3] (Valid: True)
Solution #10: [4,6,8,2,7,1,3,5] (Valid: True)
Solution #11: [6,3,1,8,4,2,7,5] (Valid: True)
Solution #12: [5,7,2,6,3,1,4,8] (Valid: True)
Solution #13: [4,7,5,2,6,1,3,8] (Valid: True)
Solution #14: [2,5,7,4,1,8,6,3] (Valid: True)
Solution #15: [6,1,5,2,8,3,7,4] (Valid: True)
Solution #16: [6,3,1,7,5,8,2,4] (Valid: True)
Solution #17: [3,7,2,8,5,1,4,6] (Valid: True)
Solution #18: [7,2,6,3,1,4,8,5] (Valid: True)
Solution #19: [5,7,1,3,8,6,4,2] (Valid: True)
Solution #20: [2,7,3,6,8,5,1,4] (Valid: True)
Solution #21: [1,7,5,8,2,4,6,3] (Valid: True)
Solution #22: [4,7,5,3,1,6,8,2] (Valid: True)
Solution #23: [5,7,2,6,3,1,8,4] (Valid: True)
Solution #24: [3,6,2,7,5,1,8,4] (Valid: True)
Solution #25: [6,3,5,8,1,4,2,7] (Valid: True)
Solution #26: [4,8,1,3,6,2,7,5] (Valid: True)
Solution #27: [2,8,6,1,3,5,7,4] (Valid: True)
Solution #28: [3,5,7,1,4,2,8,6] (Valid: True)
Solution #29: [5,1,8,6,3,7,2,4] (Valid: True)
Solution #30: [8,4,1,3,6,2,7,5] (Valid: True)
Solution #31: [5,8,4,1,7,2,6,3] (Valid: True)
Solution #32: [7,5,3,1,6,8,2,4] (Valid: True)
Solution #33: [6,3,7,2,4,8,1,5] (Valid: True)
Solution #34: [3,6,4,2,8,5,7,1] (Valid: True)
Solution #35: [6,4,7,1,8,2,5,3] (Valid: True)
Solution #36: [3,1,7,5,8,2,4,6] (Valid: True)
Solution #37: [7,3,1,6,8,5,2,4] (Valid: True)
Solution #38: [3,6,2,5,8,1,7,4] (Valid: True)
Solution #39: [5,3,8,4,7,1,6,2] (Valid: True)
Solution #40: [6,3,7,4,1,8,2,5] (Valid: True)
Solution #41: [8,2,5,3,1,7,4,6] (Valid: True)
Solution #42: [2,5,7,1,3,8,6,4] (Valid: True)
Solution #43: [4,2,5,8,6,1,3,7] (Valid: True)
Solution #44: [3,6,4,1,8,5,7,2] (Valid: True)
Solution #45: [4,2,8,6,1,3,5,7] (Valid: True)
Solution #46: [7,3,8,2,5,1,6,4] (Valid: True)
Solution #47: [5,3,1,7,2,8,6,4] (Valid: True)
Solution #48: [3,7,2,8,6,4,1,5] (Valid: True)
Solution #49: [2,4,6,8,3,1,7,5] (Valid: True)
Solution #50: [1,5,8,6,3,7,2,4] (Valid: True)
Solution #51: [5,1,4,6,8,2,7,3] (Valid: True)
Solution #52: [5,8,4,1,3,6,2,7] (Valid: True)
Solution #53: [4,7,1,8,5,2,6,3] (Valid: True)
Solution #54: [6,3,1,8,5,2,4,7] (Valid: True)
Solution #55: [2,6,1,7,4,8,3,5] (Valid: True)
Solution #56: [3,6,8,2,4,1,7,5] (Valid: True)
Solution #57: [4,1,5,8,6,3,7,2] (Valid: True)
Solution #58: [7,2,4,1,8,5,3,6] (Valid: True)
Solution #59: [8,3,1,6,2,5,7,4] (Valid: True)
Solution #60: [5,2,4,6,8,3,1,7] (Valid: True)
Solution #61: [3,5,8,4,1,7,2,6] (Valid: True)
Solution #62: [5,3,1,6,8,2,4,7] (Valid: True)
Solution #63: [1,7,4,6,8,2,5,3] (Valid: True)
Solution #64: [7,4,2,8,6,1,3,5] (Valid: True)
Solution #65: [2,6,8,3,1,4,7,5] (Valid: True)
Solution #66: [3,6,8,1,5,7,2,4] (Valid: True)
Solution #67: [4,7,3,8,2,5,1,6] (Valid: True)
Solution #68: [5,7,4,1,3,8,6,2] (Valid: True)
Solution #69: [5,1,8,4,2,7,3,6] (Valid: True)
Solution #70: [8,2,4,1,7,5,3,6] (Valid: True)
Solution #71: [5,2,8,1,4,7,3,6] (Valid: True)
Solution #72: [5,7,1,4,2,8,6,3] (Valid: True)
Solution #73: [6,4,1,5,8,2,7,3] (Valid: True)
Solution #74: [4,1,5,8,2,7,3,6] (Valid: True)
Solution #75: [3,5,2,8,1,7,4,6] (Valid: True)
Solution #76: [5,2,6,1,7,4,8,3] (Valid: True)
Solution #77: [7,4,2,5,8,1,3,6] (Valid: True)
Solution #78: [6,4,2,8,5,7,1,3] (Valid: True)
Solution #79: [4,2,8,5,7,1,3,6] (Valid: True)
Solution #80: [4,6,8,3,1,7,5,2] (Valid: True)
Solution #81: [4,6,1,5,2,8,3,7] (Valid: True)
Solution #82: [2,7,5,8,1,4,6,3] (Valid: True)
Solution #83: [1,6,8,3,7,4,2,5] (Valid: True)
Solution #84: [6,8,2,4,1,7,5,3] (Valid: True)
Solution #85: [4,2,7,3,6,8,1,5] (Valid: True)
Solution #86: [3,5,2,8,6,4,7,1] (Valid: True)
Solution #87: [6,4,7,1,3,5,2,8] (Valid: True)
Solution #88: [4,8,5,3,1,7,2,6] (Valid: True)
Solution #89: [3,8,4,7,1,6,2,5] (Valid: True)
Solution #90: [5,7,2,4,8,1,3,6] (Valid: True)
Solution #91: [4,2,7,3,6,8,5,1] (Valid: True)
Solution #92: [6,2,7,1,4,8,5,3] (Valid: True)
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com
