8-queens-annealing.kt

import kotlin.math.pow
import kotlin.random.Random

const val boardSize = 40
const val tries = 100

val random = Random(System.currentTimeMillis())

fun cost(solution: Array<Int>): Int {
    var cost = 0
    for (i in 0 until boardSize) {
        for (j in (i + 1) until boardSize) {
            if (solution[i] == solution[j]) cost++
            if (solution[i] == solution[j] + (j - i)) cost++
            if (solution[i] == solution[j] - (j - i)) cost++
        }
    }
    return cost
}

fun neighbor(solution: Array<Int>) : Array<Int> {
    val column = random.nextInt(boardSize)
    val row = random.nextInt(boardSize)
    return solution.copyOf().apply { this[column] = row }
}

fun accept(actual: Array<Int>, neighbor: Array<Int>, temp: Double) : Boolean {
    val diff = cost(neighbor) - cost(actual)
    if (diff < 0) { return true }
    return random.nextDouble() < Math.E.pow(-diff / temp)
}

fun main() {
    var current = Array(boardSize) { random.nextInt(boardSize) }

    val startAt = System.currentTimeMillis()
    for (j in 0 until tries) {
        for (i in 0 until 10000) {
            val temperature = 100.0 / (i + 100)
            val neighbor = neighbor(current)
            if (accept(current, neighbor, temperature)) {
                current = neighbor
            }

            if (cost(current) == 0) {
                println("Try #$j")
                println("Solution \"${current.joinToString(", ")}\" found in $i iterations and ${System.currentTimeMillis() - startAt}ms")
                return
            }
        }
    }
}