8Queens

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

void comb(int x, int y, int polje[8][8], int coords[12][8][2], int *n); //Ispituje sve mogucnosti za polozaj kraljica
void motionQ(int x, int y, int polje[8][8]); //Ucrtava u polje kuda se kraljica moze kretati
int Num_Of_Queens(int polje[8][8]); //Vraca broj kraljica u polju
void SolExist(int CurCoords [8][2], int coords[12][8][2], int *n); // Provjerava dali rjesenje vec postoji
void rotate90(int coords[8][2]); //Rotira figure za 90
void sort(int coords[8][2]); //Sortira koordinate po retku i stupcu
void mirrorX(int coords[8][2]); //Zrcali figure s obzirom na X os
void mirrorY(int coords[8][2]); //Zrcali figure s obzirom na Y os

int main()
{
    int coords[12][8][2];
    int n = 0;

    for(int i = 0; i<8; i++)
    {
        for(int j = 0; j<8; j++)
        {
            int polje[8][8] = {};

            comb(i, j, polje, coords, &n);
        }
    }

    for(int i = 0; i<n; i++)
    {
        int l = 0;
        for(int j = 0; j<8; j++)
        {
            for(int k = 0; k<8; k++)
            {
                if(coords[i][l][0] == j && coords[i][l][1] == k)
                {
                    l++;
                    printf("1 ");
                }
                else printf("0 ");
            }
            printf("\n");
        }

        for(int j = 0; j<8; j++)
        {
            printf("%c %d | ", 65+coords[i][j][1], -1*coords[i][j][0]+8);
        }
        printf("\n\n");
    }

    printf("Broj rjesenja: %d", n);

    return 0;
}

void comb(int x, int y, int polje[8][8], int coords[12][8][2], int *n)
{
    polje[x][y] = 2;

    motionQ(x, y, polje);

    for(int i = 0; i<8; i++)
    {
        for(int j = 0; j<8; j++)
        {
            if(polje[i][j] == 0)
            {
                int polje2[8][8] = {};
                memcpy(polje2, polje, 64*sizeof(int));

                comb(i, j, polje2, coords, n);
                int NumOfQ = Num_Of_Queens(polje2);

                if(NumOfQ==8)
                {
                    int CurCoords[8][2];
                    int z = 0;
                    for(int k = 0; k<8; k++)
                    {
                        for(int l = 0; l<8; l++)
                        {
                            if(polje2[k][l] == 2)
                            {
                                CurCoords[z][0] = k;
                                CurCoords[z++][1] = l;
                            }

                        }
                    }
                    SolExist(CurCoords, coords, n);
                }
            }
        }
    }
}

void motionQ(int x, int y, int polje[8][8])
{
    for(int i = 0; i<8; i++)
    {
        if(polje[i][y] != 2) polje[i][y] = 1;
        if(polje[x][i] != 2) polje[x][i] = 1;
    }

    int i = x-1;
    int j = y-1;
    while(i>=0 && j>=0 && i<=7 && j<=7)
    {
        if(polje[i][j] != 2) polje[i][j]  = 1;
        i = i-1;
        j = j-1;
    }

    i = x-1;
    j = y+1;
    while(i>=0 && j>=0 && i<=7 && j<=7)
    {
        if(polje[i][j] != 2) polje[i][j] = 1;
        i = i-1;
        j = j+1;
    }

    i = x+1;
    j = y-1;
    while(i>=0 && j>=0 && i<=7 && j<=7)
    {
        if(polje[i][j] != 2) polje[i][j] = 1;
        i = i+1;
        j = j-1;
    }

    i = x+1;
    j = y+1;
    while(i>=0 && j>=0 && i<=7 && j<=7)
    {
        if(polje[i][j] != 2) polje[i][j] = 1;
        i = i+1;
        j = j+1;
    }
}

int Num_Of_Queens(int polje[8][8])
{
    int count = 0;
    for(int i=0; i<8; i++)
    {
        for(int j=0; j<8; j++)
        {
            if(polje[i][j] == 2) count++;
        }
    }
    return count;
}

void SolExist(int CurCoords[8][2], int coords[12][8][2], int *n)
{
    int b;
    if(n>0)
    {
        for(int i = 0; i<*n; i++)
        {
            for(int k = 0; k<4; k++)
            {
                if(k>0) rotate90(CurCoords);
                b = 0;
                for(int j=0; j<8; j++)
                {
                    if(coords[i][j][0] == CurCoords[j][0] && coords[i][j][1] == CurCoords[j][1]) b++;
                }
                if(b==8) break;

                b=0;
                mirrorX(CurCoords);
                for(int j=0; j<8; j++)
                {
                    if(coords[i][j][0] == CurCoords[j][0] && coords[i][j][1] == CurCoords[j][1]) b++;
                }
                mirrorX(CurCoords);
                if(b==8) break;

                b=0;
                mirrorY(CurCoords);
                for(int j=0; j<8; j++)
                {
                    if(coords[i][j][0] == CurCoords[j][0] && coords[i][j][1] == CurCoords[j][1]) b++;
                }
                mirrorY(CurCoords);
                if(b==8) break;
            }

            if(b==8) break;
        }
    }

    if(b!=8 || *n == 0)
    {
        for(int i = 0; i<8; i++)
        {
            coords[*n][i][0] = CurCoords[i][0];
            coords[*n][i][1] = CurCoords[i][1];
        }
        (*n)++;
    }
}

void rotate90(int coords[8][2])
{
    for(int i = 0; i<8; i++)
    {
        int x = coords[i][0];
        coords[i][0] = coords[i][1];
        coords[i][1] = 7-x;
    }
    sort(coords);
}

void sort(int coords[8][2])
{
    for (int i = 1; i < 8; i++)
    {
        int tmp[2] = {coords[i][0], coords[i][1]};

        int j = i;
        while (j > 0 && coords[j - 1][0] > tmp[0])
        {
            coords[j][0] = coords[j - 1][0];
            coords[j][1] = coords[j - 1][1];
            j--;
        }
        coords[j][0] = tmp[0];
        coords[j][1] = tmp[1];
    }
}

void mirrorX(int coords[8][2])
{
    for(int i = 0; i<8; i++)
    {
        coords[i][1]= 7-coords[i][1];
    }
    sort(coords);
}

void mirrorY(int coords[8][2])
{
    for(int i = 0; i<8; i++)
    {
        coords[i][0]= 7-coords[i][0];
    }
    sort(coords);
}