LinkedInQueensGame.kt

class LinkedInQueensGame {
    val initialGrid = listOf(
        mutableListOf(0, 0, 0, 0, 0, 0, 0, 0, 1),
        mutableListOf(0, 0, 2, 2, 0, 0, 1, 1, 1),
        mutableListOf(0, 3, 3, 2, 0, 4, 4, 4, 0),
        mutableListOf(0, 0, 3, 2, 0, 0, 0, 4, 0),
        mutableListOf(0, 0, 3, 0, 0, 0, 0, 0, 0),
        mutableListOf(0, 0, 0, 0, 0, 6, 0, 0, 5),
        mutableListOf(0, 7, 7, 7, 0, 6, 5, 5, 5),
        mutableListOf(8, 7, 0, 0, 0, 6, 6, 0, 0),
        mutableListOf(8, 8, 8, 0, 0, 0, 0, 0, 0),
    )

    val expectedQueenCount = initialGrid.flatten().toSet().size

    val rows = initialGrid.size
    val cols = initialGrid[0].size

    val processedGrid = initialGrid.map { row ->
        row.map { Cell(cellType = it) }.toMutableList()
    }

    fun findSolution(row: Int = 0, col: Int = 0): Boolean {
        val availableSlots = findAvailableSlots(startRow = row, startCol = col)
        if (availableSlots.isEmpty()) {
            val foundSolution = countQueensInGrid() == expectedQueenCount
            if (foundSolution) {
                printSolution()
            }
            return foundSolution
        }

//        println(availableSlots.size)
        for (slot in availableSlots) {
            processedGrid[slot.row][slot.col].isEmpty = false
            if (findSolution(row = slot.row, col = slot.col)) {
                return true
            }
            processedGrid[slot.row][slot.col].isEmpty = true
        }

        return false
    }

    private fun findAvailableSlots(startRow: Int, startCol: Int): List<Slot> {
        val blockedCellTypes = mutableListOf<Int>()
        val blockedRows = mutableListOf<Int>()
        val blockedCols = mutableListOf<Int>()
        val blockedSlots = mutableSetOf<Slot>()
        for (row in 0 until rows) {
            for (col in 0 until cols) {
                val cell = processedGrid[row][col]
                if (cell.isEmpty.not()) {
                    blockedCellTypes.add(cell.cellType)
                    blockedRows.add(row)
                    blockedCols.add(col)
                    blockedSlots.add(Slot(row - 1, col - 1))
                    blockedSlots.add(Slot(row - 1, col + 1))
                    blockedSlots.add(Slot(row + 1, col - 1))
                    blockedSlots.add(Slot(row + 1, col + 1))
                }
            }
        }

        val availableSlots = mutableListOf<Slot>()
        for (row in startRow until rows) {
            for (col in 0 until cols) {
                val cell = processedGrid[row][col]
                if (cell.cellType in blockedCellTypes) continue
                if (row in blockedRows) continue
                if (col in blockedCols) continue
                if (Slot(row = row, col = col) in blockedSlots) continue
                availableSlots.add(Slot(row = row, col = col))
            }
        }

        return availableSlots
    }

    private fun countQueensInGrid(): Int {
        return processedGrid.flatten().filter { !it.isEmpty }.size
    }

    private fun printSolution() {
        val solution = processedGrid.joinToString("\n") { row ->
            row.joinToString(" ") {
                if (it.isEmpty) "${it.cellType}" else "Q"
            }
        }
        println(solution)
    }

    companion object {
        data class Cell(
            val cellType: Int,
            var isEmpty: Boolean = true
        )

        data class Slot(
            val row: Int,
            val col: Int
        )
    }
}

fun main() {
    val foundSolution = LinkedInQueensGame().findSolution()
    println(foundSolution)
}