Inhalt | Code | Beispiel |
C | Javascript | Kommentare | Zeilennummern | Midnight |
// Author Malte Pagel
// main.c
#include <stdio.h>
#include <stdlib.h>
void show_all(int *);
int set_queen(int *, int);
int possible(int *, int);
int num_cols = 8;
int all_solutions = 0;
void show_all ( int *cols ) {
int x, y;
printf("\t");
for ( y = 1; y <= num_cols; y++ ) {
for ( x = 0; x < num_cols; x++ )
if ( cols[x] == y )
printf(" Q ");
else
printf(" . ");
printf("\n\t");
}
}
int possible ( int *cols, int queen ) {
int i;
int col = num_cols - queen;
for ( i = (col + 1); i < num_cols; i++ ) {
if ( cols[col] == cols[i] ) // horizontal
return 0;
if ( abs(col - i) == abs(cols[col] - cols[i]) ) // diagonal
return 0;
}
return 1;
}
int set_queen ( int *cols, int which ) {
int queen, suggest = 1;
static int count = 1;
queen = num_cols - which;
while ( suggest <= num_cols ) {
cols[which] = suggest;
if ( possible(cols, queen) )
if ( which ) {
if ( set_queen(cols, (which-1)) )
return 1;
}
else {
if ( all_solutions )
printf("\nSolution %2d:\n", count++);
show_all(cols);
if ( !all_solutions )
return 1;
}
suggest++;
}
cols[which] = 0;
return 0;
}
int main ( int argc, char *argv[] ) {
printf("\n\n\t%d queens with no two queens attacking each other\n\n", num_cols);
// *cols is NOT a binary matrix in two dimensions;
// since it is known that every column owns one queen,
// row position of queen is stored in every value of *cols
int *cols, i;
char c;
cols = malloc(num_cols * sizeof(int *));
for ( i = 0; i < num_cols; i++ )
cols[i] = 0;
set_queen(cols, (num_cols-1));
printf("\nShow all solutions? [y/n]\n");
scanf("%c", &c);
if ( c == 'y' ) {
all_solutions = 1;
printf("\nHow many rows resp. columns? [more than 8 could be unhealthy]\n");
scanf("%d", &num_cols);
cols = malloc(num_cols * sizeof(int *));
for ( i = 0; i < num_cols; i++ )
cols[i] = 0;
set_queen(cols, (num_cols-1));
}
free(cols);
printf("\n\n");
return EXIT_SUCCESS;
}