12 knights to dominate all squares of chess board 8x8

[ubhart]

Hi I have to write program that finds a solution how to put 12 knights to a 8x8 chess board that every square would be dominated by one of the 12 knights. Do you have any suggestions from where I can start?

[Ancient Dragon]

My suggestion is to start by playing the game on a real board so that you see how it works.

[Banfa]

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.

[ubhart]

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?