package ru

import kotlin.math.absoluteValue

private var BOARD_SIZE = 15
private var counter = 0L

fun main(args: Array<String>) {
    if (!args.isEmpty()) BOARD_SIZE = args[0].toInt()
    val board = IntArray(BOARD_SIZE)
    val start = System.nanoTime()
    try {
        successfulComb(board, 0)
    } catch (e: Exception) {
    }
    val timeSpent = System.nanoTime() - start
    println("for board of size $BOARD_SIZE found $counter correct solutions in $timeSpent nanos, which is ${timeSpent / 1000000} millis, which is approx ${timeSpent / 1000000000} seconds")

}

tailrec fun successfulComb(body: IntArray, position: Int): IntArray {
    if (position >= BOARD_SIZE) {
        counter++
    } else {
        for (i in 0 until BOARD_SIZE) {
            if (!conflicts(body, i, position)) {
                body[position] = i
                return successfulComb(body, position + 1)
            }
        }
    }
    val newHead = prepareNextIteraion(body, position)
    return successfulComb(body, newHead)
}

private fun prepareNextIteraion(body: IntArray, position: Int): Int {
    var result = -1
    for (i in position - 1 downTo 0) {
        do {
            body[i]++
        } while (body[i] < BOARD_SIZE && conflicts(body, body[i], i))
        if (body[i] >= BOARD_SIZE) continue
        body.fill(0, i + 1, body.size)
        result = i + 1
        break
    }
    return if (result == -1) throw IllegalArgumentException() else result
}

fun conflicts(head: IntArray, position: Int, until: Int): Boolean {
    for (index in 0 until until) {
        if (head[index] == position || (head[index] - position).absoluteValue == (index - until).absoluteValue) return true
    }
    return false
}