Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Optimizing N queens puzzle
- public class Queen {
- int column;
- int row;
- int d1;
- int d2;
- public Queen(int column, int row, int d1, int d2) {
- super();
- this.column = column;
- this.row = row;
- this.d1 = d1;
- this.d2 = d2;
- }
- @Override
- public String toString() {
- return "Queen [column=" + column + ", row=" + row + ", d1=" + d1
- + ", d2=" + d2 + "]";
- }
- @Override
- public boolean equals(Object obj) {
- return ((Queen)obj).column == this.column && ((Queen)obj).row == this.row;
- }
- }
- import java.util.HashSet;
- import java.util.Random;
- public class SolveQueens {
- public static boolean printBoard = false;
- public static int N = 100;
- public static int maxSteps = 2000000;
- public static int[] queens = new int[N];
- public static Random random = new Random();
- public static HashSet<Queen> q = new HashSet<Queen>();
- public static HashSet rowConfl[] = new HashSet[N];
- public static HashSet d1Confl[] = new HashSet[2*N - 1];
- public static HashSet d2Confl[] = new HashSet[2*N - 1];
- public static void init () {
- int r;
- rowConfl = new HashSet[N];
- d1Confl = new HashSet[2*N - 1];
- d2Confl = new HashSet[2*N - 1];
- for (int i = 0; i < N; i++) {
- r = random.nextInt(N);
- queens[i] = r;
- Queen k = new Queen(i, r, i + r, N - 1 + i - r);
- q.add(k);
- if (rowConfl[k.row] == null) {
- rowConfl[k.row] = new HashSet<Queen>();
- }
- if (d1Confl[k.d1] == null) {
- d1Confl[k.d1] = new HashSet<Queen>();
- }
- if (d2Confl[k.d2] == null) {
- d2Confl[k.d2] = new HashSet<Queen>();
- }
- ((HashSet<Queen>)rowConfl[k.row]).add(k);
- ((HashSet<Queen>)d1Confl[k.d1]).add(k);
- ((HashSet<Queen>)d2Confl[k.d2]).add(k);
- }
- }
- public static void print () {
- for (int i = 0; i < N; i++) {
- for (int j = 0; j < N; j++) {
- System.out.print(queens[i] == j ? "♕ " : "◻◻◻ ");
- }
- System.out.println();
- }
- System.out.println();
- }
- public static boolean checkItLinear() {
- Queen r = choseConflictQueen();
- if (r == null) {
- return true;
- }
- Queen newQ = findNewBestPosition(r);
- q.remove(r);
- q.add(newQ);
- rowConfl[r.row].remove(r);
- d1Confl[r.d1].remove(r);
- d2Confl[r.d2].remove(r);
- if (rowConfl[newQ.row] == null) {
- rowConfl[newQ.row] = new HashSet<Queen>();
- }
- if (d1Confl[newQ.d1] == null) {
- d1Confl[newQ.d1] = new HashSet<Queen>();
- }
- if (d2Confl[newQ.d2] == null) {
- d2Confl[newQ.d2] = new HashSet<Queen>();
- }
- ((HashSet<Queen>)rowConfl[newQ.row]).add(newQ);
- ((HashSet<Queen>)d1Confl[newQ.d1]).add(newQ);
- ((HashSet<Queen>)d2Confl[newQ.d2]).add(newQ);
- queens[r.column] = newQ.row;
- return false;
- }
- public static Queen choseConflictQueen () {
- HashSet<Queen> conflictSet = new HashSet<Queen>();
- boolean hasConflicts = false;
- for (int i = 0; i < 2*N - 1; i++) {
- if (i < N && rowConfl[i] != null) {
- hasConflicts = hasConflicts || rowConfl[i].size() > 1;
- conflictSet.addAll(rowConfl[i]);
- }
- if (d1Confl[i] != null) {
- hasConflicts = hasConflicts || d1Confl[i].size() > 1;
- conflictSet.addAll(d1Confl[i]);
- }
- if (d2Confl[i] != null) {
- hasConflicts = hasConflicts || d2Confl[i].size() > 1;
- conflictSet.addAll(d2Confl[i]);
- }
- }
- if (hasConflicts) {
- int c = random.nextInt(conflictSet.size());
- return (Queen) conflictSet.toArray()[c];
- }
- return null;
- }
- public static Queen findNewBestPosition(Queen old) {
- int[] row = new int[N];
- int min = Integer.MAX_VALUE;
- int minInd = old.row;
- for (int i = 0; i < N; i++) {
- if (rowConfl[i] != null) {
- row[i] = rowConfl[i].size();
- }
- if (d1Confl[old.column + i] != null) {
- row[i] += d1Confl[old.column + i].size();
- }
- if (d2Confl[N - 1 + old.column - i] != null) {
- row[i] += d2Confl[N - 1 + old.column - i].size();
- }
- if (i == old.row) {
- row[i] = row[i] - 3;
- }
- if (row[i] <= min && i != minInd) {
- min = row[i];
- minInd = i;
- }
- }
- return new Queen(old.column, minInd, old.column + minInd, N - 1 + old.column - minInd);
- }
- public static void main(String[] args) {
- long startTime = System.currentTimeMillis();
- init();
- int steps = 0;
- while(!checkItLinear()) {
- if (++steps > maxSteps) {
- init();
- steps = 0;
- }
- }
- long endTime = System.currentTimeMillis();
- System.out.println("Done for " + (endTime - startTime) + "msn");
- if(printBoard){
- print();
- }
- }
- }
- import java.util.Random;
- import java.util.Vector;
- public class SolveQueens {
- public static boolean PRINT_BOARD = true;
- public static int N = 10;
- public static int MAX_STEPS = 5000;
- public static int[] queens = new int[N];
- public static Random random = new Random();
- public static int[] rowConfl = new int[N];
- public static int[] d1Confl = new int[2*N - 1];
- public static int[] d2Confl = new int[2*N - 1];
- public static Vector<Integer> conflicts = new Vector<Integer>();
- public static void init () {
- random = new Random();
- for (int i = 0; i < N; i++) {
- queens[i] = i;
- }
- }
- public static int getD1Pos (int col, int row) {
- return col + row;
- }
- public static int getD2Pos (int col, int row) {
- return N - 1 + col - row;
- }
- public static void print () {
- for (int i = 0; i < N; i++) {
- for (int j = 0; j < N; j++) {
- System.out.print(queens[i] == j ? "Q " : "* ");
- }
- System.out.println();
- }
- System.out.println();
- }
- public static boolean hasConflicts() {
- generateConflicts();
- if (conflicts.isEmpty()) {
- return false;
- }
- int r = random.nextInt(conflicts.size());
- int conflQueenCol = conflicts.get(r);
- int currentRow = queens[conflQueenCol];
- int bestRow = currentRow;
- int minConfl = getConflicts(conflQueenCol, queens[conflQueenCol]) - 3;
- int tempConflCount;
- for (int i = 0; i < N ; i++) {
- tempConflCount = getConflicts(conflQueenCol, i);
- if (i != currentRow && tempConflCount <= minConfl) {
- minConfl = tempConflCount;
- bestRow = i;
- }
- }
- queens[conflQueenCol] = bestRow;
- return true;
- }
- public static void generateConflicts () {
- conflicts = new Vector<Integer>();
- rowConfl = new int[N];
- d1Confl = new int[2*N - 1];
- d2Confl = new int[2*N - 1];
- for (int i = 0; i < N; i++) {
- int r = queens[i];
- rowConfl[r]++;
- d1Confl[getD1Pos(i, r)]++;
- d2Confl[getD2Pos(i, r)]++;
- }
- for (int i = 0; i < N; i++) {
- int conflictsCount = getConflicts(i, queens[i]) - 3;
- if (conflictsCount > 0) {
- conflicts.add(i);
- }
- }
- }
- public static int getConflicts(int col, int row) {
- return rowConfl[row] + d1Confl[getD1Pos(col, row)] + d2Confl[getD2Pos(col, row)];
- }
- public static void main(String[] args) {
- long startTime = System.currentTimeMillis();
- init();
- int steps = 0;
- while(hasConflicts()) {
- if (++steps > MAX_STEPS) {
- init();
- steps = 0;
- }
- }
- long endTime = System.currentTimeMillis();
- System.out.println("Done for " + (endTime - startTime) + "msn");
- if(PRINT_BOARD){
- print();
- }
- }
Add Comment
Please, Sign In to add comment