This is a Kotlin implementation of a 15 Puzzle solver using A*. As an example, I've listed all possible positions for a 2x2 puzzle.

AStar15Puzzle.kt

enum class Direction {
    NORTH,
    SOUTH,
    EAST,
    WEST,
}

/**
 * A "move" is a starting position and a direction in which to move.
 */
data class Move(val row: Int, val column: Int, val direction: Direction) {
    /**
     * The complement of a move, is it's "undo" move.
     */
    fun complement(): Move {
        return when(direction) {
            Direction.NORTH -> Move(row-1, column, Direction.SOUTH)
            Direction.SOUTH -> Move(row+1, column, Direction.NORTH)
            Direction.EAST -> Move(row, column+1, Direction.WEST)
            Direction.WEST -> Move(row, column-1, Direction.EAST)
        }
    }
}

typealias Board = MutableList<MutableList<Int?>>

/**
 * Puzzle class with a constructor that takes a [Board].
 */
class Puzzle(initial: Board) {
    var puzzle = initial
    val size = initial.count()
    var history: Move? = null
    var numMoves = 0

    /**
     * Return the location of the empty space in the puzzle.
     */
    fun findEmpty(board: Board): Pair<Int, Int>? {
        for (i in 0 until size) {
            for (j in 0 until size) {
                if (board[i][j] == null) {
                    return Pair(i,j)
                }
            }
        }
        return null
    }

    /**
     * Return a list of possible moves.
     */
    fun possibleMoves(board: Board): List<Move> {
        var result = mutableListOf<Move>()
        val empty = findEmpty(board) ?: return result
        val row = empty.component1()
        val column = empty.component2()
        when (row) {
            0 -> result.add(Move(row+1, column, Direction.NORTH))
            size-1 -> result.add(Move(row-1, column, Direction.SOUTH))
            else -> {
                result.add(Move(row-1, column, Direction.SOUTH))
                result.add(Move(row+1, column, Direction.NORTH))
            }
        }
        when (column) {
            0 -> result.add(Move(row, column+1, Direction.WEST))
            size-1 -> result.add(Move(row, column-1, Direction.EAST))
            else -> {
                result.add(Move(row, column-1, Direction.EAST))
                result.add(Move(row, column+1, Direction.WEST))
            }
        }
        if (history != null) {
            val lastMove = history!!.complement()
            result = result.filter { it != lastMove }.toMutableList()
        }
        return result
    }

    /**
     * Higher level logic for moving a tile.
     */
    fun moveTile(move: Move) {
        if (!isLegal(move, puzzle)) return
        puzzle = moveTileLogic(move, puzzle)
        history = move
        numMoves += 1
    }

    /**
     * Lower level logic for moving a tile into the null location.
     */
    fun moveTileLogic(move: Move, board: Board): Board{
        val row = move.row
        val column = move.column
        val direction = move.direction
        val tile = board[row][column]
        when (direction) {
            Direction.NORTH -> board[row-1][column] = tile
            Direction.SOUTH -> board[row+1][column] = tile
            Direction.EAST -> board[row][column+1] = tile
            Direction.WEST -> board[row][column-1] = tile
        }
        board[row][column] = null
        return board
    }

    /**
     * Return true if a move is legal, otherwise false.
     */
    fun isLegal(move: Move, board: Board): Boolean {
        val row = move.row
        val column = move.column
        val direction = move.direction
        if ((row == 0) && (direction == Direction.NORTH)) return false
        if ((row == size-1) && (direction == Direction.SOUTH)) return false
        if ((column == 0) && (direction == Direction.WEST)) return false
        if ((column == size-1) && (direction == Direction.EAST)) return false
        when (direction) {
            Direction.NORTH -> if (board[row-1][column] != null) return false
            Direction.SOUTH -> if (board[row+1][column] != null) return false
            Direction.EAST -> if (board[row][column+1] != null) return false
            Direction.WEST -> if (board[row][column-1] != null) return false
        }
        return true
    }

    /**
     * Cost function for A* search. Adds 1 for each tile that is out or order.
     */
    fun numberOutOfOrder(board: Board): Int {
        var result = 0
        var square = 0
        for (i in 0 until size) {
            for (j in 0 until size) {
                square = i*size + j
                if (board[i][j] != square) {
                    result += 1
                }
            }
        }
        if (board[0][0] == null) {
            result -= 1
        }
        return result
    }

