网站建设包含,建设网站虚拟主机是啥意思,有什么比较好的做简历的网站,网站建设优化服务资讯N 个皇后
问题描述
将n个皇后放在n大小的棋盘上#xff0c;没有两个皇后可以互相攻击。 最常见的 n 个皇后谜题是八个皇后谜题#xff0c;n 8#xff1a; 约束#xff1a;
使用 n 列和 n 行的棋盘。在棋盘上放置n个皇后。没有两个女王可以互相攻击。女王可以攻击同一水…N 个皇后
问题描述
将n个皇后放在n大小的棋盘上没有两个皇后可以互相攻击。 最常见的 n 个皇后谜题是八个皇后谜题n 8 约束
使用 n 列和 n 行的棋盘。在棋盘上放置n个皇后。没有两个女王可以互相攻击。女王可以攻击同一水平线、垂直线或对角线上的任何其他女王。
求解结果time limit 5s 问题大小
n搜索空间4256810^71610^193210^486410^11525610^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 {ValueRangeProviderProblemFactCollectionPropertyprivate ListColumn columnList;ValueRangeProviderProblemFactCollectionPropertyprivate ListRow rowList;PlanningEntityCollectionPropertyprivate ListQueen queenList;PlanningScoreprivate HardSoftScore score;
}
例如
QueenColumnRowAscendingDiagonalIndexDescendingDiagonalIndexA1011 (**)-1B010 (*)1 (**)1C22240D030 (*)33
(*)(**)的皇后可以互相攻击
求解器约束提供者
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) {SolverFactoryNQueen solverFactory SolverFactory.create(new SolverConfig().withSolutionClass(NQueen.class).withEntityClasses(Queen.class).withConstraintProviderClass(NQueenConstraintProvider.class).withTerminationSpentLimit(Duration.ofSeconds(5)));NQueen problem generateDemoData();SolverNQueen solver solverFactory.buildSolver();NQueen solution solver.solve(problem);printTimetable(solution);}public static NQueen generateDemoData() {ListColumn columnList new ArrayList();ListRow rowList new ArrayList();ListQueen 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();ListColumn columnList nQueen.getColumnList();ListRow rowList nQueen.getRowList();ListQueen queenList nQueen.getQueenList();MapColumn, MapRow, ListQueen 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) {ListListQueen cellList rowList.stream().map(row - {MapRow, ListQueen byRowMap queenMap.get(column);if (byRowMap null) {return Collections.QueenemptyList();}ListQueen cellQueenList byRowMap.get(row);if (cellQueenList null) {return Collections.QueenemptyList();}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));}ListQueen 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());}}}
}
