"Eight-queens — classic backtracking search. Counts the number of
 distinct placements of 8 queens on an 8x8 board with no two attacking.
 Expected count: 92."

Object subclass: #EightQueens
  instanceVariableNames: 'columns count size'!

!EightQueens methodsFor: 'init'!
init
  size := 8.
  columns := Array new: size.
  count := 0.
  ^ self!

size: n
  size := n.
  columns := Array new: n.
  count := 0.
  ^ self! !

!EightQueens methodsFor: 'access'!
count ^ count!

size ^ size! !

!EightQueens methodsFor: 'solve'!
solve
  self placeRow: 1.
  ^ count!

placeRow: row
  row > size ifTrue: [count := count + 1. ^ self].
  1 to: size do: [:col |
    (self isSafe: col atRow: row) ifTrue: [
      columns at: row put: col.
      self placeRow: row + 1]]!

isSafe: col atRow: row
  | r prevCol delta |
  r := 1.
  [r < row] whileTrue: [
    prevCol := columns at: r.
    prevCol = col ifTrue: [^ false].
    delta := col - prevCol.
    delta abs = (row - r) ifTrue: [^ false].
    r := r + 1].
  ^ true! !
