3
Contributors
3
Replies
20
Views
2 Years
Discussion Span
Last Post by ubhart
0

Understanding the problem is very import to this kind of problem because while you may have to brute force the final solution understanding the problem can help you reduce the complexity making that brute force attack easier.

For example in the problem of placing 8 chess queens on a chess board such that no queen can take any other queen recognising that because a chess board has 8 rows and columns there will need to be only 1 queen in any row or column and 1 queen in every row and column helps reduce the complexity of the problem.

In this case you can use the fact that a knight on a white square attacks only black squares and vice-versa to reduce your problem complexity.

0

Here is what i have so far:

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



    //(*******************************************************************************)
    void addNulls(char L[][9], int N[], int M[])
    {
        int i,j,g;

        for (i=1 ; i<9 ; i++)
            for (j=1 ; j<9 ; j++)
                if (L[i][j]!='K')
                    L[i][j]='0';
        for (i=1 ; i <9 ; i++)
            for (j=1 ; j <9; j++)
                if (L[i][j]=='K')
                    for (g=1 ; g <9; g++)
                        if (i+N[g]>0&&i+N[g]<9 && j+M[g]>0 && j+M[g]<9 && L[i+N[g]][ j+M[g]] == '0')
                            L[i+N[g]][ j+M[g]] = '*';
    }
    //(*******************************************************************************)
    bool checkIf(char L[][9], int N[], int M[])
    {
        int i, j;

        for ( i=1 ; i<9; i++)
            for (j=1 ; j <9; j++)
                if (L[i][j]=='K')
                {
                    if (i-2>0)
                    {
                        if (j-1>0 && L[i-2][j-1]=='0')
                            L[i-2][j-1]='*';
                        if (j+1<9 && L[i-2][j+1]=='0')
                            L[i-2][j+1]='*';
                        if (j-2>0 && L[i-1][j-2]=='0')
                            L[i-1][j-2]='*';
                        if (j+2<9 && L[i-1][j+2]=='0')
                            L[i-1][j+2]='*';
                    }
                    else if (i-1>0)
                    {
                        if (j-2>0 && L[i-1][j-2]=='0')
                            L[i-1][j-2]='*';
                        if (j+2<9 && L[i-1][j+2]=='0')
                            L[i-1][j+2]='*';
                    }
                    if (i+2<9)
                    {
                        if (j-1>0 && L[i+2][j-1]=='0')
                            L[i+2][j-1]='*';
                        if (j+1<9 && L[i+2][j+1]=='0')
                            L[i+2][j+1]='*';
                        if (j-2>0 && L[i+1][j-2]=='0')
                            L[i+1][j-2]='*';
                        if (j+2<9 && L[i+1][j+2]=='0')
                            L[i+1][j+2]='*';
                    }
                    else if (i+1<9)
                    {
                        if (j-2>0 && L[i+1][j-2]=='0')
                            L[i+1][j-2]='*';
                        if (j+2<9 && L[i+1][j+2]=='0')
                            L[i+1][j+2]='*';
                    }
                }
        return true;
        for( i=1 ; i<=9; i++)
            for (j=1 ; j<=9; j++)
            {
                if (L[i][j]=='0')
                    return false;
            }
    }
    //(*******************************************************************************)
    void printBoard(char L[][9])
    {
        int i,j;

        for (i=1 ; i<9 ; i++)
        {
            for (j=1 ; j<9 ; j++)
            {
                printf("%2c|",L[i][j]);
            }
            printf("\n");
            j=1;
        }
    }
    //(*******************************************************************************)
    void modeling(char L[][9], int N[], int M[], int z)
    {
        int i,j,o;

        i=1;
        j=1;
        if (z<12)
        {
            while (L[i][j]!='0' && i<9)
            {
                j=j+1;
                if (j==9)
                {
                    j=1;
                    i=i+1;
                }
            }
            o=1;
            while (o<10)
            {
                if (i+N[o]>0 && j+M[o]>0 && i+N[o]<9 && j+M[o]<9 && L[i+N[o]][j+M[o]]!='K')
                {
                    L[i+N[o]][j+M[o]]='K';
                    addNulls(L,N,M);
                    z=z+1;
                    modeling(L,N,M,z);
                    if (checkIf(L,N,M)==false)
                    {
                        L[i+N[o]][j+M[o]]='0';
                        z=z-1;
                    }
                    else break;
                }
                o=o+1;
            }
        }
        else
        {

            if (checkIf(L,N,M)==true)
            {

                printBoard(L);

            }
        }
    }
    //(*******************************************************************************)
    main()
    {
        char L[9][9]; // chess board
        int N[10],M[10]; //traverses

        N[1]=1;
        M[1]=2;
        N[2]=1;
        M[2]=-2;
        N[3]=2;
        M[3]=-1;
        N[4]=2;
        M[4]=1;
        N[5]=-2;
        M[5]=-1;
        N[6]=-2;
        M[6]=1;
        N[7]=-1;
        M[7]=-2;
        N[8]=-1;
        M[8]=2;
        N[9]=0;
        M[9]=0;
        addNulls(L,N,M);
        modeling(L,N,M,0);
        printf("end");

    }

I don't get the right output because there are some not dominated squares left.
Maybe you can spot my mistake?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.