Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

this
.columns = columns;
}
@Override
public boolean 
satisfied(Map assignment) {
for 
(Entry item : assignment.entrySet()) {
// q1c = ферзь на 1-й вертикали, q1r = ферзь на 1-й горизонтали
int 
q1c = item.getKey();
int 
q1r = item.getValue();
// q2c = ферзь на 2-й вертикали
for 
(
int 
q2c = q1c + 1; q2c <= columns.size(); q2c++) {
if 
(assignment.containsKey(q2c)) {
// q2r = ферзь на 2-й горизонтали
int 
q2r = assignment.get(q2c);
// тот же ряд?
if 
(q1r == q2r) {
return false
;
}
// одна диагональ?
if 
(Math.
abs
(q1r — q2r) == Math.
abs
(q1c — q2c)) {
return false
;
}
}
}
}
return true
; // нет конфликтов
}
Осталось.только.добавить.ограничение.и.запустить.поиск..Теперь.вернемся.в.ко-
нец.метода.
main()
.(листинг.3.10).
Листинг 3.10. 
QueensConstraint.java (продолжение)
csp.addConstraint(
new 
QueensConstraint(columns));
Map solution = csp.backtrackingSearch();
if 
(solution == 
null
) {

---

96
Глава 3.
Задачи с ограничениями
System.
out
.println("No solution found!");
} 
else 
{
System.
out
.println(solution);
}
}
}
Обратите.внимание.на.то,.что.мы.довольно.легко.приспособили.схему.решения.
задач.с.ограничениями,.созданную.для.раскрашивания.карты,.к.совершенно.дру-
гому.типу.задач..В.этом.и.заключается.эффективность.написания.обобщенного.
кода!.Алгоритмы.должны.быть.реализованы.настолько.широко,.насколько.это.
возможно,.если.только.не.потребуется.специализация.для.оптимизации.произ-
водительности.конкретного.приложения.
Правильное.решение.присваивает.каждому.ферзю.вертикаль.и.горизонталь:
{1=1, 2=5, 3=8, 4=6, 5=3, 6=7, 7=2, 8=4}