Peaceful chess queen armies
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.
You are encouraged to solve this task according to the task description, using any language you may know.
⇖ | ⇑ | ⇗ | ||
⇐ | ⇐ | ♛ | ⇒ | ⇒ |
⇙ | ⇓ | ⇘ | ||
⇙ | ⇓ | ⇘ | ||
⇓ |
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------ ----------