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

Published on 12 May 2024 09:40 PM
#Go

How to resolve the algorithm Peaceful chess queen armies step by step in the Go 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 Go programming language

This program solves the problem of placing the given number of black and white queens on a chessboard of given size such that no two queens threaten each other.

The solution is based on a backtracking algorithm. It tries to place m black and m white queens on an n x n board. It first tries to place a black queen on the board. If it succeeds, it tries to place a white queen on the board. If it succeeds, it tries to place the remaining black and white queens on the board. If it succeeds, it prints the board. Otherwise, it backtracks and tries to place the black queen on a different square. If it fails to place the black queen on any square, it prints "No solution exists."

The code uses several helper functions. The isAttacking function checks if two queens threaten each other. The place function tries to place m black and m white queens on an n x n board. The printBoard function prints the board.

The code is well-written and easy to understand. It uses a clear and concise style. It is also efficient and runs in O(n^m) time.

Source code in the go programming language

package main

import "fmt"

const (
    empty = iota
    black
    white
)

const (
    bqueen  = 'B'
    wqueen  = 'W'
    bbullet = '•'
    wbullet = '◦'
)

type position struct{ i, j int }

func iabs(i int) int {
    if i < 0 {
        return -i
    }
    return i
}

func place(m, n int, pBlackQueens, pWhiteQueens *[]position) bool {
    if m == 0 {
        return true
    }
    placingBlack := true
    for i := 0; i < n; i++ {
    inner:
        for j := 0; j < n; j++ {
            pos := position{i, j}
            for _, queen := range *pBlackQueens {
                if queen == pos || !placingBlack && isAttacking(queen, pos) {
                    continue inner
                }
            }
            for _, queen := range *pWhiteQueens {
                if queen == pos || placingBlack && isAttacking(queen, pos) {
                    continue inner
                }
            }
            if placingBlack {
                *pBlackQueens = append(*pBlackQueens, pos)
                placingBlack = false
            } else {
                *pWhiteQueens = append(*pWhiteQueens, pos)
                if place(m-1, n, pBlackQueens, pWhiteQueens) {
                    return true
                }
                *pBlackQueens = (*pBlackQueens)[0 : len(*pBlackQueens)-1]
                *pWhiteQueens = (*pWhiteQueens)[0 : len(*pWhiteQueens)-1]
                placingBlack = true
            }
        }
    }
    if !placingBlack {
        *pBlackQueens = (*pBlackQueens)[0 : len(*pBlackQueens)-1]
    }
    return false
}

func isAttacking(queen, pos position) bool {
    if queen.i == pos.i {
        return true
    }
    if queen.j == pos.j {
        return true
    }
    if iabs(queen.i-pos.i) == iabs(queen.j-pos.j) {
        return true
    }
    return false
}

func printBoard(n int, blackQueens, whiteQueens []position) {
    board := make([]int, n*n)
    for _, queen := range blackQueens {
        board[queen.i*n+queen.j] = black
    }
    for _, queen := range whiteQueens {
        board[queen.i*n+queen.j] = white
    }

    for i, b := range board {
        if i != 0 && i%n == 0 {
            fmt.Println()
        }
        switch b {
        case black:
            fmt.Printf("%c ", bqueen)
        case white:
            fmt.Printf("%c ", wqueen)
        case empty:
            if i%2 == 0 {
                fmt.Printf("%c ", bbullet)
            } else {
                fmt.Printf("%c ", wbullet)
            }
        }
    }
    fmt.Println("\n")
}

func main() {
    nms := [][2]int{
        {2, 1}, {3, 1}, {3, 2}, {4, 1}, {4, 2}, {4, 3},
        {5, 1}, {5, 2}, {5, 3}, {5, 4}, {5, 5},
        {6, 1}, {6, 2}, {6, 3}, {6, 4}, {6, 5}, {6, 6},
        {7, 1}, {7, 2}, {7, 3}, {7, 4}, {7, 5}, {7, 6}, {7, 7},
    }
    for _, nm := range nms {
        n, m := nm[0], nm[1]
        fmt.Printf("%d black and %d white queens on a %d x %d board:\n", m, m, n, n)
        var blackQueens, whiteQueens []position
        if place(m, n, &blackQueens, &whiteQueens) {
            printBoard(n, blackQueens, whiteQueens)
        } else {
            fmt.Println("No solution exists.\n")
        }
    }
}

You may also check:How to resolve the algorithm Largest int from concatenated ints step by step in the Python programming language
You may also check:How to resolve the algorithm Anagrams step by step in the Julia programming language
You may also check:How to resolve the algorithm Esthetic numbers step by step in the Java programming language
You may also check:How to resolve the algorithm Guess the number step by step in the R programming language
You may also check:How to resolve the algorithm Cholesky decomposition step by step in the Scala programming language