8 Queens puzzle with recursive deep search

Question

I'm trying to solve the 8 queens puzzle problem in C. I'm having problems with the recursive search. The program is supposed to start at a given column:

 execute(tabuleiro,8,0);

Where the 8 is the number of columns in the board, and 0 is the start column.

This works when I start at column 0. When I send any other column number to the recursive search, the program just counts to the last column. For example, if I choose to start the search from the number 5 column, the code search from the column 5 to 7, after this it should search from 0 to 4, but it doesn't do that.

If I do this:

execute(tabuleiro,8,3);

It fills in only the last 5 colummns, and does not return to column 0 to finish the solution:

Also, how can I select the initial position for the queen in this code? Like I said before, the column is assigned in the code, but I'm not sure how to pick the correct column.

The code has 3 functions: one is to display the board, a second to check if the move is legal (so one queen doesn't attack the other), and the last one to place one queen and recur for the remainder of the board.

#include <stdlib.h>
#include <windows.h>
int sol = 0;
void viewtab(int tab[][8], int N)
{
    int i,j;
    for( i = 0; i < N; i++)
    {
        for( j = 0; j < N; j++)
        {

            if(tab[i][j] == 1)
                printf("R\t");
            else
                printf("-\t");
        }
        printf("\n\n");
    }
    printf("\n\n");
    system("pause");
    printf("\n");
}
int secury(int tab[][8], int N, int lin, int col)
{
    // this function is to check if the move is secury
    int i, j;

    // attack in line
    for(i = 0; i < N; i++)
    {
        if(tab[lin][i] == 1)
            return 0;
    }

    //attack in colune
    for(i = 0; i < N; i++)
    {
        if(tab[i][col] == 1)
            return 0;
    }

    // attack in main diagonal
    //
    for(i = lin, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if(tab[i][j] == 1)
            return 0;
    }
    for(i = lin, j = col; i < N && j < N; i++, j++)
    {
        if(tab[i][j] == 1)
            return 0;
    }

    // attack in main secondary

    for(i = lin, j = col; i >= 0 && j < N; i--, j++)
    {
        if(tab[i][j] == 1)
            return 0;
    }
    for(i = lin, j = col; i < N && j >= 0; i++, j--)
    {
        if(tab[i][j] == 1)
            return 0;
    }

    // if arrive here the move is secury and return true
    return 1;
}
void execute(int tab[][8], int N, int col)
{
    int i;
    if(col == N)
    {
        printf("Solution %d ::\n\n", sol + 1);
        viewtab(tab, N);
        sol++;
        return;
    }

    for( i = 0; i < N; i++)
    {
        // check if is secury to put the queen at that colune
        if(secury(tab, N, i, col))
        {
            // insert the queen (with 1)
            tab[i][col] = 1;

            // call recursive
            execute(tab, N, col + 1);

            // remove queen (backtracking)
            tab[i][col] = 0;
        }
    }
}
int main()
{
    int i, j, tabuleiro[8][8];
    for (i = 0; i < 8; i = i + 1)
        for (j = 0; j < 8; j = j + 1) tabuleiro[i][j] = 0;

    execute(tabuleiro,8,0);

    return 0;
}

Answer 1

The search always stops in the rightmost column because you specifically tell it to stop there:

void execute(int tab[][8], int N, int col)
{
    int i;
    if(col == N)
    {
        printf("Solution %d ::\n\n", sol + 1);
        viewtab(tab, N);
        sol++;
        return;
    }

Look at your termination condition: you check the current column against the highest column number, and stop there.

If you want to go back to column 0, you have to change your loop logic. For instance, let col reach N, at which point you reset it to 0, and let it continue until you hit the original value. Another way is to continue until the count of placed queens is N.

---

You choose the initial point in the same way: you pick the first one and make your recursive call. If that eventually results in a solution, you print it. If not, your top-most call continues to the next row (line) of the board and puts the first queen there.

This is already in your main logic. Just make sure that secury will return true when the board is empty, rather than false or throwing an error.