8 Queens Problem

[Frank Wimberly-2]

This came up at physical Friam this am.

 

http://en.wikipedia.org/wiki/Eight_queens_puzzle

 

Frank

 

 

Frank C. Wimberly

140 Calle Ojo Feliz

Santa Fe, NM 87505

 

[hidden email]     [hidden email]

Phone:  [phone]      Cell:  [phone]

 

============================================================
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

[George Duncan-2]

Fascinating!

George Duncan
georgeduncanart.com

[phone] 
Represented by ViVO Contemporary

725 Canyon Road

Santa Fe, NM 87501

 
Dynamic application of matrix order and luminous chaos.

On Fri, Oct 4, 2013 at 1:35 PM, Frank Wimberly <[hidden email]> wrote:

This came up at physical Friam this am.

 

http://en.wikipedia.org/wiki/Eight_queens_puzzle

 

Frank

 

 

Frank C. Wimberly

140 Calle Ojo Feliz

Santa Fe, NM 87505

 

[hidden email]     [hidden email]

Phone:  <a href="tel:%28505%29%20995-8715" value="[phone]" target="_blank">[phone]      Cell:  <a href="tel:%28505%29%20670-9918" value="[phone]" target="_blank">[phone]

 

============================================================
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

============================================================
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

[Stephen Thompson]

I have been looking at the genetic algorithm again and thought
the 8-queens problem would be an interesting challenge for
figuring out a representation structure to encode the problem. 

I thought one queen per row in any of the 8 horizontal positions,
generate a collection of "rows", then construct an 8x8 board one
row at a time then check the vertical and diagonal vectors to
evaluate a "solution".

I recall the knights tour using backtracking as an early assignment
in Pascal in the mid-80s undergrad CompSci.  The Wikipedia article on
8-queens shows Wirth's backtracking program.

I hope to get around to it before the end of the year. Anyone
else tried GA on the 8-queens?

Stephen Thompson

On 10/4/2013 2:35 PM, Frank Wimberly wrote:

This came up at physical Friam this am.

 

http://en.wikipedia.org/wiki/Eight_queens_puzzle

 

Frank

 

 

Frank C. Wimberly

140 Calle Ojo Feliz

Santa Fe, NM 87505

 

[hidden email]     [hidden email]

Phone:  [phone]      Cell:  [phone]

 

============================================================
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

============================================================
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

[Marcus G. Daniels]

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

[Stephen Thompson]

Marcus:

Thanks for the suggestions on alternative approaches.  I am not aware
of the Satisfiability Modulo Theory nor Z3.  I will look into those.  Tho,
my original intent was not so much to find a solution to the 8-queens,
but instead to get additional practice on GAs.  GAs are probably inefficient
for the 8-queens, but the exercise forces me to learn about constructing
representation structures for a GA. 

I see it a bit like taking songs - one from each different musical era of the last
600 years and then creating a rendition of each in only one genre - say,
All Along The Watchtower, Rites of Spring, and Geershwin's Summertime and
create a rendition in the Renaissance musical style of a motet for each of those
three songs - new representations.

thanks,
StephT 

On 10/5/2013 1:50 AM, Marcus G. Daniels wrote:

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

============================================================
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