Algorithm

N-Queens Problem 目標是在一個大小為N×N的棋盤上放置N個皇后，使得這些皇后彼此不攻擊。

在這個問題中，皇后可以攻擊位於同一行、同一列或同一對角線上的其他皇后。

N-Queens問題的目標是找到一種方法，將N個皇后放置在棋盤上，使得它們不互相攻擊。

以下是解決N-Queens問題的一種方法：

1. 建立一個N×N的空棋盤，其中所有位置都初始化為空（沒有皇后）。
2. 從第一行開始，依次考慮每一個位置。
3. 對於每一個位置，檢查該位置是否可以放置一個皇后，而不會攻擊到之前已經放置的皇后。
4. 如果可以放置皇后，則將皇后放置在該位置，然後移動到下一行繼續操作。
5. 如果無法在該位置放置皇后，則返回到上一行，並嘗試下一個可行的位置。
6. 當成功放置了N個皇后且它們互不攻擊時，找到了一個解決方案。

需要注意的是，N-Queens問題可能有多個解決方案，也可能不存在解決方案，具體取決於N的值。

對於一些特定的N，可以使用遞歸或回溯算法來解決這個問題。

Code

// N Queen Problem in Kotlin
class NQueen {
    private val N = 8 // board size
    private val board = Array(N) { IntArray(N) }

    private fun printSolution(board: Array<IntArray>) {
        for (i in 0 until N) {
            for (j in 0 until N)
                print(" " + board[i][j]
                        + " ")
            println()
        }
    }

    private fun isSafe(board: Array<IntArray>, row: Int, col: Int): Boolean {
        var i: Int
        var j: Int

        /* Check this row on left side */
        i = 0
        while (i < col) {
            if (board[row][i] == 1)
                return false
            i++
        }

        /* Check upper diagonal on left side */
        i = row
        j = col
        while (i >= 0 && j >= 0) {
            if (board[i][j] == 1)
                return false
            i--
            j--
        }

        /* Check lower diagonal on left side */
        i = row
        j = col
        while (j >= 0 && i < N) {
            if (board[i][j] == 1)
                return false
            i++
            j--
        }

        return true
    }

    private fun solveNQUtil(board: Array<IntArray>, col: Int): Boolean {
        if (col >= N)
            return true

        for (i in 0 until N) {
            if (isSafe(board, i, col)) {
                board[i][col] = 1
                if (solveNQUtil(board, col + 1))
                    return true
                board[i][col] = 0 // BACKTRACK
            }
        }

        return false
    }

    fun solveNQ() {
        if (!solveNQUtil(board, 0)) {
            println("Solution does not exist")
            return
        }
        printSolution(board)
    }

    companion object {
        @JvmStatic
        fun main(args: Array<String>) {
            val Queen = NQueen()
            Queen.solveNQ()
        }
    }
}

// main function
fun main(args: Array<String>) {
    val Queen = NQueen()
    Queen.solveNQ()
}

所有 Code 可以在 Github 找到 ～

感謝各位讀者，我們明天見！