Eight Queens Problem In Smalltalk

An implementation of the EightQueensProblem in SmalltalkLanguage

I've gone for maximum Brownie points in that my solution does:

• arbitrary board sizes
• logs the solutions found
• only counts solutions that are unique through reflection and rotation
  • As a sanity check, if you turn that feature off, do your solution counts agree with those given on the other page?

• solves 3-D chess boards - well maybe not.

you can see

• sample output
• the code
• the test code

Quite a lot of the code is to do with only counting solutions that are unique through reflection and rotation. Some of it is a little bit repetitive (see method rotationsAndReflections and its friends), but I can't think of a way of slickening it up.

Also, I wrote the code before the tests thinking that with such a simple problem I didn't need to bother. Then when I started writing the tests I saw how foolish I had been. Perhaps I'll learn one day.

Like the Ruby version, the code also allows the generation of a solution from a partially completed board.

As for performance, I don't make any great claims, but I did manage to count the solutions for the 14*14 board without it taking a ridiculously long time.

StephenHutchinson

---

Sample output

 (1 to: 16) inject: '' into: [ :string :i | string, i printString, ': ', (Board new: i) solutions size printString, '
 ']

 1: 1
 2: 0
 3: 0
 4: 1
 5: 2
 6: 1
 7: 6
 8: 12
 9: 46
 10: 92
 11: 341
 12: 1787
 13: 9233
 14: 45752

 ((Board new: 8) solutions asSortedCollection: [ :a :b | a hash <= b hash])  inject: '' into: [ :sum :each | sum, '
 ', each printString] 

 1: |Q|_|_|_|_|_|_|_|
 2: |_|_|_|_|Q|_|_|_|
 3: |_|_|_|_|_|_|_|Q|
 4: |_|_|_|_|_|Q|_|_|
 5: |_|_|Q|_|_|_|_|_|
 6: |_|_|_|_|_|_|Q|_|
 7: |_|Q|_|_|_|_|_|_|
 8: |_|_|_|Q|_|_|_|_|

 1: |Q|_|_|_|_|_|_|_|
 2: |_|_|_|_|_|Q|_|_|
 3: |_|_|_|_|_|_|_|Q|
 4: |_|_|Q|_|_|_|_|_|
 5: |_|_|_|_|_|_|Q|_|
 6: |_|_|_|Q|_|_|_|_|
 7: |_|Q|_|_|_|_|_|_|
 8: |_|_|_|_|Q|_|_|_|

 1: |_|Q|_|_|_|_|_|_|
 2: |_|_|_|Q|_|_|_|_|
 3: |_|_|_|_|_|Q|_|_|
 4: |_|_|_|_|_|_|_|Q|
 5: |_|_|Q|_|_|_|_|_|
 6: |Q|_|_|_|_|_|_|_|
 7: |_|_|_|_|_|_|Q|_|
 8: |_|_|_|_|Q|_|_|_|

 1: |_|Q|_|_|_|_|_|_|
 2: |_|_|_|_|Q|_|_|_|
 3: |_|_|_|_|_|_|Q|_|
 4: |Q|_|_|_|_|_|_|_|
 5: |_|_|Q|_|_|_|_|_|
 6: |_|_|_|_|_|_|_|Q|
 7: |_|_|_|_|_|Q|_|_|
 8: |_|_|_|Q|_|_|_|_|

 1: |_|Q|_|_|_|_|_|_|
 2: |_|_|_|_|Q|_|_|_|
 3: |_|_|_|_|_|_|Q|_|
 4: |_|_|_|Q|_|_|_|_|
 5: |Q|_|_|_|_|_|_|_|
 6: |_|_|_|_|_|_|_|Q|
 7: |_|_|_|_|_|Q|_|_|
 8: |_|_|Q|_|_|_|_|_|

 1: |_|Q|_|_|_|_|_|_|
 2: |_|_|_|_|_|Q|_|_|
 3: |Q|_|_|_|_|_|_|_|
 4: |_|_|_|_|_|_|Q|_|
 5: |_|_|_|Q|_|_|_|_|
 6: |_|_|_|_|_|_|_|Q|
 7: |_|_|Q|_|_|_|_|_|
 8: |_|_|_|_|Q|_|_|_|

 1: |_|Q|_|_|_|_|_|_|
 2: |_|_|_|_|_|Q|_|_|
 3: |_|_|_|_|_|_|_|Q|
 4: |_|_|Q|_|_|_|_|_|
 5: |Q|_|_|_|_|_|_|_|
 6: |_|_|_|Q|_|_|_|_|
 7: |_|_|_|_|_|_|Q|_|
 8: |_|_|_|_|Q|_|_|_|

 1: |_|Q|_|_|_|_|_|_|
 2: |_|_|_|_|_|_|Q|_|
 3: |_|_|Q|_|_|_|_|_|
 4: |_|_|_|_|_|Q|_|_|
 5: |_|_|_|_|_|_|_|Q|
 6: |_|_|_|_|Q|_|_|_|
 7: |Q|_|_|_|_|_|_|_|
 8: |_|_|_|Q|_|_|_|_|

 1: |_|Q|_|_|_|_|_|_|
 2: |_|_|_|_|_|_|Q|_|
 3: |_|_|_|_|Q|_|_|_|
 4: |_|_|_|_|_|_|_|Q|
 5: |Q|_|_|_|_|_|_|_|
 6: |_|_|_|Q|_|_|_|_|
 7: |_|_|_|_|_|Q|_|_|
 8: |_|_|Q|_|_|_|_|_|

 1: |_|_|Q|_|_|_|_|_|
 2: |_|_|_|_|Q|_|_|_|
 3: |_|Q|_|_|_|_|_|_|
 4: |_|_|_|_|_|_|_|Q|
 5: |Q|_|_|_|_|_|_|_|
 6: |_|_|_|_|_|_|Q|_|
 7: |_|_|_|Q|_|_|_|_|
 8: |_|_|_|_|_|Q|_|_|

 1: |_|_|Q|_|_|_|_|_|
 2: |_|_|_|_|Q|_|_|_|
 3: |_|_|_|_|_|_|_|Q|
 4: |_|_|_|Q|_|_|_|_|
 5: |Q|_|_|_|_|_|_|_|
 6: |_|_|_|_|_|_|Q|_|
 7: |_|Q|_|_|_|_|_|_|
 8: |_|_|_|_|_|Q|_|_|

 1: |_|_|Q|_|_|_|_|_|
 2: |_|_|_|_|_|Q|_|_|
 3: |_|Q|_|_|_|_|_|_|
 4: |_|_|_|_|Q|_|_|_|
 5: |_|_|_|_|_|_|_|Q|
 6: |Q|_|_|_|_|_|_|_|
 7: |_|_|_|_|_|_|Q|_|
 8: |_|_|_|Q|_|_|_|_|

---

The Code

 Object subclass: #Board
    instanceVariableNames: 'size queenXcoords '
    classVariableNames: ''
    poolDictionaries: ''!

 !Board class publicMethods !

  new: anInteger
    ^self new initializeWithSize: anInteger! !

 !Board publicMethods !

  = aBoard
    self class = aBoard class ifFalse: [^false].
    ^aBoard hasQueenXcoords: queenXcoords!

  addAllQueensAt: aCollection
    aCollection do: [ :each | self addQueenAt: each]!

  addQueenAt: aPoint
    queenXcoords at: aPoint y put: aPoint x!

  cardinalForm
    ^(self rotationsAndReflections asSortedCollection: [ :a :b | a hash <= b hash]) first!

  copy
    ^(self class new: size)
        queenXcoords: queenXcoords copy!

  hash
    | result |
    result := 0.
    queenXcoords do:
        [ :y |    result := result * size.
                    y notNil ifTrue: [ result := result + y]].
    ^result!

  hasQueenXcoords: aCollection
    ^queenXcoords = aCollection!

  initializeWithSize: anInteger
    size := anInteger.
    queenXcoords :=Array new: size.!

  nextUnoccupiedRow
    queenXcoords doWithIndex: [ :x :y | x isNil ifTrue: [^y]].
    ^nil!

  printCharForPosition: aPoint
    ^(queenXcoords at: aPoint y) = aPoint x
        ifTrue: [ $Q]
        ifFalse: [ $_].!

  printOn: aStream
    1 to: size do:
        [ :y |
            aStream    nextPutAll: y printString;
                       nextPutAll: ': |'.
            1 to: size do: [ :x | aStream    nextPut: (self printCharForPosition: x@y);
                                             nextPut: $| ].
            aStream cr.]!

  queenAt: aPoint threatens: bPoint
    ^(aPoint x = bPoint x)
        or: [(aPoint y = bPoint y)
            or: [(aPoint x - bPoint x) abs = (aPoint y - bPoint y) abs]]!

  queenPositions
    | result |
    result := OrderedCollection new.
    queenXcoords doWithIndex: [ :x :y | x notNil ifTrue: [result add: x@y]].
    ^result!

  queenXcoords: aCollection
    queenXcoords := aCollection!

  reflectedInHorizontallAxis: aPoint
    ^aPoint x @ (size + 1 - aPoint y)!

  reflectedInNegativeDiagonal: aPoint
    ^ (size + 1 - aPoint y) @ (size + 1 - aPoint x)!

  reflectedInPositiveDiagonal: aPoint
    ^aPoint y @ aPoint x!

  reflectedInVerticalAxis: aPoint
    ^(size + 1 - aPoint x) @ aPoint y!

  rotated180: aPoint
    ^(size + 1 - aPoint x) @ (size + 1 - aPoint y)!

  rotated270: aPoint
    ^aPoint y @ (size + 1 - aPoint x)!

  rotated90: aPoint
    ^(size + 1 - aPoint y) @ aPoint x!

  rotationsAndReflections
    ^OrderedCollection new
            add: self;
            add: (self transformedUsingBlock: [ :each |self rotated90: each]);
            add: (self transformedUsingBlock: [ :each |self rotated180: each]);
            add: (self transformedUsingBlock: [ :each |self rotated270: each]);
            add: (self transformedUsingBlock: [ :each |self reflectedInHorizontallAxis: each]);
            add: (self transformedUsingBlock: [ :each |self reflectedInVerticalAxis: each]);
            add: (self transformedUsingBlock: [ :each |self reflectedInPositiveDiagonal: each]);
            add: (self transformedUsingBlock: [ :each |self reflectedInNegativeDiagonal: each]);
            yourself!

  solutions
    self nextUnoccupiedRow isNil ifTrue: [^Set with: self cardinalForm].
    ^(self unthreatenedSquaresInRow: self nextUnoccupiedRow)
        inject: Set new
        into: [ :collection :each | collection
                                        addAll: (self copy addQueenAt: each) solutions;
                                        yourself]!

  transformedUsingBlock: aBlock
    ^(self class new: size)
        addAllQueensAt: (self queenPositions collect: aBlock)!

  unthreatenedSquaresInRow: anInteger
    | queenPositions |
    queenPositions := self queenPositions.
    ^((1 to: size) collect: [ :x | x@anInteger])
        select: [ :eachSquare | queenPositions
                                    allSatisfy: [ :eachQueen | (self queenAt: eachQueen threatens: eachSquare) not]]! !

---

Tests

 TestCase subclass: #EightTestCase
    instanceVariableNames: ''
    classVariableNames: ''
    poolDictionaries: ''!

 !EightTestCase publicMethods !

  testAddQueen
    | board |
    board := Board new: 4.
    board addQueenAt: 1@2.
    self should: [ board printString = '1: |_|_|_|_|
  2: |Q|_|_|_|
  3: |_|_|_|_|
  4: |_|_|_|_|
  ']!

  testBoardDifferent
    | board1 board2 |
    board1 := Board new: 4.
    board1 addQueenAt: 1@2;
           addQueenAt: 2@1.
    board2 :=  Board new: 4.
    board2 addQueenAt: 1@1;
           addQueenAt: 1@2.
    self shouldnt: [ board1 = board2]!

  testBoardEquals
    | board1 board2 |
    board1 := Board new: 4.
    board1 addQueenAt: 1@2;
           addQueenAt: 2@1.
    board2 :=  Board new: 4.
    board2 addQueenAt: 2@1;
           addQueenAt: 1@2.
    self should: [ board1 = board2]!

  testNew1
    | board |
    board := Board new: 1.
    self should: [ board printString = '1: |_|
 ']!

  testNew4
    | board |
    board := Board new: 4.
    self should: [ board printString = '1: |_|_|_|_|
  2: |_|_|_|_|
  3: |_|_|_|_|
  4: |_|_|_|_|
  ']!

  testReflectionsAndRotations
    | board boardH boardV boardPd boardNd board90 board180 board270 rnr |
    board := (Board new: 4) addQueenAt: 1@2.
    rnr := board rotationsAndReflections.
    boardH := (Board new: 4) addQueenAt: 4@2.
    boardV := (Board new: 4) addQueenAt: 1@3.
    boardPd := (Board new: 4) addQueenAt: 2@1.
    boardNd := (Board new: 4) addQueenAt: 3@4.
    board90 := (Board new: 4) addQueenAt: 3@1.
    board180 := (Board new: 4) addQueenAt: 4@3.
    board270 := (Board new: 4) addQueenAt: 2@4.
    self should: [rnr includes: board].
    self should: [rnr includes: boardH].
    self should: [rnr includes: boardV].
    self should: [rnr includes: boardPd].
    self should: [rnr includes: boardNd].
    self should: [rnr includes: board90].
    self should: [rnr includes: board180].
    self should: [rnr includes: board270].!

  testSolutions1
    | board solutions solution1|
    board := Board new: 1.
    solution1 := Board new: 1.
    solution1 addQueenAt: 1@1.
    solutions := board solutions.
    self should: [solutions size = 1].
    self should: [solutions includes: solution1 ].!

  testSolutions4
    | board solutions solution1|
    board := Board new: 4.
    solution1 := Board new: 4.
    solution1
        addQueenAt: 1@3;
        addQueenAt: 2@1;
        addQueenAt: 3@4;
        addQueenAt: 4@2.
    solutions := board solutions.
    self should: [solutions size = 1].
    self should: [solutions includes: solution1 ].!

  testSolutions8
    | board solutions |
    board := Board new: 8.
    solutions := board solutions.
    self should: [solutions size = 12].! !