Итак, я сейчас работаю над проектом по размещению N королев на доске NxN и предотвращению их атаки друг на друга. Этот проект предназначен для ознакомительного курса AI. Он имеет несколько определенных c критериев для получения полных баллов, а именно: поиск до 3 решений для любого размера доски до N = 100 за 5 секунд или меньше. В настоящее время я пытаюсь сделать эту проблему удовлетворением ограничения, выбрав наиболее ограниченную строку, которая, если я правильно ее понимаю, не позволит получить строки, которые ближе к полностью атакованным.
Изначально пользователь вводит столбец число и королева будут размещены в этом столбце в первом ряду доски. Оттуда доска атаки будет обновляться с использованием этой комбинации столбцов строк, увеличивая значение всех диагоналей, а строка и столбец - небольшой пример первого и последнего ниже
void main()
{
int size, row, col;
row = 1;
cout << "Enter the board size: ";
cin >> size;
cout << "Enter column of first queen: ";
cin >> col;
cols[row] = col; // cols store the column value of each queen in that particular row.
updateAttack(row, col, +1, size);
findNextQueen(size);
// return here if we found all the solution
//cout << solutionCount << " solutions found. see NQueen.out.\n";
cout << solutionCount << " solutions found. see NQueen.out.\n";
fout.close();
system("pause");
}
void updateAttack(int r, int c, int change, int size) // Updates the attack board given the location a queen being placed
{
int r1, c1;
// update diagnals
for (r1 = r - 1, c1 = c - 1; r1 >= 1 && c1 >= 1; r1--, c1--)
attack[r1][c1] += change;
for (r1 = r + 1, c1 = c + 1; r1 <= size && c1 <= size; r1++, c1++)
attack[r1][c1] += change;
for (r1 = r - 1, c1 = c + 1; r1 >= 1 && c1 <= size; r1--, c1++)
attack[r1][c1] += change;
for (r1 = r + 1, c1 = c - 1; r1 <= size && c1 >= 1; r1++, c1--)
attack[r1][c1] += change;
// update columns
for (r1 = 1, c1 = c; r1 <= size; r1++) // k goes to each row
attack[r1][c1] += change;
}
Основная проблема с помощью этой программы выбирает, в какую строку помещать ферзь. В простом методе обратного отслеживания с рекурсивными вызовами ферзи вы увеличиваете количество строк вниз и помещаете ферзь в первое место в той строке, которая в данный момент не подвергается атаке, а затем делать то же самое для следующей строки и следующей королевы, пока королева не может быть размещена, и в этом случае вы возвращаетесь назад и пытаетесь исправить предыдущую королеву, перемещая ее в следующее место. Пример того, как это делается с обратным отслеживанием и отсутствием CSP, реализованным ниже.
void findNextQueen(int r, int size)
{
for (int c=1;c<=size;c++)
{
if (attack[r][c]==0) // not under attack
{
cols[r]=c; // assign another queen
if (r<size)
{
updateAttack(r,c,+1, size);
findNextQueen(r+1, size);
updateAttack(r,c, -1, size);
}
else
{
print1solution(size);
if (solutionCount >= 3)
{
cout << solutionCount << " solutions found. see NQueen.out.\n";
system("pause");
exit(0);
}
}
}
}
return;
}
Удовлетворение ограничения пытается решить проблему, возникшую во время этого обратного отслеживания, когда позже вы можете полностью заполнить строки ниже значениями атаки, которые приведут к потребуется много возвратов, что увеличит время, которое занимает много времени. Он делает это, пытаясь выбрать строки, в которых сначала выполняется больше пробелов, чтобы предотвратить их потерю и требовать позднего возврата. Мой пример того, что вызывает проблемы, в настоящее время кажется, что всегда можно найти 0 возможных решений ниже.
void findNextQueen(int size)
{
int bestRowCount = 0;
int bestRow = 2;
for (int r = 2; r <= size; r++) // Meant to find the most constrained row and use that as my r value for attack array
{
int aRowCount = 0; // Count of attacks in current row
for (int c = 1; c <= size; c++)
{
if (attack[r][c] >= 1)
{
aRowCount++;
}
}
if ((aRowCount > bestRowCount) && (aRowCount != size))
{
bestRowCount = aRowCount;
bestRow = r;
}
}
for (int c = 1; c <= size; c++)
{
if (attack[bestRow][c] == 0) // not under attack
{
cols[bestRow] = c; // assign another queen
if (queensLeft(size) == 1) // returns true if there are rows that still lack a queen
{
updateAttack(bestRow, c, +1, size);
findNextQueen(size);
cols[bestRow] = 0;
updateAttack(bestRow, c, -1, size);
}
else
{
print1solution(size);
if (solutionCount >= 3)
{
cout << solutionCount << " solutions found. see NQueen.out.\n";
system("pause");
exit(0);
}
}
}
}
return;
}