object Chess {


  sealed trait Figure {
    def isThreat(p1: Pos, p2: Pos): Boolean

    def getColor: Color
  }

  sealed trait Color

  case object Black extends Color

  case object White extends Color

  case class Pos(x: Int, y: Int)


  case class Queen(color: Color) extends Figure {
    def isThreat(p1: Pos, p2: Pos): Boolean = {
      p1.x == p2.x || p1.y == p2.y || Math.abs(p1.x - p2.x) == Math.abs(p1.y - p2.y)
    }

    def getColor: Color = color
  }

  case class Pawn(color: Color) extends Figure {
    def isThreat(p1: Pos, p2: Pos): Boolean = {
      val isThreatToBlackByY = p1.y == p2.y + 1 && color == White
      val isThreatToWhiteByY = p1.y == p2.y - 1 && color == Black
      (isThreatToBlackByY || isThreatToWhiteByY) && Math.abs(p1.x - p2.x) == 1
    }
    def getColor: Color = color
  }

  type Board = List[(Pos, Figure)]


  def getBoards(figures: List[Figure], size: Int): List[Board] = {
    def extend(left: List[Figure]): List[Board] =
      left match {
        case Nil => List(List())
        case f :: fs =>
          for {
            board <- extend(fs)
            x <- 1 to size
            y <- 1 to size
            p = Pos(x, y)
            if board.forall {
              case (pos, figure) => p != pos && (!f.isThreat(p, pos) || f.getColor == figure.getColor)
            }
          } yield (p, f) :: board
      }
    extend(figures)
  }

  def main(args: Array[String]) {
    val figures = List(Pawn(Black), Pawn(White))
    val size = 2
    for (board <- getBoards(figures, size)) {
      println("----- board ------")
      printBoard(board, size)
    }
  }

  def printBoard(b: Board, size: Int) {
    for (x <- 1 to size) {
      for (y <- 1 to size)
        b.find {
          case (pos, _) => pos.x == x && pos.y == y
        } match {
          case None => print(" XX")
          case Some((pos, figure)) => {
            val symbol = figure match {
              case Queen(_) => "Q"
              case Pawn(_) => "P"
              case _ => "?"
            }
            val color = if (figure.getColor == White) "W"
            else "B"
            print(s" ${symbol}${color}")
          }
        }
      println()
    }
  }
}