Two solutions to the problem of finding all placements of some collection of chess pieces on a chess board of specified size such that no piece is under threat from any other. The problem was recently posed to me by a friend. The 'optimised' solution is significantly faster that the 'unoptimised' one. For example, on my laptop, the n-queens prob…

Chess

package chess

// Everything from this line down to the cut is common to the 'unoptimised' and 'optimised' solutions

case class Location(row: Int, column: Int)

trait Piece {
  def canAttackLocation(from: Location, to: Location): Boolean
}
case object Rook extends Piece {
  def canAttackLocation(from: Location, to: Location): Boolean = from.row == to.row || from.column == to.column
}
case object Knight extends Piece {
  def canAttackLocation(from: Location, to: Location): Boolean = Math.abs(from.row - to.row) + Math.abs(from.column - to.column) == 3
}
case object Bishop extends Piece {
  def canAttackLocation(from: Location, to: Location): Boolean = Math.abs(from.row - to.row) == Math.abs(from.column - to.column)
}
case object Queen extends Piece {
  def canAttackLocation(from: Location, to: Location): Boolean = from.row == to.row || from.column == to.column || Math.abs(from.row - to.row) == Math.abs(from.column - to.column)
}
case object King extends Piece {
  def canAttackLocation(from: Location, to: Location): Boolean = Math.abs(from.row - to.row) <= 1 && Math.abs(from.column - to.column) <= 1
}

trait Board {
  def size(): Location
  def availableLocations(): List[Location]
  def place(piece: Piece, location: Location): Option[Board]
  def hasPieceAttackedBy(piece: Piece, location: Location): Boolean
  def pieceAt(location: Location): Option[Piece]
}

// ✄----------------------------

// Everything from here down to the next cut is for the 'unoptimised' solution

object UnoptimisedChess {
  case class MapBoard(size: Location, pieces: Map[Location, Piece] = Map()) extends Board {
    val availableLocations =
      (for {
        row ← 0 until size.row
        column ← 0 until size.column
        location = Location(row, column)
        if !pieces.keySet(location)
        if !pieces.exists(p ⇒ p._2.canAttackLocation(p._1, location))
      } yield Location(row, column)).toList

    def place(piece: Piece, location: Location): Option[Board] =
      if (availableLocations.contains(location) && !hasPieceAttackedBy(piece, location))
        Some(MapBoard(size, pieces + (location -> piece)))
      else None

    def hasPieceAttackedBy(piece: Piece, location: Location): Boolean = pieces.exists(p ⇒ piece.canAttackLocation(location, p._1))
    def pieceAt(location: Location): Option[Piece] = pieces.get(location)
  }

  def solve(size: Location, pieces: List[Piece]) = doIt(MapBoard(size), pieces).toSet

  private def doIt(initial: Board, pieces: List[Piece]): List[Board] = pieces match {
    case Nil ⇒ List(initial)
    case piece :: remainingPieces ⇒ initial.availableLocations.flatMap { location ⇒
      initial.place(piece, location).toList.flatMap { doIt(_, remainingPieces) }
    }
  }
}

// ✄----------------------------

// Everything from here down to the next cut is for the 'optimised' solution

case class PieceCount(piece: Piece, count: Int)

object OptimisedChess {
  case class EmptyBoard(size: Location) extends Board {
    val availableLocations =
      (for {
        row ← 0 until size.row
        column ← 0 until size.column
      } yield Location(row, column)).toList

    def place(piece: Piece, location: Location) = Some(NonEmptyBoard(this, piece, location))
    def hasPieceAttackedBy(piece: Piece, location: Location) = false
    def pieceAt(location: Location) = None
  }

