How to resolve the algorithm Peaceful chess queen armies step by step in the Kotlin programming language

Published on 22 June 2024 08:30 PM
#Kotlin

How to resolve the algorithm Peaceful chess queen armies step by step in the Kotlin programming language

Table of Contents

Problem Statement

In chess, a queen attacks positions from where it is, in straight lines up-down and left-right as well as on both its diagonals. It attacks only pieces not of its own colour.

The goal of Peaceful chess queen armies is to arrange m black queens and m white queens on an n-by-n square grid, (the board), so that no queen attacks another of a different colour.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Peaceful chess queen armies step by step in the Kotlin programming language

Kotlin Code that Solves the N-Queens Problem

Overview: This code implements the N-Queens problem in Kotlin, which involves placing N queens on an NxN chessboard such that no two queens threaten each other.

Code Explanation:

1. Enums and Types:

  • The Piece enum represents the different pieces on the board: Empty, Black, White.
  • Position is a type alias for a pair of integers representing a position on the board.

2. place Function:

  • This function takes in the number of queens m, the size of the board n, and mutable lists for black and white queens.
  • It uses backtracking to place queens on the board.
  • It iterates through all positions on the board and checks if a queen can be placed without threatening any other queen.
  • If a queen can be placed, it adds it to the соответствующие list and flips a flag to indicate that it's placing white or black queens.
  • If placing a queen leads to a solution (when m becomes 0), it returns true.
  • Otherwise, it removes the last placed queen and continues backtracking.

3. isAttacking Function:

  • This checks if one queen is attacking another by checking if they are on the same row, column, or diagonal.

4. printBoard Function:

  • This function prints the board with the placed black and white queens.
  • It uses ASCII characters to represent different board squares and pieces.

5. main Function:

  • This function tests the code by trying to place different numbers of queens on boards of different sizes.
  • It calls the place function and prints the solution or a message if no solution exists.

How the Code Works:

  1. The code loops through a list of tuple (n, m), where n is the board size and m is the number of queens.
  2. For each tuple, it calls the place function to try and place queens on the board.
  3. If the place function succeeds, it prints the solution board using the printBoard function.
  4. If the place function fails, it prints a message indicating that no solution exists.

Example Output:

1 black and 1 white queens on a 2 x 2 board:
No solution exists.

1 black and 1 white queens on a 3 x 3 board:
◦ W B
B ◦ ◦
◦ B W

1 black and 1 white queens on a 4 x 4 board:
◦ W ◦ B
B ◦ ◦ ◦
◦ B W ◦
◦ ◦ ◦ W

Source code in the kotlin programming language

import kotlin.math.abs

enum class Piece {
    Empty,
    Black,
    White,
}

typealias Position = Pair<Int, Int>

fun place(m: Int, n: Int, pBlackQueens: MutableList<Position>, pWhiteQueens: MutableList<Position>): Boolean {
    if (m == 0) {
        return true
    }
    var placingBlack = true
    for (i in 0 until n) {
        inner@
        for (j in 0 until n) {
            val pos = Position(i, j)
            for (queen in pBlackQueens) {
                if (queen == pos || !placingBlack && isAttacking(queen, pos)) {
                    continue@inner
                }
            }
            for (queen in pWhiteQueens) {
                if (queen == pos || placingBlack && isAttacking(queen, pos)) {
                    continue@inner
                }
            }
            placingBlack = if (placingBlack) {
                pBlackQueens.add(pos)
                false
            } else {
                pWhiteQueens.add(pos)
                if (place(m - 1, n, pBlackQueens, pWhiteQueens)) {
                    return true
                }
                pBlackQueens.removeAt(pBlackQueens.lastIndex)
                pWhiteQueens.removeAt(pWhiteQueens.lastIndex)
                true
            }
        }
    }
    if (!placingBlack) {
        pBlackQueens.removeAt(pBlackQueens.lastIndex)
    }
    return false
}

fun isAttacking(queen: Position, pos: Position): Boolean {
    return queen.first == pos.first
            || queen.second == pos.second
            || abs(queen.first - pos.first) == abs(queen.second - pos.second)
}

fun printBoard(n: Int, blackQueens: List<Position>, whiteQueens: List<Position>) {
    val board = MutableList(n * n) { Piece.Empty }

    for (queen in blackQueens) {
        board[queen.first * n + queen.second] = Piece.Black
    }
    for (queen in whiteQueens) {
        board[queen.first * n + queen.second] = Piece.White
    }
    for ((i, b) in board.withIndex()) {
        if (i != 0 && i % n == 0) {
            println()
        }
        if (b == Piece.Black) {
            print("B ")
        } else if (b == Piece.White) {
            print("W ")
        } else {
            val j = i / n
            val k = i - j * n
            if (j % 2 == k % 2) {
                print("• ")
            } else {
                print("◦ ")
            }
        }
    }
    println('\n')
}

fun main() {
    val nms = listOf(
        Pair(2, 1), Pair(3, 1), Pair(3, 2), Pair(4, 1), Pair(4, 2), Pair(4, 3),
        Pair(5, 1), Pair(5, 2), Pair(5, 3), Pair(5, 4), Pair(5, 5),
        Pair(6, 1), Pair(6, 2), Pair(6, 3), Pair(6, 4), Pair(6, 5), Pair(6, 6),
        Pair(7, 1), Pair(7, 2), Pair(7, 3), Pair(7, 4), Pair(7, 5), Pair(7, 6), Pair(7, 7)
    )
    for ((n, m) in nms) {
        println("$m black and $m white queens on a $n x $n board:")
        val blackQueens = mutableListOf<Position>()
        val whiteQueens = mutableListOf<Position>()
        if (place(m, n, blackQueens, whiteQueens)) {
            printBoard(n, blackQueens, whiteQueens)
        } else {
            println("No solution exists.\n")
        }
    }
}

You may also check:How to resolve the algorithm Speech synthesis step by step in the Sidef programming language
You may also check:How to resolve the algorithm Exponentiation operator step by step in the Lua programming language
You may also check:How to resolve the algorithm Multifactorial step by step in the Plain TeX programming language
You may also check:How to resolve the algorithm Show ASCII table step by step in the BaCon programming language
You may also check:How to resolve the algorithm 15 puzzle game step by step in the Mathematica / Wolfram Language programming language