Solving the Wims Mat Puzzle

Wims-Mat-Puzzle.kt

package com.wimpuzzle

import java.util.*

fun main(args: Array<String>) {
    val solver = Solver()
    solver.solve()
}

class Piece(val positions: Array<Array<Array<Int>>>,val id:Int,var orientation: Int=0){
    override fun toString():String="$id$orientation"
}
data class Position(val r:Int,val c:Int)

class Solver {
    val empty = Piece(emptyArray(),0)
    var nb = 0
    val pieces = arrayOf(
            Piece(arrayOf(
                    arrayOf(
                            arrayOf(1, 2, 1, 2)
                    ),
                    arrayOf(
                            arrayOf(2, 1, 2, 1)
                    )
            ),1),
            Piece(arrayOf(
                    arrayOf(
                            arrayOf(1),
                            arrayOf(2),
                            arrayOf(1),
                            arrayOf(2)
                    ),
                    arrayOf(
                            arrayOf(2),
                            arrayOf(1),
                            arrayOf(2),
                            arrayOf(1)
                    )
            ),2),
            Piece(arrayOf(
                    arrayOf(
                            arrayOf(0,2),
                            arrayOf(2,1),
                            arrayOf(1,0)
                    ),
                    arrayOf(
                            arrayOf(2,0),
                            arrayOf(1,2),
                            arrayOf(0,1)
                    ),
                    arrayOf(
                            arrayOf(1,0),
                            arrayOf(2,1),
                            arrayOf(0,2)
                    ),
                    arrayOf(
                            arrayOf(0,1),
                            arrayOf(1,2),
                            arrayOf(2,0)
                    )
            ),3),
            Piece(arrayOf(
                    arrayOf(
                            arrayOf(2,1,2),
                            arrayOf(0,0,1)
                    ),
                    arrayOf(
                            arrayOf(0,0,1),
                            arrayOf(2,1,2)
                    ),
                    arrayOf(
                            arrayOf(2,1,2),
                            arrayOf(1,0,0)
                    ),
                    arrayOf(
                            arrayOf(1,0,0),
                            arrayOf(2,1,2)
                    )
            ),4),
            Piece(arrayOf(
                    arrayOf(
                            arrayOf(2,0),
                            arrayOf(1,0),
                            arrayOf(2,1)
                    ),
                    arrayOf(
                            arrayOf(2,1),
                            arrayOf(1,0),
                            arrayOf(2,0)
                    ),
                    arrayOf(
                            arrayOf(0,2),
                            arrayOf(0,1),
                            arrayOf(1,2)
                    ),
                    arrayOf(
                            arrayOf(1,2),
                            arrayOf(0,1),
                            arrayOf(0,2)
                    )
            ),5),
            Piece(arrayOf(
                    arrayOf(
                        arrayOf(2,1),
                        arrayOf(1,2)
                    ),
                    arrayOf(
                            arrayOf(1,2),
                            arrayOf(2,1)
                    )
            ),6),
            Piece(arrayOf(
                    arrayOf(
                            arrayOf(1,2),
                            arrayOf(2,0),
                            arrayOf(1,0)
                    ),
                    arrayOf(
                            arrayOf(2,1),
                            arrayOf(0,2),
                            arrayOf(0,1)
                    ),
                    arrayOf(
                            arrayOf(1,0),
                            arrayOf(2,0),
                            arrayOf(1,2)
                    ),
                    arrayOf(
                            arrayOf(0,1),
                            arrayOf(0,2),
                            arrayOf(2,1)
                    )
            ),7),
            Piece(arrayOf(
                    arrayOf(
                            arrayOf(0,1,2),
                            arrayOf(1,2,0)
                    ),
                    arrayOf(
                            arrayOf(2,1,0),
                            arrayOf(0,2,1)
                    ),
                    arrayOf(
                            arrayOf(1,2,0),
                            arrayOf(0,1,2)
                    ),
                    arrayOf(
                            arrayOf(0,2,1),
                            arrayOf(2,1,0)
                    )
            ),8),
            Piece(arrayOf(
                    arrayOf(
                            arrayOf(1,2,1),
                            arrayOf(0,0,2)
                    ),
                    arrayOf(
                            arrayOf(1,2,1),
                            arrayOf(2,0,0)
                    ),
                    arrayOf(
                            arrayOf(2,0,0),
                            arrayOf(1,2,1)
                    ),
                    arrayOf(
                            arrayOf(0,0,2),
                            arrayOf(1,2,1)
                    )
            ),9)
    )

    val board = Array(6, { Array(6, { empty }) })

    fun canPlacePiece(piece: Array<Array<Int>>,positon:Position):Boolean{
        if (positon.r<0) return false
        if (positon.c<0) return false
        if (positon.r+piece.lastIndex>board.lastIndex) return false
        if (positon.c+(piece.firstOrNull()?.lastIndex?:0) > board.firstOrNull()?.lastIndex?:0) return false
        for(r in 0 .. piece.lastIndex){
            for(c in 0 .. piece[r].lastIndex){
                val color = (r + c) % 2 + 1
                if (piece[r][c]!=0 && ( piece[r][c]!=color || board[positon.r+r][positon.c+c]!=empty)){
                    return false
                }
            }
        }
        return true
    }
    fun placePiece(piece: Piece,orientation:Int,positon:Position){
        piece.orientation = orientation
        for(r in 0 .. piece.positions[orientation].lastIndex) {
            for (c in 0 .. piece.positions[orientation][r].lastIndex) {
                if(piece.positions[orientation][r][c]!=0) {
                    board[positon.r + r][positon.c + c] = piece
                }
            }
        }
    }
    fun removePiece(piece: Piece,orientation:Int,positon:Position){
        for(r in 0 .. piece.positions[orientation].lastIndex) {
            for (c in 0 .. piece.positions[orientation][r].lastIndex) {
                if(piece.positions[orientation][r][c]!=0) {
                    board[positon.r + r][positon.c + c] = empty
                }
            }
        }
    }
    fun getNextFreePostion():Optional<Position>{
        for(r in 0 .. board.lastIndex){
            for(c in 0 .. board[r].lastIndex){
                if (board[r][c]==empty) return Optional.of(Position(r,c))
            }
        }
        return Optional.empty<Position>()
    }
    fun solve(){
        val set = sortedSetOf(kotlin.Comparator { a:Piece, b:Piece -> a.id - b.id  },*pieces)
        solveR(set)
    }

    fun displayBoard(){
        println(board.joinToString("\n") { it.joinToString() })
    }

    fun solveR(set:SortedSet<Piece>):Boolean{
        if(set.isEmpty()){
            println("Solved it. Solution number $nb")
            displayBoard()
            nb++
            return true
        }
        set.toList().forEach { piece ->
            for(orientation in 0..piece.positions.lastIndex){
                val pieceMask  = piece.positions[orientation]
                val nextPosition = getNextFreePostion()
                if(!nextPosition.isPresent){
                    return false
                }
                val position = nextPosition.get()
                val idx = pieceMask.firstOrNull()?.indexOfFirst { it!=0 }?:-1
                if (idx==-1) continue
                val effectivePosition = position.copy(position.r,position.c-idx)
                if(canPlacePiece(pieceMask, effectivePosition)){
                    set.remove(piece)
                    placePiece(piece,orientation,effectivePosition)
                    solveR(set)
                    removePiece(piece,orientation,effectivePosition)
                    set.add(piece)
                }
            }
        }
        return false
    }
}