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

Question

В основном это проблема 8 Queens, но решающая ее с грубой силой в массиве 1D. Скажем, у меня есть массив (с именем б) размером 8, с элементами в диапазоне от 0 до 7.

Я инициализации каждого индекса в массиве с 8 по-петлями, например:

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 Queens с использованием грубой силы. Отсюда я понимаю, что это условия:

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

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

Здесь элементы Ь [3], В [4] и б [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]

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

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

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

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

также неприемлемы. У меня также не может быть 2 или более одинаковых чисел.

Проблема, с которой я столкнулась, заключается в создании функции проверки. Мне сказали, что мне нужно использовать 1 для цикла и 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+ решения), это не так мало, как мне сказали, это должно быть.

Answer 1

Я думаю, что есть небольшая проблема с вашей проверкой столкновений в диагоналях: у вас есть 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;