Queens puzzle
Adapted from NCURSES Programming HOWTO, by Pradeep Padala. The program comes from the HOWTO’s example archive,
JustForFun/queens.c, maintained by Thomas E. Dickey.
The N-Queens puzzle asks you to put N queens on an N by N chessboard so that no two attack each other.
This program solves it by simple backtracking, for the number of queens given as its argument, and shows each solution as it finds it. Press a key for the next solution, or F1 to stop. The Run button runs it with 8.
Example: Queens puzzle
#include <stdlib.h>#include <curses.h>
#define QUEEN_CHAR '*'
static void int tile_width, int tile_height){ int endy, endx, i, j;
endy = starty + lines * tile_height; endx = startx + cols * tile_width;
for (j = starty; j <= endy; j += tile_height) for (i = startx; i <= endx; ++i) for (i = startx; i <= endx; i += tile_width) for (j = starty; j <= endy; ++j) for (j = starty + tile_height; j <= endy - tile_height; j += tile_height) { for (i = startx + tile_width; i <= endx - tile_width; i += tile_width) } for (i = startx + tile_width; i <= endx - tile_width; i += tile_width) { }}
static voidprint(int *positions, int num_queens){ int count; int y = 2, x = 2, w = 4, h = 2; static int solution = 1;
for (count = 1; count <= num_queens; ++count) { int tempy = y + (count - 1) * h + h / 2; int tempx = x + (positions[count] - 1) * w + w / 2; } "Press Any Key to See next solution (F1 to Exit)"); exit(EXIT_SUCCESS); }}
static intplace(int current, int *position){ int i; if (current == 1) return (1); for (i = 1; i < current; ++i) if (position[i] == position[current]) return (0); else if (abs(position[i] - position[current]) == abs(i - current)) return (0);
return (1);}
static int *nqueens(int num){ int current, *position, num_solutions = 0;
if ((position = (int *) calloc((size_t) num + 1, sizeof(int))) == NULL) { perror("calloc"); exit(EXIT_FAILURE); }
position[1] = 0; current = 1; /* current queen is being checked */ /* position[current] is the column */ while (current > 0) { position[current] += 1; while (position[current] <= num && !place(current, position)) position[current] += 1; if (position[current] <= num) { if (current == num) { ++num_solutions; print(position, num); } else { current += 1; position[current] = 0; } } else current -= 1; /* backtrack */ } printf("Total Number of Solutions : %d\n", num_solutions); return (position);}
intmain(int argc, char *argv[]){ int num_queens, *positions;
if (argc != 2) { printf("Usage: %s <number of queens (chess board order)>\n", argv[0]); return EXIT_FAILURE; }
num_queens = atoi(argv[1]); positions = nqueens(num_queens); free(positions); return EXIT_SUCCESS;}