    /**
     * This is the cost function [numMoves] plus the heuristic function
     * [numberOutOfOrder]. This sum is the ranking used for A* search.
     */
    fun rankMove(move: Move, board: Board): Int {
        var tmp = MutableList(3) { MutableList<Int?>(3) { null } }
        for (i in 0 until size) {
            for (j in 0 until size) {
                tmp[i][j] = board[i][j]
            }
        }
        tmp = moveTileLogic(move, tmp)
        return numberOutOfOrder(tmp) + numMoves
    }

    /**
     * Heuristic function that estimates how far we are from the goal state.
     */
    fun makeMinimalMove() {
        val possible = possibleMoves(puzzle)
        val rank = possible.map { rankMove(it, puzzle) }
        var minIndex = 0
        var minRanking = rank[0]
        println(puzzle)
        for (i in 0 until possible.count()) {
            println("    Rank: ${rank[i]} ${possible[i]}")
        }
        for ((index, ranking) in rank.withIndex()) {
            if (ranking < minRanking) {
                minIndex = index
            }
        }
        moveTile(possible[minIndex])
    }
}


fun main() {
    val ITERATION_LIMIT = 10000
    println("A* Search")

    // val p = mutableListOf(mutableListOf(null, 1), mutableListOf(2, 3)) as Board // √
    // val p = mutableListOf(mutableListOf(null, 1), mutableListOf(3, 2)) as Board // no solution
    // val p = mutableListOf(mutableListOf(null, 2), mutableListOf(1, 3)) as Board // no solution
    // val p = mutableListOf(mutableListOf(null, 2), mutableListOf(3, 1)) as Board // √
    // val p = mutableListOf(mutableListOf(null, 3), mutableListOf(1, 2)) as Board // √
    // val p = mutableListOf(mutableListOf(null, 3), mutableListOf(2, 1)) as Board // no solution
    // val p = mutableListOf(mutableListOf(1, null), mutableListOf(2, 3)) as Board // √
    // val p = mutableListOf(mutableListOf(1, null), mutableListOf(3, 2)) as Board // no solution
    // val p = mutableListOf(mutableListOf(2, null), mutableListOf(1, 3)) as Board // no solution
    // val p = mutableListOf(mutableListOf(2, null), mutableListOf(3, 1)) as Board // √
    // val p = mutableListOf(mutableListOf(3, null), mutableListOf(1, 2)) as Board // √
    // val p = mutableListOf(mutableListOf(3, null), mutableListOf(2, 1)) as Board // no solution
    // val p = mutableListOf(mutableListOf(1, 2), mutableListOf(null, 3)) as Board // no solution
    // val p = mutableListOf(mutableListOf(1, 3), mutableListOf(null, 2)) as Board // √
    // val p = mutableListOf(mutableListOf(2, 1), mutableListOf(null, 3)) as Board // √
    // val p = mutableListOf(mutableListOf(2, 3), mutableListOf(null, 1)) as Board // no solution
    // val p = mutableListOf(mutableListOf(3, 1), mutableListOf(null, 2)) as Board // no solution
    // val p = mutableListOf(mutableListOf(3, 2), mutableListOf(null, 1)) as Board // √
    // val p = mutableListOf(mutableListOf(1, 2), mutableListOf(3, null)) as Board // no solution
    // val p = mutableListOf(mutableListOf(1, 3), mutableListOf(2, null)) as Board // √
    val p = mutableListOf(mutableListOf(2, 1), mutableListOf(3, null)) as Board // √
    // val p = mutableListOf(mutableListOf(2, 3), mutableListOf(1, null)) as Board // no solution
    // val p = mutableListOf(mutableListOf(3, 1), mutableListOf(2, null)) as Board // no solution
    // val p = mutableListOf(mutableListOf(3, 2), mutableListOf(1, null)) as Board // √

    val puzzle = Puzzle(p)
    var count = 0
    while (puzzle.numberOutOfOrder(puzzle.puzzle) > 0) {
        count += 1
        println("\n>>> $count")
        puzzle.makeMinimalMove()
        if (count > ITERATION_LIMIT) break
    }
    count += 1
    println("\n>>> $count")
    puzzle.makeMinimalMove()
}