Проверка конфликта головоломки 8 королев
Я недавно прочитал о проблеме 8 королев и попытался решить ее самостоятельно, в C ++. Я создал класс с именем eq.h, файл реализации с именем eq.cpp и main.cpp.
В чем я не уверен, так это как проверить строки, столбцы и диагональные конфликты? Я думаю о том, чтобы использовать для проверки конфликтов вложенный цикл for. Как это можно применить? Я создал функцию valid () для этой цели. Ниже то, что у меня так далеко.
1) экв.ч
#ifndef 8QUEEN_H
#define 8QUEEN_H
#include <iostream>
#include <algorithm>
using namespace std;
class 8queen
{
public:
8queen();
~8queen();
int solve();//solve problem using next_permutation
void display();
private:
bool valid();
int queens[8]; //array to store 8 integers that represent 8 queens
};
#endif
2) eq.cpp
#include "eq.h"#include <iostream>
#include <algorithm>
using namespace std;
8queen::8queen()
{
for(int i=0;i<0;i++)
{
queens[i]=i;
}
}
8queen::~8queen()
{
}
//using next_perm, return all possible positions of the queens
int 8queen::solve()
{
int count=0;
do{
if(valid())
{
count++;
display();
}
}
while(next_permutation(queens,queens+8));
return count;
}
//display the positions of the queens
void 8queen::display()
{
for(int i=0; i<0;i++)
{
cout<<queens[i]<<' ';
cout<<endl;
}
}
//check if position is valid or not
bool 8queen::valid()
{
return true;
}
3) main.cpp
#include "eq.h"#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
8queen object;cout<<object.solve()<<endl;
}
Решение
Хорошо
Предположим, у вас есть шахматная сетка.
Для горизонтальных и вертикальных конфликтов вы можете использовать set этот магазин i а также j (строка и столбец) положения королевы. Если другая королева имеет то же самое i или же j конфликт.
Основной:
SET
row_set contains? (i) - conflict
column_set contains? (j) - conflict
Диагональные конфликты (от левого угла к правому углу)
Более сложный случай.
Предположим, что у вас есть королева на (1,1) и хочу поставить новую королеву на (8,8)
Таким образом, эта ситуация может быть конфликтной. Конечно.
Бывает, если значение разницы (j - i) подобные.
Предположим, что у вас есть королева на (1,7) и хочу поставить королеву (2,8)
Опять же значение разницы (j - i) здесь тоже самое
Диагональные конфликты (от правого угла к левому углу)
Предположим, что у вас есть королева на (8,1) и хочу поставить новую королеву на (1,8)
Конфликт.
Бывает если сумма сумма (j + i) подобные.
Предположим, что у вас есть королева на (1,2) и хочу поставить новую королеву на (2,1)
Конфликт!
Это происходит потому, что значение суммы одинаково (j + i)
Основной:
SET
left_to_right_set contains? (j - i) — конфликт
right_to_left_set contains? (j + i) — конфликт
Я надеюсь, что это поможет вам
Другие решения
Вместо этого рассмотрим следующий код. c[0][i] содержит количество королев в одном ряду, c[1][i] содержит количество королев в одном столбце, d[0][i] содержит число ферзей для обратной диагонали, d[1][i] содержит # королев для главных диагоналей. Отредактируйте его так, чтобы он обрабатывал сетку 8×8 вместо сетки 4×4.
int c[2][4] = {}, d[2][7] = {};
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
char x;
cin >> x;
if (x != 'x') continue;
++c[0][i], ++c[1][j];
++d[0][i + j], ++d[1][i + (3 - j)];
}
}
for (int i = 0; i < 4; ++i)
if (c[0][i] > 1 || c[1][i] > 1)
return true;
for (int i = 0; i < 7; ++i)
if (d[0][i] > 1 || d[1][i] > 1)
return true;
return false;