  case class NonEmptyBoard(parent: Board, piece: Piece, location: Location) extends Board {
    val size = parent.size

    val availableLocations = parent.availableLocations.filterNot(l ⇒ l == location || piece.canAttackLocation(location, l))

    def place(piece: Piece, location: Location) =
      if (availableLocations.contains(location) && !hasPieceAttackedBy(piece, location))
        Some(NonEmptyBoard(this, piece, location))
      else None

    def hasPieceAttackedBy(attackingPiece: Piece, attackingLocation: Location) =
      attackingPiece.canAttackLocation(attackingLocation, location) ||
        parent.hasPieceAttackedBy(attackingPiece, attackingLocation)

    def pieceAt(location: Location) = if (location == this.location) Some(piece) else parent.pieceAt(location)
  }

  private def placePieces(piece: PieceCount, board: Board) = {
    def placePiecesInAvailableLocations(remainingCount: Int, board: Board, availableLocations: List[Location]): List[Board] =
      if (remainingCount == 0)
        List(board)
      else
        availableLocations match {
          case location :: rest ⇒ board.place(piece.piece, location).map(b ⇒ placePiecesInAvailableLocations(remainingCount - 1, b, rest)).getOrElse(Nil) ::: placePiecesInAvailableLocations(remainingCount, board, rest)
          case Nil ⇒ Nil
        }
    placePiecesInAvailableLocations(piece.count, board, board.availableLocations)
  }

  def solve(size: Location, pieces: List[PieceCount]): List[Board] = {
    def recurse(initial: Board, pieces: List[PieceCount]): List[Board] = pieces match {
      case Nil ⇒ List(initial)
      case piece :: rest ⇒ placePieces(piece, initial).flatMap(b ⇒ recurse(b, rest))
    }

    recurse(EmptyBoard(size), pieces)
  }

}

// ✄----------------------------

// All of this is to get the valid boards and render them, using both optimised and unoptimised solutions

object ChessRunner extends App {
  def render(board: Board) = {
    for (row ← 0 until board.size.row) {
      for (column ← 0 until board.size.column)
        yield print(renderPiece(board.pieceAt(Location(row, column))))
      println
    }
    println
  }

  private def renderPiece(piece: Option[Piece]) =
    piece.map {
      _ match {
        case Rook ⇒ '\u2656'
        case Knight ⇒ '\u2658'
        case Bishop ⇒ '\u2657'
        case Queen ⇒ '\u2655'
        case King ⇒ '\u2654'
      }
    } getOrElse '\u00B7'

  private def renderSolutions(heading: String, solutions: Iterable[Board], startTime: Long, endTime: Long) {
    println(s"${heading}: There are ${solutions.size} solutions. Time taken: ${endTime - startTime} ms")
    for (solution ← solutions) {
      render(solution)
    }
  }

  val size = Location(4, 3) // the size of the board
  val pieces = List(Knight, Knight, Rook, King, Bishop) // the set of pieces to attempt to place

  // Get valid boards using the 'unoptimised' solution
  val unoptimisedStartTime = System.currentTimeMillis
  val unoptimisedSolutions = UnoptimisedChess.solve(size, pieces)
  val unoptimisedEndTime = System.currentTimeMillis
  renderSolutions("Unoptimised", unoptimisedSolutions, unoptimisedStartTime, unoptimisedEndTime)

  println("----")

  // Get valid boards using the 'optimised' solution
  val pieceCounts = pieces.groupBy(p ⇒ p).map(p ⇒ PieceCount(p._2.head, p._2.size)).toList
  val optimisedStartTime = System.currentTimeMillis
  val optimisedSolutions = OptimisedChess.solve(size, pieceCounts)
  val optimisedEndTime = System.currentTimeMillis
  renderSolutions("Optimised", optimisedSolutions, optimisedStartTime, optimisedEndTime)

  /* The above will print:
Unoptimised: There are 4 solutions. Time taken: 84 ms
♘·♔
♗··
♘··
·♖·

♔·♘
··♗
··♘
·♖·

·♖·
♘··
♗··
♘·♔

·♖·
··♘
··♗
♔·♘

----
Optimised: There are 4 solutions. Time taken: 8 ms
♘·♔
♗··
♘··
·♖·

♔·♘
··♗
··♘
·♖·

·♖·
♘··
♗··
♘·♔

·♖·
··♘
··♗
♔·♘
*/
}