Member Avatar for 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?

  • 3 Contributors
  • 3 Replies
  • 535 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by ubhart

Dani AI

Generated

A focused follow-up for that ties the earlier tips from and into concrete fixes and a safer backtracking flow.

The approach (pick an uncovered square and try every knight position that covers it) is fine; using a physical board is great for intuition () and the colour-parity observation () is valuable for pruning: knight moves flip square colour, so precompute coverers by colour to cut the search space.

Primary defects found in the posted code (these explain the “not dominated” result):

  • The dominance check returns early. A stray return true; makes every partial configuration look complete. Replace it with a simple scan that returns false if any undominated square remains.
  • Undo/restore of domination marks is missing. After removing a knight the program must recompute domination (re-run the function that sets '*') — otherwise old '*' marks persist and hide uncovered squares.
  • Bounds and order of checks cause out-of-range access. Conditions like L[i][j] != '0' && i < 9 evaluate L[i][j] before ensuring i is valid; switch the order or use 0-based loops (0..7) to avoid undefined behaviour. Also avoid <=9 — iterate exactly over the 8 board rows/cols.
  • Backtracking must propagate success. Return a bool (or set a global flag) from the recursive function so the search stops when a valid 12‑knight solution is found.

Minimal corrective sketches (use 0-based board for clarity):

bool fully_dominated(const char B[8][8]) {
  for (int r = 0; r < 8; ++r)
    for (int c = 0; c < 8; ++c)
      if (B[r][c] == '.') return false;
  return true;
}
/* backtracking sketch */
if (find_first_uncovered(B) < 0) { print_board(B); return true; }
for (each candidate S that covers that cell) {
  B[S] = 'K'; recompute_domination(B);
  if (backtrack(B, placed+1)) return true;
  B[S] = '.'; recompute_domination(B); /* must recompute after undo */
}
return false;

Performance tips: precompute, for each of the 64 squares, a bitmask (uint64_t) of the squares dominated by a knight placed there; update coverage with OR operations when placing/removing knights. Use a heuristic: pick the uncovered square with the fewest candidate knights (minimum branching). Use branch-and-bound (placed + lower_bound > 12 prune). These changes make the search both correct and fast.

Recommended Answers

All 3 Replies

Member Avatar for Ancient Dragon

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

Member Avatar for 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.

Member Avatar for 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?

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.