Eight queens puzzle (Scala)
From LiteratePrograms
The eight queens problem is the problem of placing eight queens on an 8×8 chessboard such that none of them attack one another (no two are in the same row, column, or diagonal). More generally, the n queens problem places n queens on an n×n chessboard.
This article describes a simple Scala implementation of a solver for the Eight Queens puzzle.
Contents |
Representation
The solver will create a list of solutions, where each solution is a list of integers. Each of those integers represent a column in which one of the queens is placed. The queens are in reverse order, i.e. the last queen to be placed is first in the solution.
Strategy
We will begin with an empty list of solutions and perform an add operation on it to get a list of partial solutions with one queen each. The add operation will be repeated until we have a list of solutions with eight queens each. We will need to define the add operator, and to be able to do that, we have to define a way to know, given a partial solution, which of the squares in the next row can be attacked by the already placed queens.
Find a safe place
If we have already placed four queens on rows 1 - 4, the placement of the fifth queen is constrained by the earlier placements such that 1) we may not place the queen in the same column as any of the earlier queens, and 2) we may not place the queen in a square that is diagonally connected to any of the earlier queens. The first constraint is easy to implement if s is a solution (a list containing the column numbers of the queens that have already been placed) and x is a candidate column number for the next queen:
val s = List(5, 7, 2, 6) val unsafe = s toSet if (unsafe(x)) // no else // ok
The second constraint is a little bit more complicated, since we need to calculate which squares are diagonally connected to the queens we already have. For the queen in the previous row, those squares are 4 and 6, and for the queen before that, they are 5 and 9 (the first one is already taken, and the other is off the board, but never mind). In general, if one of the queens in the partial solution is on column c and it is the rth queen going backwards in the solution (starting from 1), squares c - r, c, and c + r are attacked by that queen. This means that we can define a function for the calculation:
<<Define finder function>>= val finder: ((Int, Int)) => Seq[Int] = { case (c, r) => Seq(c - r, c, c + r) }
To use this function, we need values for c and r. The former comes directly from the partial solution, and the latter can be zipped in:
val s = List(5, 7, 2, 6) s zip (1 to 8) // yields List((5,1), (7,2), (2,3), (6,4))
Given the constant n, which stands for 8, we can create the set of unsafe squares like this:
<<Create set of unsafe squares>>= (s zip (1 to n)) flatMap finder toSet
Let us put what we have so far in an object:
<<Find unsafe set for s>>= object UnsafeSet { Define finder function def apply (s: List[Int]) = Create set of unsafe squares }
Define an add operator
The unsafe set generator will help us define an operator that can take a collection p of (partial) solutions, each with k-1 queens placed, and return a collection of solutions with k queens placed.
We pick a partial solution s from p and calculate the unsafe set for that partial solution.
<<Get partial solution and unsafe set>>= s <- p u = UnsafeSet(s)
We can get a candidate column for placement by picking it from the range 1 to n. If it isn't in the unsafe set, we can use it.
<<Get candidate column and check if it is safe>>= x <- 1 to n if !u(x)
Every x-value that passes the test is consed with the current s and collected by the for comprehension. Values of s that don't allow any x-value to pass are discarded.
<<Extend solution list>>= for { Get partial solution and unsafe set Get candidate column and check if it is safe } yield x :: s
Now we can define the add operator:
pk ← pk-1 add k
It takes a list of partial solutions with k-1 queens each and an integer value (which it ignores, since it doesn't need it) and returns a list of partial solutions with k queens each. The type alias LLI stands for List[List[Int]].
<<Add queen>>= val add: (LLI, Int) => LLI = { (p, _) => Extend solution list }
Define a solution list builder
Using the shorthand form of foldLeft, we can define a function that builds a list of complete solutions step by step using the add operator.
<<Define solution builder>>= def queens (start: LLI) = (start /: (1 to n))(add)
The complete program
And here is the complete program.
<<eightqueens.scala>>= object EightQueens { val n = 8 type LLI = List[List[Int]] Find unsafe set for s Add queen Define solution builder def main (args: Array[String]) { val solutions = queens(List(List())) solutions foreach println println(solutions.size) } }
| Download code |