N 個皇后

問題描述

將n個皇后放在n大小的棋盤上，沒有兩個皇后可以互相攻擊。 最常見的 n 個皇后謎題是八個皇后謎題，n = 8：

約束：

• 使用 n 列和 n 行的棋盤。
• 在棋盤上放置n個皇后。
• 沒有兩個女王可以互相攻擊。女王可以攻擊同一水平線、垂直線或對角線上的任何其他女王。

求解結果（time limit 5s）

問題大小

n	搜索空間
4	256
8	10^7
16	10^19
32	10^48
64	10^115
256	10^616

域模型

@Data
@AllArgsConstructor
public class Column {private int index;
}
@Data
@AllArgsConstructor
public class Row {private int index;
}
@Data
@AllArgsConstructor
@NoArgsConstructor
@PlanningEntity
public class Queen {@PlanningIdprivate Integer id;@PlanningVariableprivate Column column;@PlanningVariableprivate Row row;// 升序對角線索引（左上到右下）public int getAscendingDiagonalIndex() {return column.getIndex() + row.getIndex();}// 降序對角線索引（左下到右上）public int getDescendingDiagonalIndex() {return column.getIndex() - row.getIndex();}
}
@Data
@AllArgsConstructor
@NoArgsConstructor
@PlanningSolution
public class NQueen {@ValueRangeProvider@ProblemFactCollectionPropertyprivate List<Column> columnList;@ValueRangeProvider@ProblemFactCollectionPropertyprivate List<Row> rowList;@PlanningEntityCollectionPropertyprivate List<Queen> queenList;@PlanningScoreprivate HardSoftScore score;
}

例如：

Queen	Column	Row	AscendingDiagonalIndex	DescendingDiagonalIndex
A1	0	1	1 (**)	-1
B0	1	0 (*)	1 (**)	1
C2	2	2	4	0
D0	3	0 (*)	3	3

(*)(**)的皇后可以互相攻擊

求解器（約束提供者）

public class NQueenConstraintProvider implements ConstraintProvider {@Overridepublic Constraint[] defineConstraints(ConstraintFactory constraintFactory) {return new Constraint[]{// 列沖突columnConflict(constraintFactory),// 行沖突rowConflict(constraintFactory),// 升序對角線沖突ascendingDiagonalIndexConflict(constraintFactory),// 降序對角線沖突descendingDiagonalIndexConflict(constraintFactory),};}public Constraint columnConflict(ConstraintFactory constraintFactory) {return constraintFactory.forEach(Queen.class).join(Queen.class,Joiners.equal(Queen::getColumn),Joiners.lessThan(Queen::getId)).penalize(HardSoftScore.ONE_HARD).asConstraint("Column conflict");}public Constraint rowConflict(ConstraintFactory constraintFactory) {return constraintFactory.forEach(Queen.class).join(Queen.class,Joiners.equal(Queen::getRow),Joiners.lessThan(Queen::getId)).penalize(HardSoftScore.ONE_HARD).asConstraint("Row conflict");}public Constraint ascendingDiagonalIndexConflict(ConstraintFactory constraintFactory) {return constraintFactory.forEach(Queen.class).join(Queen.class,Joiners.equal(Queen::getAscendingDiagonalIndex),Joiners.lessThan(Queen::getId)).penalize(HardSoftScore.ONE_HARD).asConstraint("AscendingDiagonalIndex conflict");}public Constraint descendingDiagonalIndexConflict(ConstraintFactory constraintFactory) {return constraintFactory.forEach(Queen.class).join(Queen.class,Joiners.equal(Queen::getDescendingDiagonalIndex),Joiners.lessThan(Queen::getId)).penalize(HardSoftScore.ONE_HARD).asConstraint("DescendingDiagonalIndex conflict");}
}

應用

public class NQueenApp {public static void main(String[] args) {SolverFactory<NQueen> solverFactory = SolverFactory.create(new SolverConfig().withSolutionClass(NQueen.class).withEntityClasses(Queen.class).withConstraintProviderClass(NQueenConstraintProvider.class).withTerminationSpentLimit(Duration.ofSeconds(5)));NQueen problem = generateDemoData();Solver<NQueen> solver = solverFactory.buildSolver();NQueen solution = solver.solve(problem);printTimetable(solution);}public static NQueen generateDemoData() {List<Column> columnList = new ArrayList<>();List<Row> rowList = new ArrayList<>();List<Queen> queenList = new ArrayList<>();for (int i = 0; i < 8; i++) {columnList.add(new Column(i));rowList.add(new Row(i));queenList.add(new Queen(i, null, null));}return new NQueen(columnList, rowList, queenList, null);}private static void printTimetable(NQueen nQueen) {System.out.println("");List<Column> columnList = nQueen.getColumnList();List<Row> rowList = nQueen.getRowList();List<Queen> queenList = nQueen.getQueenList();Map<Column, Map<Row, List<Queen>>> queenMap = queenList.stream().filter(queen -> queen.getColumn() != null && queen.getRow() != null).collect(Collectors.groupingBy(Queen::getColumn, Collectors.groupingBy(Queen::getRow)));System.out.println("|     | " + columnList.stream().map(room -> String.format("%-3s", room.getIndex())).collect(Collectors.joining(" | ")) + " |");System.out.println("|" + "-----|".repeat(columnList.size() + 1));for (Column column : columnList) {List<List<Queen>> cellList = rowList.stream().map(row -> {Map<Row, List<Queen>> byRowMap = queenMap.get(column);if (byRowMap == null) {return Collections.<Queen>emptyList();}List<Queen> cellQueenList = byRowMap.get(row);if (cellQueenList == null) {return Collections.<Queen>emptyList();}return cellQueenList;}).collect(Collectors.toList());System.out.println("| " + String.format("%-3s", column.getIndex()) + " | "+ cellList.stream().map(cellQueenList -> String.format("%-3s",cellQueenList.stream().map(queen -> queen.getId().toString()).collect(Collectors.joining(", ")))).collect(Collectors.joining(" | "))+ " |");System.out.println("|" + "-----|".repeat(columnList.size() + 1));}List<Queen> unassignedQueens = queenList.stream().filter(Queen -> Queen.getColumn() == null || Queen.getRow() == null).collect(Collectors.toList());if (!unassignedQueens.isEmpty()) {System.out.println("");System.out.println("Unassigned Queens");for (Queen Queen : unassignedQueens) {System.out.println("  " + Queen.getColumn() + " - " + Queen.getRow());}}}
}