Guest User

Untitled

a guest
Aug 16th, 2018
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.47 KB | None | 0 0
  1. Optimizing N queens puzzle
  2. public class Queen {
  3.  
  4. int column;
  5. int row;
  6. int d1;
  7. int d2;
  8.  
  9. public Queen(int column, int row, int d1, int d2) {
  10. super();
  11. this.column = column;
  12. this.row = row;
  13. this.d1 = d1;
  14. this.d2 = d2;
  15. }
  16.  
  17. @Override
  18. public String toString() {
  19. return "Queen [column=" + column + ", row=" + row + ", d1=" + d1
  20. + ", d2=" + d2 + "]";
  21. }
  22.  
  23. @Override
  24. public boolean equals(Object obj) {
  25. return ((Queen)obj).column == this.column && ((Queen)obj).row == this.row;
  26. }
  27.  
  28. }
  29.  
  30. import java.util.HashSet;
  31. import java.util.Random;
  32.  
  33.  
  34. public class SolveQueens {
  35. public static boolean printBoard = false;
  36. public static int N = 100;
  37. public static int maxSteps = 2000000;
  38. public static int[] queens = new int[N];
  39. public static Random random = new Random();
  40.  
  41. public static HashSet<Queen> q = new HashSet<Queen>();
  42.  
  43. public static HashSet rowConfl[] = new HashSet[N];
  44. public static HashSet d1Confl[] = new HashSet[2*N - 1];
  45. public static HashSet d2Confl[] = new HashSet[2*N - 1];
  46.  
  47. public static void init () {
  48. int r;
  49. rowConfl = new HashSet[N];
  50. d1Confl = new HashSet[2*N - 1];
  51. d2Confl = new HashSet[2*N - 1];
  52. for (int i = 0; i < N; i++) {
  53. r = random.nextInt(N);
  54. queens[i] = r;
  55. Queen k = new Queen(i, r, i + r, N - 1 + i - r);
  56. q.add(k);
  57. if (rowConfl[k.row] == null) {
  58. rowConfl[k.row] = new HashSet<Queen>();
  59. }
  60. if (d1Confl[k.d1] == null) {
  61. d1Confl[k.d1] = new HashSet<Queen>();
  62. }
  63. if (d2Confl[k.d2] == null) {
  64. d2Confl[k.d2] = new HashSet<Queen>();
  65. }
  66. ((HashSet<Queen>)rowConfl[k.row]).add(k);
  67. ((HashSet<Queen>)d1Confl[k.d1]).add(k);
  68. ((HashSet<Queen>)d2Confl[k.d2]).add(k);
  69. }
  70. }
  71.  
  72. public static void print () {
  73. for (int i = 0; i < N; i++) {
  74. for (int j = 0; j < N; j++) {
  75. System.out.print(queens[i] == j ? "♕ " : "◻◻◻ ");
  76. }
  77. System.out.println();
  78. }
  79. System.out.println();
  80. }
  81.  
  82.  
  83. public static boolean checkItLinear() {
  84.  
  85. Queen r = choseConflictQueen();
  86.  
  87. if (r == null) {
  88. return true;
  89. }
  90.  
  91. Queen newQ = findNewBestPosition(r);
  92.  
  93. q.remove(r);
  94. q.add(newQ);
  95. rowConfl[r.row].remove(r);
  96. d1Confl[r.d1].remove(r);
  97. d2Confl[r.d2].remove(r);
  98. if (rowConfl[newQ.row] == null) {
  99. rowConfl[newQ.row] = new HashSet<Queen>();
  100. }
  101. if (d1Confl[newQ.d1] == null) {
  102. d1Confl[newQ.d1] = new HashSet<Queen>();
  103. }
  104. if (d2Confl[newQ.d2] == null) {
  105. d2Confl[newQ.d2] = new HashSet<Queen>();
  106. }
  107. ((HashSet<Queen>)rowConfl[newQ.row]).add(newQ);
  108. ((HashSet<Queen>)d1Confl[newQ.d1]).add(newQ);
  109. ((HashSet<Queen>)d2Confl[newQ.d2]).add(newQ);
  110. queens[r.column] = newQ.row;
  111. return false;
  112. }
  113.  
  114. public static Queen choseConflictQueen () {
  115.  
  116. HashSet<Queen> conflictSet = new HashSet<Queen>();
  117. boolean hasConflicts = false;
  118.  
  119. for (int i = 0; i < 2*N - 1; i++) {
  120. if (i < N && rowConfl[i] != null) {
  121. hasConflicts = hasConflicts || rowConfl[i].size() > 1;
  122. conflictSet.addAll(rowConfl[i]);
  123. }
  124. if (d1Confl[i] != null) {
  125. hasConflicts = hasConflicts || d1Confl[i].size() > 1;
  126. conflictSet.addAll(d1Confl[i]);
  127. }
  128. if (d2Confl[i] != null) {
  129. hasConflicts = hasConflicts || d2Confl[i].size() > 1;
  130. conflictSet.addAll(d2Confl[i]);
  131. }
  132. }
  133. if (hasConflicts) {
  134. int c = random.nextInt(conflictSet.size());
  135. return (Queen) conflictSet.toArray()[c];
  136. }
  137.  
  138. return null;
  139. }
  140.  
  141. public static Queen findNewBestPosition(Queen old) {
  142. int[] row = new int[N];
  143. int min = Integer.MAX_VALUE;
  144. int minInd = old.row;
  145.  
  146. for (int i = 0; i < N; i++) {
  147. if (rowConfl[i] != null) {
  148. row[i] = rowConfl[i].size();
  149. }
  150. if (d1Confl[old.column + i] != null) {
  151. row[i] += d1Confl[old.column + i].size();
  152. }
  153. if (d2Confl[N - 1 + old.column - i] != null) {
  154. row[i] += d2Confl[N - 1 + old.column - i].size();
  155. }
  156. if (i == old.row) {
  157. row[i] = row[i] - 3;
  158. }
  159.  
  160. if (row[i] <= min && i != minInd) {
  161. min = row[i];
  162. minInd = i;
  163. }
  164. }
  165.  
  166. return new Queen(old.column, minInd, old.column + minInd, N - 1 + old.column - minInd);
  167. }
  168.  
  169. public static void main(String[] args) {
  170. long startTime = System.currentTimeMillis();
  171. init();
  172. int steps = 0;
  173. while(!checkItLinear()) {
  174. if (++steps > maxSteps) {
  175. init();
  176. steps = 0;
  177. }
  178. }
  179. long endTime = System.currentTimeMillis();
  180. System.out.println("Done for " + (endTime - startTime) + "msn");
  181.  
  182. if(printBoard){
  183. print();
  184. }
  185.  
  186.  
  187. }
  188. }
  189.  
  190. import java.util.Random;
  191. import java.util.Vector;
  192.  
  193.  
  194. public class SolveQueens {
  195. public static boolean PRINT_BOARD = true;
  196. public static int N = 10;
  197. public static int MAX_STEPS = 5000;
  198.  
  199. public static int[] queens = new int[N];
  200. public static Random random = new Random();
  201.  
  202.  
  203. public static int[] rowConfl = new int[N];
  204. public static int[] d1Confl = new int[2*N - 1];
  205. public static int[] d2Confl = new int[2*N - 1];
  206.  
  207. public static Vector<Integer> conflicts = new Vector<Integer>();
  208.  
  209. public static void init () {
  210. random = new Random();
  211. for (int i = 0; i < N; i++) {
  212. queens[i] = i;
  213. }
  214. }
  215.  
  216. public static int getD1Pos (int col, int row) {
  217. return col + row;
  218. }
  219.  
  220. public static int getD2Pos (int col, int row) {
  221. return N - 1 + col - row;
  222. }
  223.  
  224. public static void print () {
  225. for (int i = 0; i < N; i++) {
  226. for (int j = 0; j < N; j++) {
  227. System.out.print(queens[i] == j ? "Q " : "* ");
  228. }
  229. System.out.println();
  230. }
  231. System.out.println();
  232. }
  233.  
  234.  
  235. public static boolean hasConflicts() {
  236.  
  237. generateConflicts();
  238.  
  239. if (conflicts.isEmpty()) {
  240. return false;
  241. }
  242.  
  243. int r = random.nextInt(conflicts.size());
  244. int conflQueenCol = conflicts.get(r);
  245. int currentRow = queens[conflQueenCol];
  246. int bestRow = currentRow;
  247. int minConfl = getConflicts(conflQueenCol, queens[conflQueenCol]) - 3;
  248. int tempConflCount;
  249.  
  250. for (int i = 0; i < N ; i++) {
  251. tempConflCount = getConflicts(conflQueenCol, i);
  252. if (i != currentRow && tempConflCount <= minConfl) {
  253. minConfl = tempConflCount;
  254. bestRow = i;
  255. }
  256. }
  257. queens[conflQueenCol] = bestRow;
  258. return true;
  259. }
  260.  
  261. public static void generateConflicts () {
  262.  
  263. conflicts = new Vector<Integer>();
  264.  
  265. rowConfl = new int[N];
  266. d1Confl = new int[2*N - 1];
  267. d2Confl = new int[2*N - 1];
  268.  
  269. for (int i = 0; i < N; i++) {
  270. int r = queens[i];
  271. rowConfl[r]++;
  272. d1Confl[getD1Pos(i, r)]++;
  273. d2Confl[getD2Pos(i, r)]++;
  274. }
  275.  
  276. for (int i = 0; i < N; i++) {
  277. int conflictsCount = getConflicts(i, queens[i]) - 3;
  278. if (conflictsCount > 0) {
  279. conflicts.add(i);
  280. }
  281. }
  282. }
  283.  
  284. public static int getConflicts(int col, int row) {
  285. return rowConfl[row] + d1Confl[getD1Pos(col, row)] + d2Confl[getD2Pos(col, row)];
  286. }
  287.  
  288.  
  289.  
  290. public static void main(String[] args) {
  291. long startTime = System.currentTimeMillis();
  292. init();
  293. int steps = 0;
  294. while(hasConflicts()) {
  295. if (++steps > MAX_STEPS) {
  296. init();
  297. steps = 0;
  298. }
  299. }
  300. long endTime = System.currentTimeMillis();
  301. System.out.println("Done for " + (endTime - startTime) + "msn");
  302.  
  303. if(PRINT_BOARD){
  304. print();
  305. }
  306. }
Add Comment
Please, Sign In to add comment