Как узнать, есть ли в массиве последовательные числа в C++?

По сути, это проблема 8 ферзей, но решение ее грубой силой в одномерном массиве. Скажем, у меня есть массив (с именем b) размера 8 с элементами от 0 до 7.

Я инициализирую каждый индекс в массиве 8 циклами for, например так:

int b[8]={0};

int count = 0;


for(b[0] = 0; b[0]<8; b[0]++){ 
for(b[1] = 0; b[1]<8; b[1]++){ 
for(b[2] = 0; b[2]<8; b[2]++){ 
for(b[3] = 0; b[3]<8; b[3]++){ 
for(b[4] = 0; b[4]<8; b[4]++){ 
for(b[5] = 0; b[5]<8; b[5]++){
for(b[6] = 0; b[6]<8; b[6]++){
for(b[7] = 0; b[7]<8; b[7]++){
                if(check(b)) 
                {
                count++;
                print(b, count);
                }
            }}
        }}
    }}
}}

Эта программа должна проверять каждую комбинацию чисел от 0 до 7 и возвращать true только для определенных условий. Предполагается, что должно быть 92 решения, если это звучит знакомо, так и должно быть — это проблема 8 ферзей с использованием грубой силы. Отсюда я понимаю, что это условия:

Я хочу иметь возможность проверить, имеет ли массив последовательную строку чисел; такие как:

[0|5|7|1|2|3|6|4]

Здесь элементы b[3], b[4] и b[5] идут подряд. Я не хочу этого, я хочу вернуть false, так как есть последовательная строка чисел (в основном атакуют ферзи)

Мне также не нужен массив, содержащий строку последовательных чисел, идущих в обратном направлении, например:

[0|5|7|3|2|1|6|4]

И, наконец, мне не нужны два или более числа в индексах, где они выглядели бы последовательными, если бы мы просто изменили числа между ними:

[0|2|4|6|1|3|5|7]

Вышеупомянутое неприемлемо, потому что b[0] и b[7] являются числами в их «последовательном индексе» (поскольку по крайней мере 2 ферзя атакуют друг друга).

[6|1|3|0|4|7|5|2]

Выше также неприемлемо, потому что b[1] и b[4] также находятся в последовательных индексах.

Точно так же, когда значения меняются местами, массивы

[7|2|4|6|1|3|5|0]

[6|4|3|0|1|7|5|2]

также не приемлемы. Я также не могу иметь 2 или более одинаковых номеров.

Проблема, с которой я сталкиваюсь, заключается в создании функции проверки. Мне сказали, что мне нужно использовать 1 цикл for и 1 оператор if-then. Может ли функция проверки просто взять весь массив как есть? И если да, то как посмотреть на самый правый элемент в массиве и проверить, есть ли у него последовательные индексы (на него нападают ферзи)? Я пробовал это:

bool ok(int board[8]){

    for(int c = 7; c >= 0; c--){ //row check
        for (int j=0; j<c; j++){
            if (board[c]==board[j]){
                return false;
            }
        }


        for(int i = 1; i <= c; i++){
            // diagonal check from top left to bottom right
            if  ((board[c]-i >= 0) && (board[c-i] == board[c]-i))
                {return false;}
            if ((board[c]+i <= 7) && (board[c+i] == board[c]+i))
                {return false;}
            // diagonal check from bottom left to top right
            if ((board[c]-i >= 0) && (board[c-i] == board[c]+i))
                {return false;}
            if ((board[c]+i <= 7) && (board[c+i] == board[c]-i))
                {return false;}

        }

    }

    return true;
}

Но это не только не работает (я получаю более 300 решений), но и не так мало, как мне говорят.


c++ arrays function n-queens
person Ishmael    schedule 03.03.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я думаю, что есть небольшая проблема с вашей проверкой столкновений по диагоналям: у вас есть 15 диагоналей, идущих в каждую сторону (включая очень короткие диагонали в один квадрат в углах), в то время как ваш код проверяет только семь из каждой из-за board[c]+i <= 7 и board[c]-i >= 0 условия.

Вот как вы можете упростить проверки и ускорить их, используя три булевых массива: у вас есть 8 строк, 15 восходящих диагоналей и 15 нисходящих диагоналей:

bool row[8];
bool ascending[15];
bool descending[15];

Изначально ни в одном из этих рядов/диагоналей нет ферзей. Проходя элементы board, делайте так:

for (int i = 0 ; i != 8 ; i++) {
    // Check and mark the row
    if (row[board[i]]) return false;
    row[board[i]] = true;
    // Check and mark the ascending diagonal
    int ascIdx = board[i]+i;
    if (ascending[ascIdx]) return false;
    ascending[ascIdx] = true;
    int descIdx = 7+board[i]-i;
    if (descending[descIdx]) return false;
    descending[descIdx] = true;
}
return true;
person Sergey Kalinichenko    schedule 03.03.2013
comment
Извините, я не знаком с логическими массивами (даже не знал, что они существуют), не могли бы вы уточнить, что именно if (row[board[i]]) return false; выполняет? Я понимаю, что это проверка истинности условия, но для чего она проверяет истинность или ложность? - person Ishmael; 03.03.2013
comment
@Chase Как вы правильно догадались, логические массивы хранят логические значения (true или false). Первоначально массивы должны быть установлены в false, потому что bool — это примитивный тип (я не показывал этот код в ответе, но по сути вам нужен цикл, устанавливающий каждый элемент массива в false). Когда вы обращаетесь к элементу по определенному индексу, вы возвращаете последнее сохраненное там значение. То, что происходит в приведенных выше условиях if, по сути является проверкой типа того, установил ли я значение в том же элементе на true раньше. - person Sergey Kalinichenko; 03.03.2013
comment
Спасибо, это действительно помогло! - person Ishmael; 03.03.2013