8 Задача Queen: почему рекурсивная функция продолжает выполняться, если условие равно false

Question

Я решил проблему 8 ферзей, не понимая, почему рекурсивная функция продолжает выполняться, если условие while loop равно false.

Код с приведенным ниже решением работает идеально. Это печатает все возможные решения и общее количество решений.

Логика кода состоит в том, чтобы проверить, не подвергается ли текущая строка столбцов атаке какого-либо ранее помещенного ферзя, если нет - установить ферзь и перейти к следующему столбцу, если это так - проверить те же столбцы в следующей строке.

Когда place_queen(int col) вызывается впервые, когда я передаю параметр 0, ведьма означает, что программа начинает искать решения, начиная со столбца 0.

Итак, передо мной шахматная доска, и я следую ей своему коду. Я заполнил кол 0,1,2,3 и 4 table[0] = 1; table[1] = 3; table[2] = 5; table[3] = 2; table[4] = 4;

Сейчас я нахожусь на 5-й колонке, и в этом столбце нет безопасных строк. Я достигаю table[5] = 9, что означает, что я закончил цикл while, потому что условие table[5] <= 8 неверно.

Мои вопросы:

1. Почему код продолжает выполняться, если условие цикла while ложно, когда я впервые достигаю 5-й столбец 9-й строки?
2. Почему программа из столбца 5 возвращается в столбец 4 и продолжает поиск следующей безопасной строки, если в коде нет места, указывающего на это?

Код:

#include <stdio.h>
int count = 0;
int table[8] = {};

int     is_safe(int col) 
{
int c = col - 1;
int i = 1;  

while(c >= 0)
{   
    if( table[col] == table[c] || table[col] == table[c] - i  || (table[col]) ==  table[c] + i)  
            return 0;
    i++;    
    c--;
}

return 1;
}


void    place_queen(int col)
{   
    table[col] = 1;
    while(table[col] <= 8)
    {
        if(is_safe(col))
        {
            if(col == 7)
        {           
            count++;
            for(int i = 0; i < 8; i++)
                printf("%d", table[i]);

            printf("\n");
        }
        else
            place_queen((col + 1));
    }

    table[col]++;
    }   
}


int      eight_queens(void)
{   
    place_queen(0);

    return count;
} 

P.S. Индексы столбцов от 0 до 7, а индексы строк от 1 до 8.

Answer 1

Звонок с col==5 не продолжается.Он возвращает, а затем вызов с col==4 увеличивает строку для столбца 4 и продолжает идти.Примерно так:

• place_queen (4): цикл выполняется 3 раза, поэтому строки равны 13524, затем is_safe(4) возвращает true и вызывается place_queen(5).
  • place_queen (5): цикл выполняется 8 раз, is_safe(5) никогда не выполняется и функция завершается
• place_queen (4): продолжается, завершает циклитерации и выполняет ее еще 3 раза, поэтому строки 13528 и is_safe(4) снова истина.
  • place_queen (5): цикл выполняется 8 раз, is_safe(5) никогда не выполняется и функция завершается
• place_queen (4): продолжается и т. Д ...