I've written a short program to find solutions to the 36 Cube puzzle.
I'm trying to break away from my normal Java / imperative style, and would like some feedback on how I'm doing.
Puzzle.scala
package cube36
/**
* An immutable class representing the state of a 36 Cube puzzle
*/
case class CubePuzzle(val board: Board, val availablePieces: List[Piece]) {
/**
* Add a piece to this puzzle, to create new instance of the puzzle
* @param rowNum row to add piece to
* @param colNum column to add piece to
* @param piece piece to add
* @param checkSuitable check if the position will accept this piece (default true if omitted)
* @return a new puzzle instance, with the specified piece added
*/
def addPiece(rowNum: Int, colNum: Int, piece: Piece, checkSuitable: Boolean = true): CubePuzzle = {
val newBoard = board.addPiece(rowNum, colNum, piece,checkSuitable)
CubePuzzle(newBoard, availablePieces.filterNot(_ == piece))
}
/**
* Find solutions to the puzzle which satisfy the rules
* @param solutionsSoFar
* @return a list of all valid solutions
*/
def solve(solutionsSoFar: List[Board]=List[Board]()): List[Board] = {
if (this.availablePieces.size == 0) this.board :: solutionsSoFar
else {
val nextPiece = availablePieces.head
val availableSpots = board.spaces.filter(space => board.suitable(space, nextPiece))
val sols = for (spot <- availableSpots) yield addPiece(spot._1, spot._2, nextPiece,false).solve(solutionsSoFar)
sols.flatten.toList
}
}
}
object CubePuzzle {
// Have to put two pieces in 'special' positions, where they wouldn't be expected to fit.
// No solution otherwise.
private val startingBoard = Board().addPiece(1, 2, Piece(Yellow, 5),false).addPiece(3, 2, Piece(Orange, 6),false)
private val availablePieces = (List[Piece]() ++
getPieces(Yellow, 6) ++
getPieces(Red, 6) ++
getPieces(Purple, 6) ++
getPieces(Blue, 6) ++
getPieces(Green, 6) ++
getPieces(Orange, 6)).
filterNot(_ == Piece(Yellow, 5)).
filterNot(_ == Piece(Orange, 6))
private def getPieces(colour: Colour, maxSize: Int): Set[Piece] = (for (x <- 1 to 6) yield Piece(colour, x)).toSet
def apply() = new CubePuzzle(startingBoard, availablePieces)
}
sealed trait Colour;
case object Red extends Colour;
case object Purple extends Colour;
case object Blue extends Colour;
case object Green extends Colour;
case object Yellow extends Colour;
case object Orange extends Colour;
case class Piece(val colour: Colour, val size: Int) {
require(size <= 6 && size >= 1,"Piece size out of range")
override def toString: String = colour.toString().head.toString + size.toString
}
Board.scala
package cube36
case class Board(val placedPieces: IndexedSeq[IndexedSeq[Option[Piece]]] /*rows of cols*/ ) {
val row1Heights = List[Int](1, 3, 4, 5, 2, 0)
val row2Heights = List[Int](2, 5, 0, 4, 1, 3)
val row3Heights = List[Int](0, 1, 3, 2, 5, 4)
val row4Heights = List[Int](5, 4, 1, 3, 0, 2)
val row5Heights = List[Int](4, 2, 5, 0, 3, 1)
val row6Heights = List[Int](3, 0, 2, 1, 4, 5)
val contours = List[List[Int]](row1Heights, row2Heights, row3Heights, row4Heights, row5Heights, row6Heights)
private[cube36] def spaces: Seq[(Int, Int)] = for (row <- 0 to 5; col <- 0 to 5; if (placedPieces(row)(col)).isEmpty) yield (row, col)
private[cube36] def suitable(space: (Int, Int), piece: Piece): Boolean = {
lazy val spaceEmpty = placedPieces(space._1)(space._2).isEmpty
lazy val height = contours(space._1)(space._2)
lazy val rightHeight = height + piece.size == 6
lazy val colour = piece.colour
lazy val cl = placedPieces.map(row => row(space._2))
lazy val matches = cl.map(x => x.map(p => p.colour == colour))
lazy val colourAlreadyInCol = matches.contains(Some(true))
lazy val rw = placedPieces(space._1)
lazy val rmatches = rw.map(x => x.map(p => p.colour == colour))
lazy val colourAlreadyInRow = rmatches.contains(Some(true))
val unsuitable = (!spaceEmpty) || (!rightHeight) || colourAlreadyInCol || colourAlreadyInRow
!unsuitable
}
private[cube36] def addPiece(rowNum: Int, colNum: Int, piece: Piece, checkSuitable: Boolean = true): Board = {
if (checkSuitable && !suitable((rowNum, colNum), piece)) throw new IllegalArgumentException("Not suitable for this poition")
val newRow = placedPieces(rowNum).updated(colNum, Some(piece))
Board(placedPieces.updated(rowNum, newRow))
}
private[this] def rowString(row:IndexedSeq[Option[Piece]]):String = {
val r=for(p<-row) yield p match {
case Some(pc) => "|" + pc
case None => " _ "
}
r.foldLeft("")((a,b)=>a+b) + "|"
}
override def toString: String = {
val border = "==================="
val content = for (row <- placedPieces) yield rowString(row)
val folded=content.foldLeft(border)((a,b)=> a +"\n" + b)
folded + "\n" + border
}
}
object Board {
def apply(): Board = {
val emptyRow = IndexedSeq[Option[Piece]](None, None, None, None, None, None)
val emptyPieces = IndexedSeq(emptyRow, emptyRow, emptyRow, emptyRow, emptyRow, emptyRow)
Board(emptyPieces)
}
}
