Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Place 8 Queens on Chessboard
project(eight_queens)
cmake_minimum_required(VERSION 2.8)
aux_source_directory(. SRC_LIST)
add_executable(${PROJECT_NAME} ${SRC_LIST})
#include <stdio.h>
#include <assert.h>
#define ROWS 8
#define COLS ROWS
typedef int field_t[ROWS][COLS];
void print_field(field_t *f)
{
for (int r = 0; r < 8; r++)
{
for (int c = 0; c < 8; c++)
{
printf(" %c ", ((*f)[r][c] ? '*': '.'));
}
printf("\n");
}
}
int is_position_under_attack(field_t *f, int r, int c)
{
int dc[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dr[8] = { 0, 1, 1, 1, 0, -1, -1, -1};
for (int d = 0; d < 8; d++)
{
int max_len = (ROWS > COLS ? ROWS : COLS);
for (int l = 1; l < max_len; ++l)
{
int nr = r + l * dr[d];
int nc = c + l * dc[d];
if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS)
continue;
if ((*f)[nr][nc])
return 1;
}
}
return 0;
}
int place_queens(field_t *f, int r)
{
if (r >= ROWS)
{
// All queens placed. Return success.
return 1;
}
for (int c = 0; c < COLS; ++c)
{
if (!is_position_under_attack(f, r, c))
{
(*f)[r][c] = 1;
if (place_queens(f, r + 1))
{
// Successfully placed all remaining queens.
return 1;
}
(*f)[r][c] = 0;
}
}
// No such placement.
//printf("falling back!\n");
//print_field(f);
return 0;
}
int main()
{
field_t f = {0};
int result = place_queens(&f, 0);
if (result)
{
print_field(&f);
}
else
{
printf("No such placement.\n");
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.