12 knights (chess) to dominate all squares

Question

ubhart 0 Newbie Poster

10 Years Ago

Hi, I am making program that finds solution how to put 12 knights(horses) to chess board that every square is dominated or engaged by other knight.
Look at my code:

#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?

c

2 Contributors
2 Replies
273 Views
22 Hours Discussion Span
Latest Post 10 Years Ago Latest Post by ubhart

rubberman 1,355 Nearly a Posting Virtuoso

10 Years Ago

You would fail my class... :-( DO NOT fail to use curly-braces to delimit ALL conditional statements and loops. This is one of the biggest causes of system logic issues...

Fix that, and I'll take another look at your code.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

ubhart 0 Newbie Poster · Answer 1 · 2014-03-26T20:43:30+00:00

@rubberman , you mean like this:

#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 <10; 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]='*';
                    }
                    // return true;
                }
                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;
    }
    int cnt=0;
    for( i=1 ; i<9; i++)
    {
        for (j=1 ; j<9; j++)
        {

            if (L[i][j]=='0')
            {
                cnt++;
            }


        }
    }
    //printf("%d\n", cnt);
    if(cnt==0) return true;
    else 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))
                {
                    L[i+N[o]][j+M[o]]='0';
                    z=z-1;
                }
                else break;
            }
            o=o+1;
        }
    }
    else
    {

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

            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");

}