Created
August 31, 2013 21:14
-
-
Save lancewalton/6400667 to your computer and use it in GitHub Desktop.
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…
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
♘·♔ | |
♗·· | |
♘·· | |
·♖· | |
♔·♘ | |
··♗ | |
··♘ | |
·♖· | |
·♖· | |
♘·· | |
♗·· | |
♘·♔ | |
·♖· | |
··♘ | |
··♗ | |
♔·♘ | |
*/ | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment