По сути, это проблема 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 для цикла и 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+ решений), оно не так мало, как мне говорят, должно быть.
Я думаю, что есть небольшая проблема с вашей проверкой столкновений в диагоналях: у вас есть 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;
Других решений пока нет …