Peaceful chess queen armies
You are encouraged to solve this task according to the task description, using any language you may know.
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.
- Task
- Create a routine to represent two-colour queens on a 2-D board. (Alternating black/white background colours, Unicode chess pieces and other embellishments are not necessary, but may be used at your discretion).
- Create a routine to generate at least one solution to placing
m
equal numbers of black and white queens on ann
square board. - Display here results for the
m=4, n=5
case.
- References
- Peaceably Coexisting Armies of Queens (Pdf) by Robert A. Bosch. Optima, the Mathematical Programming Socity newsletter, issue 62.
- A250000 OEIS
C
<lang c>#include <math.h>
- include <stdbool.h>
- include <stdio.h>
- include <stdlib.h>
enum Piece {
Empty, Black, White,
};
typedef struct Position_t {
int x, y;
} Position;
///////////////////////////////////////////////
struct Node_t {
Position pos; struct Node_t *next;
};
void releaseNode(struct Node_t *head) {
if (head == NULL) return;
releaseNode(head->next); head->next = NULL;
free(head);
}
typedef struct List_t {
struct Node_t *head; struct Node_t *tail; size_t length;
} List;
List makeList() {
return (List) { NULL, NULL, 0 };
}
void releaseList(List *lst) {
if (lst == NULL) return;
releaseNode(lst->head); lst->head = NULL; lst->tail = NULL;
}
void addNode(List *lst, Position pos) {
struct Node_t *newNode;
if (lst == NULL) { exit(EXIT_FAILURE); }
newNode = malloc(sizeof(struct Node_t)); if (newNode == NULL) { exit(EXIT_FAILURE); }
newNode->next = NULL; newNode->pos = pos;
if (lst->head == NULL) { lst->head = lst->tail = newNode; } else { lst->tail->next = newNode; lst->tail = newNode; }
lst->length++;
}
void removeAt(List *lst, size_t pos) {
if (lst == NULL) return;
if (pos == 0) { struct Node_t *temp = lst->head;
if (lst->tail == lst->head) { lst->tail = NULL; }
lst->head = lst->head->next; temp->next = NULL;
free(temp); lst->length--; } else { struct Node_t *temp = lst->head; struct Node_t *rem; size_t i = pos;
while (i-- > 1) { temp = temp->next; }
rem = temp->next; if (rem == lst->tail) { lst->tail = temp; }
temp->next = rem->next;
rem->next = NULL; free(rem);
lst->length--; }
}
///////////////////////////////////////////////
bool isAttacking(Position queen, Position pos) {
return queen.x == pos.x || queen.y == pos.y || abs(queen.x - pos.x) == abs(queen.y - pos.y);
}
bool place(int m, int n, List *pBlackQueens, List *pWhiteQueens) {
struct Node_t *queenNode; bool placingBlack = true; int i, j;
if (pBlackQueens == NULL || pWhiteQueens == NULL) { exit(EXIT_FAILURE); }
if (m == 0) return true; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { Position pos = { i, j };
queenNode = pBlackQueens->head; while (queenNode != NULL) { if ((queenNode->pos.x == pos.x && queenNode->pos.y == pos.y) || !placingBlack && isAttacking(queenNode->pos, pos)) { goto inner; } queenNode = queenNode->next; }
queenNode = pWhiteQueens->head; while (queenNode != NULL) { if ((queenNode->pos.x == pos.x && queenNode->pos.y == pos.y) || placingBlack && isAttacking(queenNode->pos, pos)) { goto inner; } queenNode = queenNode->next; }
if (placingBlack) { addNode(pBlackQueens, pos); placingBlack = false; } else { addNode(pWhiteQueens, pos); if (place(m - 1, n, pBlackQueens, pWhiteQueens)) { return true; } removeAt(pBlackQueens, pBlackQueens->length - 1); removeAt(pWhiteQueens, pWhiteQueens->length - 1); placingBlack = true; }
inner: {} } } if (!placingBlack) { removeAt(pBlackQueens, pBlackQueens->length - 1); } return false;
}
void printBoard(int n, List *pBlackQueens, List *pWhiteQueens) {
size_t length = n * n; struct Node_t *queenNode; char *board; size_t i, j, k;
if (pBlackQueens == NULL || pWhiteQueens == NULL) { exit(EXIT_FAILURE); }
board = calloc(length, sizeof(char)); if (board == NULL) { exit(EXIT_FAILURE); }
queenNode = pBlackQueens->head; while (queenNode != NULL) { board[queenNode->pos.x * n + queenNode->pos.y] = Black; queenNode = queenNode->next; }
queenNode = pWhiteQueens->head; while (queenNode != NULL) { board[queenNode->pos.x * n + queenNode->pos.y] = White; queenNode = queenNode->next; }
for (i = 0; i < length; i++) { if (i != 0 && i % n == 0) { printf("\n"); } switch (board[i]) { case Black: printf("B "); break; case White: printf("W "); break; default: j = i / n; k = i - j * n; if (j % 2 == k % 2) { printf(" "); } else { printf("# "); } break; } }
printf("\n\n");
}
void test(int n, int q) {
List blackQueens = makeList(); List whiteQueens = makeList();
printf("%d black and %d white queens on a %d x %d board:\n", q, q, n, n); if (place(q, n, &blackQueens, &whiteQueens)) { printBoard(n, &blackQueens, &whiteQueens); } else { printf("No solution exists.\n\n"); }
releaseList(&blackQueens); releaseList(&whiteQueens);
}
int main() {
test(2, 1);
test(3, 1); test(3, 2);
test(4, 1); test(4, 2); test(4, 3);
test(5, 1); test(5, 2); test(5, 3); test(5, 4); test(5, 5);
test(6, 1); test(6, 2); test(6, 3); test(6, 4); test(6, 5); test(6, 6);
test(7, 1); test(7, 2); test(7, 3); test(7, 4); test(7, 5); test(7, 6); test(7, 7);
return EXIT_SUCCESS;
}</lang>
- 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: B # # W # 2 black and 2 white queens on a 3 x 3 board: No solution exists. 1 black and 1 white queens on a 4 x 4 board: B # # # W # # # # 2 black and 2 white queens on a 4 x 4 board: B # # # W B # # # W 3 black and 3 white queens on a 4 x 4 board: No solution exists. 1 black and 1 white queens on a 5 x 5 board: B # # # W # # # # # # # # 2 black and 2 white queens on a 5 x 5 board: B # # B # W # W # # # # # # 3 black and 3 white queens on a 5 x 5 board: B # # B # W # W # # # B # W # 4 black and 4 white queens on a 5 x 5 board: B B # # B W # W # # # B W # W # 5 black and 5 white queens on a 5 x 5 board: No solution exists. 1 black and 1 white queens on a 6 x 6 board: B # # # # W # # # # # # # # # # # # # 2 black and 2 white queens on a 6 x 6 board: B # # B # # W # W # # # # # # # # # # # 3 black and 3 white queens on a 6 x 6 board: B # # B B # W # W # # # # # # W # # # # # 4 black and 4 white queens on a 6 x 6 board: B # # B B # W # W # # # # # B # W W # # # # 5 black and 5 white queens on a 6 x 6 board: B # B # # # B # B W # # # W W # # # B W W # 6 black and 6 white queens on a 6 x 6 board: No solution exists. 1 black and 1 white queens on a 7 x 7 board: B # # # # W # # # # # # # # # # # # # # # # # # # 2 black and 2 white queens on a 7 x 7 board: B # # B # # W # W # # # # # # # # # # # # # # # # # 3 black and 3 white queens on a 7 x 7 board: B # # B # # W # W B # # # # W # # # # # # # # # # # # 4 black and 4 white queens on a 7 x 7 board: B # # B # # W # W B # # B # # W # W # # # # # # # # # # 5 black and 5 white queens on a 7 x 7 board: B # # B # # W # W B # # B # # W # W B # # # # W # # # # # 6 black and 6 white queens on a 7 x 7 board: B # # B # # W # W B # # B # # W # W B # # B # # W # W # # # 7 black and 7 white queens on a 7 x 7 board: B # B # B # B # B # B # # B # W # W # # W # # W # # W # W W #
C#
<lang csharp>using System; using System.Collections.Generic;
namespace PeacefulChessQueenArmies {
using Position = Tuple<int, int>;
enum Piece { Empty, Black, White }
class Program { static bool IsAttacking(Position queen, Position pos) { return queen.Item1 == pos.Item1 || queen.Item2 == pos.Item2 || Math.Abs(queen.Item1 - pos.Item1) == Math.Abs(queen.Item2 - pos.Item2); }
static bool Place(int m, int n, List<Position> pBlackQueens, List<Position> pWhiteQueens) { if (m == 0) { return true; } bool placingBlack = true; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { var pos = new Position(i, j); foreach (var queen in pBlackQueens) { if (queen.Equals(pos) || !placingBlack && IsAttacking(queen, pos)) { goto inner; } } foreach (var queen in pWhiteQueens) { if (queen.Equals(pos) || placingBlack && IsAttacking(queen, pos)) { goto inner; } } if (placingBlack) { pBlackQueens.Add(pos); placingBlack = false; } else { pWhiteQueens.Add(pos); if (Place(m - 1, n, pBlackQueens, pWhiteQueens)) { return true; } pBlackQueens.RemoveAt(pBlackQueens.Count - 1); pWhiteQueens.RemoveAt(pWhiteQueens.Count - 1); placingBlack = true; } inner: { } } } if (!placingBlack) { pBlackQueens.RemoveAt(pBlackQueens.Count - 1); } return false; }
static void PrintBoard(int n, List<Position> blackQueens, List<Position> whiteQueens) { var board = new Piece[n * n];
foreach (var queen in blackQueens) { board[queen.Item1 * n + queen.Item2] = Piece.Black; } foreach (var queen in whiteQueens) { board[queen.Item1 * n + queen.Item2] = Piece.White; }
for (int i = 0; i < board.Length; i++) { if (i != 0 && i % n == 0) { Console.WriteLine(); } switch (board[i]) { case Piece.Black: Console.Write("B "); break; case Piece.White: Console.Write("W "); break; case Piece.Empty: int j = i / n; int k = i - j * n; if (j % 2 == k % 2) { Console.Write(" "); } else { Console.Write("# "); } break; } }
Console.WriteLine("\n"); }
static void Main() { var nms = new 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 (int i = 0; i < nms.GetLength(0); i++) { Console.WriteLine("{0} black and {0} white queens on a {1} x {1} board:", nms[i, 1], nms[i, 0]); List<Position> blackQueens = new List<Position>(); List<Position> whiteQueens = new List<Position>(); if (Place(nms[i, 1], nms[i, 0], blackQueens, whiteQueens)) { PrintBoard(nms[i, 0], blackQueens, whiteQueens); } else { Console.WriteLine("No solution exists.\n"); } } } }
}</lang>
- 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: B # # W # 2 black and 2 white queens on a 3 x 3 board: No solution exists. 1 black and 1 white queens on a 4 x 4 board: B # # # W # # # # 2 black and 2 white queens on a 4 x 4 board: B # # # W B # # # W 3 black and 3 white queens on a 4 x 4 board: No solution exists. 1 black and 1 white queens on a 5 x 5 board: B # # # W # # # # # # # # 2 black and 2 white queens on a 5 x 5 board: B # # B # W # W # # # # # # 3 black and 3 white queens on a 5 x 5 board: B # # B # W # W # # # B # W # 4 black and 4 white queens on a 5 x 5 board: B B # # B W # W # # # B W # W # 5 black and 5 white queens on a 5 x 5 board: No solution exists. 1 black and 1 white queens on a 6 x 6 board: B # # # # W # # # # # # # # # # # # # 2 black and 2 white queens on a 6 x 6 board: B # # B # # W # W # # # # # # # # # # # 3 black and 3 white queens on a 6 x 6 board: B # # B B # W # W # # # # # # W # # # # # 4 black and 4 white queens on a 6 x 6 board: B # # B B # W # W # # # # # B # W W # # # # 5 black and 5 white queens on a 6 x 6 board: B # B # # # B # B W # # # W W # # # B W W # 6 black and 6 white queens on a 6 x 6 board: No solution exists. 1 black and 1 white queens on a 7 x 7 board: B # # # # W # # # # # # # # # # # # # # # # # # # 2 black and 2 white queens on a 7 x 7 board: B # # B # # W # W # # # # # # # # # # # # # # # # # 3 black and 3 white queens on a 7 x 7 board: B # # B # # W # W B # # # # W # # # # # # # # # # # # 4 black and 4 white queens on a 7 x 7 board: B # # B # # W # W B # # B # # W # W # # # # # # # # # # 5 black and 5 white queens on a 7 x 7 board: B # # B # # W # W B # # B # # W # W B # # # # W # # # # # 6 black and 6 white queens on a 7 x 7 board: B # # B # # W # W B # # B # # W # W B # # B # # W # W # # # 7 black and 7 white queens on a 7 x 7 board: B # B # B # B # B # B # # B # W # W # # W # # W # # W # W W #
D
<lang d>import std.array; import std.math; import std.stdio; import std.typecons;
enum Piece {
empty, black, white,
}
alias position = Tuple!(int, "i", int, "j");
bool place(int m, int n, ref position[] pBlackQueens, ref position[] pWhiteQueens) {
if (m == 0) { return true; } bool placingBlack = true; foreach (i; 0..n) { inner: foreach (j; 0..n) { auto pos = position(i, j); foreach (queen; pBlackQueens) { if (queen == pos || !placingBlack && isAttacking(queen, pos)) { continue inner; } } foreach (queen; pWhiteQueens) { if (queen == pos || placingBlack && isAttacking(queen, pos)) { continue inner; } } if (placingBlack) { pBlackQueens ~= pos; placingBlack = false; } else { pWhiteQueens ~= pos; if (place(m - 1, n, pBlackQueens, pWhiteQueens)) { return true; } pBlackQueens.length--; pWhiteQueens.length--; placingBlack = true; } } } if (!placingBlack) { pBlackQueens.length--; } return false;
}
bool isAttacking(position queen, position pos) {
return queen.i == pos.i || queen.j == pos.j || abs(queen.i - pos.i) == abs(queen.j - pos.j);
}
void printBoard(int n, position[] blackQueens, position[] whiteQueens) {
auto board = uninitializedArray!(Piece[])(n * n); board[] = Piece.empty;
foreach (queen; blackQueens) { board[queen.i * n + queen.j] = Piece.black; } foreach (queen; whiteQueens) { board[queen.i * n + queen.j] = Piece.white; } foreach (i,b; board) { if (i != 0 && i % n == 0) { writeln; } final switch (b) { case Piece.black: write("B "); break; case Piece.white: write("W "); break; case Piece.empty: int j = i / n; int k = i - j * n;
if (j % 2 == k % 2) { write("• "w); } else { write("◦ "w); } break; } } writeln('\n');
}
void main() {
auto nms = [ [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], ]; foreach (nm; nms) { writefln("%d black and %d white queens on a %d x %d board:", nm[1], nm[1], nm[0], nm[0]); position[] blackQueens; position[] whiteQueens; if (place(nm[1], nm[0], blackQueens, whiteQueens)) { printBoard(nm[0], blackQueens, whiteQueens); } else { writeln("No solution exists.\n"); } }
}</lang>
- 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: B ◦ • ◦ • W • ◦ • 2 black and 2 white queens on a 3 x 3 board: No solution exists. 1 black and 1 white queens on a 4 x 4 board: B ◦ • ◦ ◦ • W • • ◦ • ◦ ◦ • ◦ • 2 black and 2 white queens on a 4 x 4 board: B ◦ • ◦ ◦ • W • B ◦ • ◦ ◦ • W • 3 black and 3 white queens on a 4 x 4 board: No solution exists. 1 black and 1 white queens on a 5 x 5 board: B ◦ • ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 2 black and 2 white queens on a 5 x 5 board: B ◦ • ◦ B ◦ • W • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 3 black and 3 white queens on a 5 x 5 board: B ◦ • ◦ B ◦ • W • ◦ • W • ◦ • ◦ • ◦ B ◦ • W • ◦ • 4 black and 4 white queens on a 5 x 5 board: • B • B • ◦ • ◦ • B W ◦ W ◦ • ◦ • ◦ • B W ◦ W ◦ • 5 black and 5 white queens on a 5 x 5 board: No solution exists. 1 black and 1 white queens on a 6 x 6 board: B ◦ • ◦ • ◦ ◦ • W • ◦ • • ◦ • ◦ • ◦ ◦ • ◦ • ◦ • • ◦ • ◦ • ◦ ◦ • ◦ • ◦ • 2 black and 2 white queens on a 6 x 6 board: B ◦ • ◦ B ◦ ◦ • W • ◦ • • W • ◦ • ◦ ◦ • ◦ • ◦ • • ◦ • ◦ • ◦ ◦ • ◦ • ◦ • 3 black and 3 white queens on a 6 x 6 board: B ◦ • ◦ B B ◦ • W • ◦ • • W • ◦ • ◦ ◦ • ◦ • ◦ • • ◦ W ◦ • ◦ ◦ • ◦ • ◦ • 4 black and 4 white queens on a 6 x 6 board: B ◦ • ◦ B B ◦ • W • ◦ • • W • ◦ • ◦ ◦ • ◦ • ◦ B • ◦ W W • ◦ ◦ • ◦ • ◦ • 5 black and 5 white queens on a 6 x 6 board: • B • ◦ B ◦ ◦ • ◦ B ◦ B W ◦ • ◦ • ◦ W • W • ◦ • • ◦ • ◦ • B W • W • ◦ • 6 black and 6 white queens on a 6 x 6 board: No solution exists. 1 black and 1 white queens on a 7 x 7 board: B ◦ • ◦ • ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 2 black and 2 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 3 black and 3 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ • ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 4 black and 4 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ B ◦ • ◦ • W • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 5 black and 5 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ • ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • 6 black and 6 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ B ◦ • ◦ • W • ◦ • W • ◦ • ◦ • ◦ • 7 black and 7 white queens on a 7 x 7 board: • B • ◦ • B • ◦ B ◦ • B • ◦ • B • ◦ • B • ◦ • ◦ • B • ◦ W ◦ W ◦ • ◦ W ◦ • ◦ W ◦ • ◦ W ◦ W W • ◦ •
Go
This is based on the C# code here.
Textual rather than HTML output. Whilst the unicode symbols for the black and white queens are recognized by the Ubuntu 16.04 terminal, I found it hard to visually distinguish between them so I've used 'B' and 'W' instead. <lang go>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") } }
}</lang>
- 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: B ◦ • ◦ • W • ◦ • 2 black and 2 white queens on a 3 x 3 board: No solution exists. 1 black and 1 white queens on a 4 x 4 board: B ◦ • ◦ • ◦ W ◦ • ◦ • ◦ • ◦ • ◦ 2 black and 2 white queens on a 4 x 4 board: B ◦ • ◦ • ◦ W ◦ B ◦ • ◦ • ◦ W ◦ 3 black and 3 white queens on a 4 x 4 board: No solution exists. 1 black and 1 white queens on a 5 x 5 board: B ◦ • ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 2 black and 2 white queens on a 5 x 5 board: B ◦ • ◦ B ◦ • W • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 3 black and 3 white queens on a 5 x 5 board: B ◦ • ◦ B ◦ • W • ◦ • W • ◦ • ◦ • ◦ B ◦ • W • ◦ • 4 black and 4 white queens on a 5 x 5 board: • B • B • ◦ • ◦ • B W ◦ W ◦ • ◦ • ◦ • B W ◦ W ◦ • 5 black and 5 white queens on a 5 x 5 board: No solution exists. 1 black and 1 white queens on a 6 x 6 board: B ◦ • ◦ • ◦ • ◦ W ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ 2 black and 2 white queens on a 6 x 6 board: B ◦ • ◦ B ◦ • ◦ W ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ 3 black and 3 white queens on a 6 x 6 board: B ◦ • ◦ B B • ◦ W ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ W ◦ • ◦ • ◦ • ◦ • ◦ 4 black and 4 white queens on a 6 x 6 board: B ◦ • ◦ B B • ◦ W ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • B • ◦ W W • ◦ • ◦ • ◦ • ◦ 5 black and 5 white queens on a 6 x 6 board: • B • ◦ B ◦ • ◦ • B • B W ◦ • ◦ • ◦ W ◦ W ◦ • ◦ • ◦ • ◦ • B W ◦ W ◦ • ◦ 6 black and 6 white queens on a 6 x 6 board: No solution exists. 1 black and 1 white queens on a 7 x 7 board: B ◦ • ◦ • ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 2 black and 2 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 3 black and 3 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ • ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 4 black and 4 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ B ◦ • ◦ • W • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 5 black and 5 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ • ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • 6 black and 6 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ B ◦ • ◦ • W • ◦ • W • ◦ • ◦ • ◦ • 7 black and 7 white queens on a 7 x 7 board: • B • ◦ • B • ◦ B ◦ • B • ◦ • B • ◦ • B • ◦ • ◦ • B • ◦ W ◦ W ◦ • ◦ W ◦ • ◦ W ◦ • ◦ W ◦ W W • ◦ •
Julia
GUI version, uses the Gtk library. The place! function is condensed from the C# example. <lang julia>using Gtk
struct Position
row::Int col::Int
end
function place!(numeach, bsize, bqueens, wqueens)
isattack(q, pos) = (q.row == pos.row || q.col == pos.col || abs(q.row - pos.row) == abs(q.col - pos.col)) noattack(qs, pos) = !any(x -> isattack(x, pos), qs) positionopen(bqs, wqs, p) = !any(x -> x == p, bqs) && !any(x -> x == p, wqs)
placingbqueens = true if numeach < 1 return true end for i in 1:bsize, j in 1:bsize bpos = Position(i, j) if positionopen(bqueens, wqueens, bpos) if placingbqueens && noattack(wqueens, bpos) push!(bqueens, bpos) placingbqueens = false elseif !placingbqueens && noattack(bqueens, bpos) push!(wqueens, bpos) if place!(numeach - 1, bsize, bqueens, wqueens) return true end pop!(bqueens) pop!(wqueens) placingbqueens = true end end end if !placingbqueens pop!(bqueens) end false
end
function peacefulqueenapp()
win = GtkWindow("Peaceful Chess Queen Armies", 800, 800) |> (GtkFrame() |> (box = GtkBox(:v))) boardsize = 5 numqueenseach = 4 hbox = GtkBox(:h) boardscale = GtkScale(false, 2:16) set_gtk_property!(boardscale, :hexpand, true) blabel = GtkLabel("Choose Board Size") nqueenscale = GtkScale(false, 1:24) set_gtk_property!(nqueenscale, :hexpand, true) qlabel = GtkLabel("Choose Number of Queens Per Side") solveit = GtkButton("Solve") set_gtk_property!(solveit, :label, " Solve ") solvequeens(wid) = (boardsize = Int(GAccessor.value(boardscale)); numqueenseach = Int(GAccessor.value(nqueenscale)); update!()) signal_connect(solvequeens, solveit, :clicked) map(w->push!(hbox, w),[blabel, boardscale, qlabel, nqueenscale, solveit]) scrwin = GtkScrolledWindow() grid = GtkGrid() push!(scrwin, grid) map(w -> push!(box, w),[hbox, scrwin]) piece = (white = "\u2655", black = "\u265B", blank = " ") stylist = GtkStyleProvider(Gtk.CssProviderLeaf(data=""" label {background-image: image(cornsilk); font-size: 48px;} button {background-image: image(tan); font-size: 48px;}"""))
function update!() bqueens, wqueens = Vector{Position}(), Vector{Position}() place!(numqueenseach, boardsize, bqueens, wqueens) if length(bqueens) == 0 warn_dialog("No solution for board size $boardsize and $numqueenseach queens each.", win) return end empty!(grid) labels = Array{Gtk.GtkLabelLeaf, 2}(undef, (boardsize, boardsize)) buttons = Array{GtkButtonLeaf, 2}(undef, (boardsize, boardsize)) for i in 1:boardsize, j in 1:boardsize if isodd(i + j) grid[i, j] = buttons[i, j] = GtkButton(piece.blank) set_gtk_property!(buttons[i, j], :expand, true) push!(Gtk.GAccessor.style_context(buttons[i, j]), stylist, 600) else grid[i, j] = labels[i, j] = GtkLabel(piece.blank) set_gtk_property!(labels[i, j], :expand, true) push!(Gtk.GAccessor.style_context(labels[i, j]), stylist, 600) end pos = Position(i, j) if pos in bqueens set_gtk_property!(grid[i, j], :label, piece.black) elseif pos in wqueens set_gtk_property!(grid[i, j], :label, piece.white) end end showall(win) end
update!() cond = Condition() endit(w) = notify(cond) signal_connect(endit, win, :destroy) showall(win) wait(cond)
end
peacefulqueenapp() </lang>
Kotlin
<lang scala>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") } }
}</lang>
- 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: B ◦ • ◦ • W • ◦ • 2 black and 2 white queens on a 3 x 3 board: No solution exists. 1 black and 1 white queens on a 4 x 4 board: B ◦ • ◦ ◦ • W • • ◦ • ◦ ◦ • ◦ • 2 black and 2 white queens on a 4 x 4 board: B ◦ • ◦ ◦ • W • B ◦ • ◦ ◦ • W • 3 black and 3 white queens on a 4 x 4 board: No solution exists. 1 black and 1 white queens on a 5 x 5 board: B ◦ • ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 2 black and 2 white queens on a 5 x 5 board: B ◦ • ◦ B ◦ • W • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 3 black and 3 white queens on a 5 x 5 board: B ◦ • ◦ B ◦ • W • ◦ • W • ◦ • ◦ • ◦ B ◦ • W • ◦ • 4 black and 4 white queens on a 5 x 5 board: • B • B • ◦ • ◦ • B W ◦ W ◦ • ◦ • ◦ • B W ◦ W ◦ • 5 black and 5 white queens on a 5 x 5 board: No solution exists. 1 black and 1 white queens on a 6 x 6 board: B ◦ • ◦ • ◦ ◦ • W • ◦ • • ◦ • ◦ • ◦ ◦ • ◦ • ◦ • • ◦ • ◦ • ◦ ◦ • ◦ • ◦ • 2 black and 2 white queens on a 6 x 6 board: B ◦ • ◦ B ◦ ◦ • W • ◦ • • W • ◦ • ◦ ◦ • ◦ • ◦ • • ◦ • ◦ • ◦ ◦ • ◦ • ◦ • 3 black and 3 white queens on a 6 x 6 board: B ◦ • ◦ B B ◦ • W • ◦ • • W • ◦ • ◦ ◦ • ◦ • ◦ • • ◦ W ◦ • ◦ ◦ • ◦ • ◦ • 4 black and 4 white queens on a 6 x 6 board: B ◦ • ◦ B B ◦ • W • ◦ • • W • ◦ • ◦ ◦ • ◦ • ◦ B • ◦ W W • ◦ ◦ • ◦ • ◦ • 5 black and 5 white queens on a 6 x 6 board: • B • ◦ B ◦ ◦ • ◦ B ◦ B W ◦ • ◦ • ◦ W • W • ◦ • • ◦ • ◦ • B W • W • ◦ • 6 black and 6 white queens on a 6 x 6 board: No solution exists. 1 black and 1 white queens on a 7 x 7 board: B ◦ • ◦ • ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 2 black and 2 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 3 black and 3 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ • ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 4 black and 4 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ B ◦ • ◦ • W • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • ◦ • 5 black and 5 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ • ◦ • ◦ • W • ◦ • ◦ • ◦ • ◦ • ◦ • 6 black and 6 white queens on a 7 x 7 board: B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ B ◦ • ◦ • W • ◦ • W B ◦ • ◦ B ◦ • ◦ • W • ◦ • W • ◦ • ◦ • ◦ • 7 black and 7 white queens on a 7 x 7 board: • B • ◦ • B • ◦ B ◦ • B • ◦ • B • ◦ • B • ◦ • ◦ • B • ◦ W ◦ W ◦ • ◦ W ◦ • ◦ W ◦ • ◦ W ◦ W W • ◦ •
Perl
Terse
<lang perl>use strict; use warnings;
my $m = shift // 4; my $n = shift // 5; my %seen; my $gaps = join '|', qr/-*/, map qr/.{$_}(?:-.{$_})*/s, $n-1, $n, $n+1; my $attack = qr/(\w)(?:$gaps)(?!\1)\w/;
place( scalar ('-' x $n . "\n") x $n ); print "No solution to $m $n\n";
sub place
{ local $_ = shift; $seen{$_}++ || /$attack/ and return; # previously or attack (my $have = tr/WB//) < $m * 2 or exit !print "Solution to $m $n\n\n$_"; place( s/-\G/ qw(W B)[$have % 2] /er ) while /-/g; # place next queen }</lang>
- Output:
Solution to 4 5 W---W --B-- -B-B- --B-- W---W
Verbose
A refactored version of the same code, with fancier output. <lang perl>use strict; use warnings; use feature 'say'; use feature 'state'; use utf8; binmode(STDOUT, ':utf8');
my $solution; # algorithm requires this variable to be global
- recursively place the next queen
sub place {
my($board, $n, $m, $empty_square) = @_; state(%seen,$attack);
# logic of 'attack' regex: queen ( ... paths between queens containing only empty squares ... ) queen of other color unless ($attack) { $attack = '([WB])' . # 1st queen '(?:' . join('|', "[$empty_square]*", map { "(?^s:.{$_}(?:[$empty_square].{$_})*)" } $n-1, $n, $n+1 ) . ')' . '(?!\1)[WB]'; # 2nd queen }
# bail out if seen this configuration previously, or attack detected return if $seen{$board}++ or $board =~ /$attack/;
# success if queen count is m×2 $solution = $board and goto DONE if $m * 2 == (my $have = $board =~ tr/WB//);
# place the next queen (alternating colors each time) place( $board =~ s/[$empty_square]\G/ qw<W B>[$have % 2] /er, $n, $m, $empty_square ) while $board =~ /[$empty_square]/g;
}
my($m, $n) = (shift, shift) || (4, 5); my $empty_square = '◦•'; my $board = join "\n", map { substr $empty_square x $n, $_%2, $n } 1..$n;
place( $board, $n, $m, $empty_square );
DONE: say $solution
? sprintf "Solution to $m $n\n\n%s", map { s/(.)/$1 /gm; s/B /♛/gm; s/W /♕/gmr } $solution : "No solution to $m $n";</lang>
- Output:
Solution to 4 5 ♕◦ • ◦ ♕ ◦ • ♛• ◦ • ♛• ♛• ◦ • ♛• ◦ ♕◦ • ◦ ♕
Perl 6
<lang perl6># recursively place the next queen sub place ($board, $n, $m, $empty-square) {
my $cnt; state (%seen,$attack); state $solution = False;
# logic of regex: queen ( ... paths between queens containing only empty squares ... ) queen of other color once { my %Q = 'WBBW'.comb; # return the queen of alternate color my $re = '(<[WB]>)' ~ # 1st queen '[' ~ join(' |', qq/<[$empty-square]>*/, map { qq/ . ** {$_}[<[$empty-square]> . ** {$_}]*/ }, $n-1, $n, $n+1 ) ~ ']' ~ '<{%Q{$0}}>'; # 2nd queen $attack = "rx/$re/".EVAL; }
# return first result found (omit this line to get last result found) return $solution if $solution;
# bail out if seen this configuration previously, or attack detected return if %seen{$board}++ or $board ~~ $attack;
# success if queen count is m×2, set state variable and return from recursion $solution = $board and return if $m * 2 == my $queens = $board.comb.Bag{<W B>}.sum;
# place the next queen (alternating colors each time) place( $board.subst( /<[◦•]>/, {<W B>[$queens % 2]}, :nth($cnt) ), $n, $m, $empty-square ) while $board ~~ m:nth(++$cnt)/<[◦•]>/;
return $solution
}
my ($m, $n) = @*ARGS == 2 ?? @*ARGS !! (4, 5); my $empty-square = '◦•'; my $board = ($empty-square x $n**2).comb.rotor($n)>>.join[^$n].join: "\n";
my $solution = place $board, $n, $m, $empty-square;
say $solution
?? "Solution to $m $n\n\n{S:g/(\N)/$0 / with $solution}" !! "No solution to $m $n";</lang>
- Output:
W • ◦ • W • ◦ B ◦ • ◦ B ◦ B ◦ • ◦ B ◦ • W • ◦ • W
Phix
<lang Phix>-- demo\rosetta\Queen_Armies.exw string html = "" constant as_html = true constant queens = {``,
`♛`,
`♕`,
`?`}
procedure showboard(integer n, sequence blackqueens, whitequeens)
sequence board = repeat(repeat('-',n),n) for i=1 to length(blackqueens) do integer {qi,qj} = blackqueens[i] board[qi,qj] = 'B' {qi,qj} = whitequeens[i] board[qi,qj] = 'W' end for if as_html then string out = sprintf("
## %d black and %d white queens on a %d-by-%d board
\n", {length(blackqueens),length(whitequeens),n,n}), tbl = ""
out &= "
\n " for x=1 to n do for y=1 to n do if y=1 then tbl &= " \n \n" end if integer xw = find({x,y},blackqueens)!=0, xb = find({x,y},whitequeens)!=0, dx = xw+xb*2+1 string ch = queens[dx], bg = iff(mod(x+y,2)?"":` bgcolor="silver"`) tbl &= sprintf(" \n",{bg,ch})end for end for out &= tbl[11..$]out &= " \n
%s |
\n
\n"
html &= out else integer b = length(blackqueens), w = length(whitequeens) printf(1,"%d black and %d white queens on a %d x %d board:\n", {b, w, n, n}) puts(1,join(board,"\n")&"\n")
-- ?{n,blackqueens, whitequeens}
end if
end procedure
function isAttacking(sequence queen, pos)
integer {qi,qj} = queen, {pi,pj} = pos return qi=pi or qj=pj or abs(qi-pi)=abs(qj-pj)
end function
function place(integer m, n, sequence blackqueens = {}, whitequeens = {})
if m == 0 then showboard(n,blackqueens,whitequeens) return true end if bool placingBlack := true for i=1 to n do for j=1 to n do sequence pos := {i, j} for q=1 to length(blackqueens) do sequence queen := blackqueens[q] if queen == pos or ((not placingBlack) and isAttacking(queen, pos)) then pos = {} exit end if end for if pos!={} then for q=1 to length(whitequeens) do sequence queen := whitequeens[q] if queen == pos or (placingBlack and isAttacking(queen, pos)) then pos = {} exit end if end for if pos!={} then if placingBlack then blackqueens = append(blackqueens, pos) placingBlack = false else whitequeens = append(whitequeens, pos) if place(m-1, n, blackqueens, whitequeens) then return true end if blackqueens = blackqueens[1..$-1] whitequeens = whitequeens[1..$-1] placingBlack = true end if end if end if end for end for return false
end function
for n=2 to 7 do
for m=1 to n-(n<5) do if not place(m,n) then string no = sprintf("Cannot place %d+ queen armies on a %d-by-%d board",{m,n,n}) if as_html then html &= sprintf("# %s
\n\n",{no}) else printf(1,"%s.\n", {no}) end if end if end for
end for
constant html_header = """ <!DOCTYPE html> <html lang="en">
<head> <meta charset="utf-8" /> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> <title>Rosettacode Rank Languages by popularity</title> </head> <body>
queen armies
""", -- or
html_footer = """ </body>
</html>
""" -- orif as_html then
integer fn = open("queen_armies.html","w") puts(fn,html_header) puts(fn,html) puts(fn,html_footer) close(fn) printf(1,"See queen_armies.html\n")
end if
?"done" {} = wait_key()</lang>
- Output:
with as_html = false
Cannot place 1+ queen armies on a 2-by-2 board. 1 black and 1 white queens on a 3 x 3 board: B-- --W --- Cannot place 2+ queen armies on a 3-by-3 board. <snip> 7 black and 7 white queens on a 7 x 7 board: -B---B- -B--B-- -B---B- ----B-- W-W---W ---W--- W-WW---
- Output:
with as_html = true
# Cannot place 1+ queen armies on a 2-by-2 board
## 1 black and 1 white queens on a 3-by-3 board
♛ | ||
♕ | ||
# Cannot place 2+ queen armies on a 3-by-3 board
<snip>
## 7 black and 7 white queens on a 7-by-7 board
♛ | ♛ | |||||
♛ | ♛ | |||||
♛ | ♛ | |||||
♛ | ||||||
♕ | ♕ | ♕ | ||||
♕ | ||||||
♕ | ♕ | ♕ |
Python
Python: Textual output
<lang python>from itertools import combinations, product, count from functools import lru_cache, reduce
_bbullet, _wbullet = '\u2022\u25E6'
_or = set.__or__
def place(m, n):
"Place m black and white queens, peacefully, on an n-by-n board" board = set(product(range(n), repeat=2)) # (x, y) tuples placements = {frozenset(c) for c in combinations(board, m)} for blacks in placements: black_attacks = reduce(_or, (queen_attacks_from(pos, n) for pos in blacks), set()) for whites in {frozenset(c) # Never on blsck attacking squares for c in combinations(board - black_attacks, m)}: if not black_attacks & whites: return blacks, whites return set(), set()
@lru_cache(maxsize=None) def queen_attacks_from(pos, n):
x0, y0 = pos a = set([pos]) # Its position a.update((x, y0) for x in range(n)) # Its row a.update((x0, y) for y in range(n)) # Its column # Diagonals for x1 in range(n): # l-to-r diag y1 = y0 -x0 +x1 if 0 <= y1 < n: a.add((x1, y1)) # r-to-l diag y1 = y0 +x0 -x1 if 0 <= y1 < n: a.add((x1, y1)) return a
def pboard(black_white, n):
"Print board" if black_white is None: blk, wht = set(), set() else: blk, wht = black_white print(f"## {len(blk)} black and {len(wht)} white queens " f"on a {n}-by-{n} board:", end=) for x, y in product(range(n), repeat=2): if y == 0: print() xy = (x, y) ch = ('?' if xy in blk and xy in wht else 'B' if xy in blk else 'W' if xy in wht else _bbullet if (x + y)%2 else _wbullet) print('%s' % ch, end=) print()
if __name__ == '__main__':
n=2 for n in range(2, 7): print() for m in count(1): ans = place(m, n) if ans[0]: pboard(ans, n) else: print (f"# Can't place {m}+ queens on a {n}-by-{n} board") break # print('\n') m, n = 5, 7 ans = place(m, n) pboard(ans, n)</lang>
- Output:
# Can't place 1+ queens on a 2-by-2 board ## 1 black and 1 white queens on a 3-by-3 board: ◦•◦ B◦• ◦•W # Can't place 2+ queens on a 3-by-3 board ## 1 black and 1 white queens on a 4-by-4 board: ◦•W• B◦•◦ ◦•◦• •◦•◦ ## 2 black and 2 white queens on a 4-by-4 board: ◦B◦• •B•◦ ◦•◦• W◦W◦ # Can't place 3+ queens on a 4-by-4 board ## 1 black and 1 white queens on a 5-by-5 board: ◦•◦•◦ W◦•◦• ◦•◦•◦ •◦•◦B ◦•◦•◦ ## 2 black and 2 white queens on a 5-by-5 board: ◦•◦•W •◦B◦• ◦•◦•◦ •◦•B• ◦W◦•◦ ## 3 black and 3 white queens on a 5-by-5 board: ◦W◦•◦ •◦•◦W B•B•◦ B◦•◦• ◦•◦W◦ ## 4 black and 4 white queens on a 5-by-5 board: ◦•B•B W◦•◦• ◦W◦W◦ W◦•◦• ◦•B•B # Can't place 5+ queens on a 5-by-5 board ## 1 black and 1 white queens on a 6-by-6 board: ◦•◦•◦• W◦•◦•◦ ◦•◦•◦• •◦•◦B◦ ◦•◦•◦• •◦•◦•◦ ## 2 black and 2 white queens on a 6-by-6 board: ◦•◦•◦• •◦B◦•◦ ◦•◦•◦• •◦•B•◦ ◦•◦•◦• W◦•◦W◦ ## 3 black and 3 white queens on a 6-by-6 board: ◦•B•◦• •B•◦•◦ ◦•◦W◦W •◦•◦•◦ W•◦•◦• •◦•◦B◦ ## 4 black and 4 white queens on a 6-by-6 board: WW◦•W• •W•◦•◦ ◦•◦•◦B •◦B◦•◦ ◦•◦B◦• •◦•B•◦ ## 5 black and 5 white queens on a 6-by-6 board: ◦•W•W• B◦•◦•◦ ◦•W•◦W B◦•◦•◦ ◦•◦•◦W BB•B•◦ # Can't place 6+ queens on a 6-by-6 board ## 5 black and 5 white queens on a 7-by-7 board: ◦•◦•B•◦ •W•◦•◦W ◦•◦•B•◦ B◦•◦•◦• ◦•B•◦•◦ •◦•B•◦• ◦W◦•◦WW
Python: HTML output
Uses the solver function place
from the above textual output case.
<lang python>from peaceful_queen_armies_simpler import place
from itertools import product, count
_bqueenh, _wqueenh = '♛', '♕'
def hboard(black_white, n):
"HTML board generator" if black_white is None: blk, wht = set(), set() else: blk, wht = black_white out = (f"
## {len(blk)} black and {len(wht)} white queens " f"on a {n}-by-{n} board
\n")
out += '
\n ' tbl = for x, y in product(range(n), repeat=2): if y == 0: tbl += ' \n \n' xy = (x, y) ch = ('?' if xy in blk and xy in wht else _bqueenh if xy in blk else _wqueenh if xy in wht else "") bg = "" if (x + y)%2 else ' bgcolor="silver"' tbl += f' \n'out += tbl[7:]out += ' \n
{ch} |
\n
\n'
return out
if __name__ == '__main__':
n=2 html = for n in range(2, 7): print() for m in count(1): ans = place(m, n) if ans[0]: html += hboard(ans, n) else: html += (f"# Can't place {m}+ queen armies on a " f"{n}-by-{n} board
\n\n" ) break # html += '
\n' m, n = 6, 7 ans = place(m, n) html += hboard(ans, n) with open('peaceful_queen_armies.htm', 'w') as f: f.write(html)</lang>
- Output:
# Can't place 1+ queen armies on a 2-by-2 board
## 1 black and 1 white queens on a 3-by-3 board
♛ | ||
♕ |
# Can't place 2+ queen armies on a 3-by-3 board
## 1 black and 1 white queens on a 4-by-4 board
♕ | |||
♛ | |||
## 2 black and 2 white queens on a 4-by-4 board
♛ | |||
♛ | |||
♕ | ♕ |
# Can't place 3+ queen armies on a 4-by-4 board
## 1 black and 1 white queens on a 5-by-5 board
♕ | ||||
♛ | ||||
## 2 black and 2 white queens on a 5-by-5 board
♕ | ||||
♛ | ||||
♛ | ||||
♕ |
## 3 black and 3 white queens on a 5-by-5 board
♕ | ||||
♕ | ||||
♛ | ♛ | |||
♛ | ||||
♕ |
## 4 black and 4 white queens on a 5-by-5 board
♛ | ♛ | |||
♕ | ||||
♕ | ♕ | |||
♕ | ||||
♛ | ♛ |
# Can't place 5+ queen armies on a 5-by-5 board
## 1 black and 1 white queens on a 6-by-6 board
♕ | |||||
♛ | |||||
## 2 black and 2 white queens on a 6-by-6 board
♛ | |||||
♛ | |||||
♕ | ♕ |
## 3 black and 3 white queens on a 6-by-6 board
♛ | |||||
♛ | |||||
♕ | ♕ | ||||
♕ | |||||
♛ |
## 4 black and 4 white queens on a 6-by-6 board
♕ | ♕ | ♕ | |||
♕ | |||||
♛ | |||||
♛ | |||||
♛ | |||||
♛ |
## 5 black and 5 white queens on a 6-by-6 board
♕ | ♕ | ||||
♛ | |||||
♕ | ♕ | ||||
♛ | |||||
♕ | |||||
♛ | ♛ | ♛ |
# Can't place 6+ queen armies on a 6-by-6 board
## 6 black and 6 white queens on a 7-by-7 board
♛ | ♛ | |||||
♕ | ||||||
♕ | ♕ | ♕ | ||||
♕ | ||||||
♛ | ♛ | |||||
♕ | ||||||
♛ | ♛ |
zkl
<lang zkl>fcn isAttacked(q, x,y) // ( (r,c), x,y ) : is queen at r,c attacked by q@(x,y)?
{ r,c:=q; (r==x or c==y or r+c==x+y or r-c==x-y) }
fcn isSafe(r,c,qs) // queen safe at (r,c)?, qs=( (r,c),(r,c)..)
{ ( not qs.filter1(isAttacked,r,c) ) }
fcn isEmpty(r,c,qs){ (not (qs and qs.filter1('wrap([(x,y)]){ r==x and c==y })) ) } fcn _peacefulQueens(N,M,qa,qb){ //--> False | (True,((r,c)..),((r,c)..) )
// qa,qb --> // ( (r,c),(r,c).. ), solution so far to last good spot if(qa.len()==M==qb.len()) return(True,qa,qb); n, x,y := N, 0,0; if(qa) x,y = qa[-1]; else n=(N+1)/2; // first queen, first quadrant only foreach r in ([x..n-1]){ foreach c in ([y..n-1]){
if(isEmpty(r,c,qa) and isSafe(r,c,qb)){ qc,qd := qa.append(T(r,c)), self.fcn(N,M, qb,qc); if(qd) return( if(qd[0]==True) qd else T(qc,qd) ); }
} y=0 } False
}
fcn peacefulQueens(N=5,M=4){ # NxN board, M white and black queens
qs:=_peacefulQueens(N,M, T,T); println("Solution for %dx%d board with %d black and %d white queens:".fmt(N,N,M,M)); if(not qs)println("None"); else{ z:=Data(Void,"-"*N*N); foreach r,c in (qs[1]){ z[r*N + c]="W" } foreach r,c in (qs[2]){ z[r*N + c]="B" } z.text.pump(Void,T(Void.Read,N-1),"println"); }
}</lang> <lang zkl>peacefulQueens(); foreach n in ([4..10]){ peacefulQueens(n,n) }</lang>
- Output:
Solution for 5x5 board with 4 black and 4 white queens: W---W --B-- -B-B- --B-- W---W Solution for 4x4 board with 4 black and 4 white queens: None Solution for 5x5 board with 5 black and 5 white queens: None Solution for 6x6 board with 6 black and 6 white queens: None Solution for 7x7 board with 7 black and 7 white queens: W---W-W --B---- -B-B-B- --B---- W-----W --BB--- W-----W Solution for 8x8 board with 8 black and 8 white queens: W---W--- --B---BB W---W--- --B---B- ---B---B -W---W-- W---W--- --B----- Solution for 9x9 board with 9 black and 9 white queens: W---W---W --B---B-- -B---B--- ---W---W- -B---B--- ---W---W- -B---B--- ---W---W- -B------- Solution for 10x10 board with 10 black and 10 white queens: W---W---WW --B---B--- -B-B------ -----W-W-W -BBB------ -----W-W-W -B-------- ------B--- ---B------ ----------