Peaceful chess queen armies: Difference between revisions

=={{header|C}}==

{{trans|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>

{{out}}

<pre>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 #</pre>