8 Queens Problem

/**
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
/**
 * Author: Pratanu Mandal
 * Date:   24-11-2017
 * Desc:   N-Queens problem using genetic algorithm
 *
 * Copyright © Pratanu Mandal, 2017
 */


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


/** parameters */
#define NQUEENS      8   // no. of queens
#define POP        100   // count of population
#define M_RATE      10   // mutation rate
#define LIMIT       -1   // limit - maximum no. of iterations, -1 = infinity

#define SHOW_GEN     0   // show generations 0 = FALSE, 1 = TRUE


/** global variables */
int ** genX;     // generation X
int ** genY;     // generation Y or X+1
float * fitness; // fitness values for generation X

void display();
void calcFitness();


/**
 * method to initialize variables
 */
void init()
{
    // initialize random seed
    srand(time(NULL));

    // initialize generations
    genX = (int **) malloc(sizeof(int *) * POP);
    genY = (int **) malloc(sizeof(int *) * POP);

    // randomly generate initial population
    for (int i = 0; i < POP; i++) {
        genX[i] = (int *) malloc(sizeof(int) * NQUEENS);
        genY[i] = (int *) malloc(sizeof(int) * NQUEENS);

        for (int j = 0; j < NQUEENS; j++) {
            int flag, val;
            do {
                flag = 0;
                val = rand() % NQUEENS;
                for (int k = 0; k < j; k++) {
                    if (val == genX[i][k]) {
                        flag = 1;
                        break;
                    }
                }
            } while(flag);
            genX[i][j] = val;
        }
    }

    // initialize fitness array
    fitness = (float *) malloc(sizeof(float) * POP);
}


/**
 * method to calculate the fitness of population of generation X
 */
void calcFitness()
{
    for (int i = 0; i < POP; i++) {

        int clash = 0;

        // check horizontally
        for (int j = 0; j < NQUEENS; j++) {
            for (int k = j+1; k < NQUEENS; k++) {
                if (genX[i][j] == genX[i][k]) {
                    clash++;
                }
            }
        }

        // check diagonally
        for (int j = 0; j < NQUEENS; j++) {
            for (int k = 0; k < NQUEENS; k++) {
                if (j != k) {
                    int dx = abs(j - k);
                    int dy = abs(genX[i][j] - genX[i][k]);
                    if (dx == dy)
                        clash++;
                }
            }
        }

        // if goal, fitness is 1.0
        fitness[i] = 1.0f / (1.0f + clash);
    }
}


/**
 * method to select one parent
 */
int selectParent()
{
    // using tournament selection - much faster, and suitable for floating values
    int sz = (int)(POP * 0.2), c;

    int candidate[sz];

    for (int i = 0; i < sz; i++) {
        int flag = 0;
        do {
            c = rand() % POP;
            flag = 0;
            for (int j = 0; j < i; j++) {
                if (candidate[j] == c) {
                    flag = 1;
                    break;
                }
            }
        } while (flag);

        candidate[i] = c;
    }

    int index = 0;

    for (int i = 1; i < sz; i++) {
        if (fitness[candidate[i]] > fitness[candidate[index]]) {
            index = i;
        }
    }

    return index;
}


/**
 * method to perform crossover on generation X
 */
void crossover()
{
    for (int i = 0; i < POP; i++) {
        int p1 = selectParent();
        int p2 = selectParent();

        if (p1 == p2) {     // single parent
            memcpy(genY[i], genX[p1], sizeof(int) * NQUEENS);
        }
        else {  // crossover
            // take a gene from either parent based on a 50% chance
            // once a gene is taken, it cannot be repeated
            for (int j = 0; j < NQUEENS; j++) {
                int px;
                if (rand() % 2) px = p1;
                else px = p2;

                int k;
                for (k = 0; k < NQUEENS; k++) {
                    int flag = 0;
                    for (int m = 0; m < j; m++) {
                        if (genX[px][k] == genY[i][m]) {
                            flag = 1;
                            break;
                        }
                    }
                    if (!flag) break;
                }

                if (k == NQUEENS) {
                    // we have exhausted parent px
                    j--;
                    continue;
                }

                genY[i][j] = genX[px][k];
            }
        }
    }

    // swap generations
    int ** temp = genX;
    genX = genY;
    genY = temp;
}


/**
 * perform mutation on generation Y (now stored in generation X)
 */
void mutation()
{
    // using swapping mutation
    for (int i = 0; i < POP; i++) {
        int r = rand() % 100;

        if (r <= M_RATE) {
            int j = rand() % NQUEENS;
            int k;
            do {
                k = rand() % NQUEENS;
            } while (j == k);

            int temp = genX[i][j];
            genX[i][j] = genX[i][k];
            genX[i][k] = temp;
        }
    }
}


/**
 * method to free all variables
 */
void destroy()
{
    for (int i = 0; i < POP; i++) {
        free(genX[i]);
        free(genY[i]);
    }

    free(genX);
    free(genY);
}


/**
 * utility method to display the population of a generation X
 */
void display()
{
    for (int i = 0; i < POP; i++) {
        for (int j = 0; j < NQUEENS; j++) {
            printf(" %d ", genX[i][j]);
        }
        printf("| %f %d\n", fitness[i], i);
    }
}


/**
 * utility method to display the solution
 */
void displayQueens(int index)
{
    for (int i = 0; i < NQUEENS; i++) {
        for (int j = 0; j < NQUEENS; j++) {
            if (genX[index][i] == j)
                printf(" Q ");
            else
                printf(" . ");
        }
        printf("\n\n");
    }
}


/**
 * method implementing the genetic algorithm
 *
 * limit: the maximum no. of generations to be searched for a solution
 *        if set to -1, the limit is infinity
 *
 * found (return): -1 if not found, non-negative int otherwise
 */
int geneticAlgorithm(int limit)
{
    int found = -1;

    for (int i = 0; limit == -1 || i <= limit; i++) {
        // calculate fitness of generation X
        calcFitness();

        if (SHOW_GEN) {
            printf("[Generation %d]\n", i);
            display();
            printf("\n\n");
        }

        // find the fittest candidate of generation i
        int index = 0;  // assuming that fitness[0] contains largest value
        for (int j = 1; j < POP; j++) {
            if (fitness[j] > fitness[index])
                index = j;
        }

        // if fittest candidate has reached desired fitness, terminate
        if (fitness[index] == 1.0f) {
            found = index;
            break;
        }

        crossover();    // perform crossover
        mutation();     // perform mutation
    }

    return found;
}


/**
 * method that is to be used as an entry-point
 * initializes, executes GA, displays results, and cleans up
 */
void run()
{
    init();

    int found = geneticAlgorithm(LIMIT);

    if (found == -1) {
        printf("\nSolution not found\n");
    }
    else {
        printf("\nSolution: ");
        for (int i = 0; i < NQUEENS; i++) {
            printf("%d ", genX[found][i]);
        }
        printf("\n\n\n");

        displayQueens(found);
    }

    destroy();
}


/**
 * main - entry point to program
 * dispatch execution to other methods
 */
int main()
{
    run();

    printf("\n\nPress [ENTER] to continue ...");
    getchar();

    return 0;
}