/**
 * Author Malte Pagel
 * Free to use for any purpose
 * Runability or usefulness is NOT guaranteed
 */


// main.c

#include <stdio.h>
#include <stdlib.h>


void show_all(int *);
int set_queen(int *, int);
int possible(int *, int);


/*
 * Default; can be changed by user for to get squares of different size
 */
int num_cols = 8;
/*
 * Quasi boolean
 */
int all_solutions = 0;


/*
 * Displays a solution; shows Queen as 'Q' and empty field as '.'
 */
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");
        }
}

/*
 * Prooves if a queen can be set.
 * Does NOT proove columns (it is known that every column can only own one queen).
 * Prooves only against already set columns.
 */
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;
}
/*
 * Recursive function.
 * Tries every row in every column:
 *      - if a queen attacks an already set queen, try was bad.
 *      - if she doesn't, but the next queen attacks an already set queen, try also was bad.
 *      - if queen is allowed and there are no columns left, try was good.
 * When variable 'all_solutions' is not set, function stops after finding first solution
 */
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;
}



/*
 * Initialization:
 * Searches for one solution on chess table (num_cols = 8).
 * Asks user for number of columns ( = number of rows, table is square).
 * Allocates memory and starts 'set_queen()' with first (i.e. most right) column.
 */
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;
}