00001
00005 package edu.mit.csail.sdg.squander.examples.chess;
00006
00007 import java.util.Arrays;
00008 import java.util.HashSet;
00009 import java.util.Set;
00010
00011 import edu.mit.csail.sdg.squander.examples.chess.ChessBoard.Cell;
00012
00018 public class ChessBoardMan {
00019
00020
00021
00022
00023
00024 public static int[] dx = new int[] {2, 1, -1, -2, -2, -1, 1, 2};
00025 public static int[] dy = new int[] {1, 2, 2, 1, -1, -2, -2, -1};
00026
00027 private static long t1, t2;
00028
00032 public static Cell[] knightsTourMan(int n, int m) {
00033 int[][] pot = new int[n][m];
00034 int si = 0;
00035 int sj = 2;
00036 pot[si][sj] = 1;
00037 t1 = System.currentTimeMillis();
00038 search(pot, n, m , si, sj, 2);
00039 System.out.println("not found");
00040 t2 = System.currentTimeMillis();
00041 System.out.println("time: " + (t2 - t1)/1000.0);
00042 return null;
00043 }
00044
00045
00046 private static void search(int[][] pot, int n, int m, int currI, int currJ, int cnt) {
00047 for (int k = 0; k < 8; k++) {
00048 int nextI = currI + dx[k];
00049 int nextJ = currJ + dy[k];
00050 if (nextI < 0 || nextI >= n) continue;
00051 if (nextJ < 0 || nextJ >= m) continue;
00052 if (pot[nextI][nextJ] != 0) continue;
00053 pot[nextI][nextJ] = cnt;
00054 if (cnt == n*m) {
00055 t2 = System.currentTimeMillis();
00056 System.out.println("found!");
00057 print(pot);
00058 System.out.println("time: " + (t2 - t1)/1000.0);
00059 System.exit(32);
00060 } else {
00061 search(pot, n, m, nextI, nextJ, cnt+1);
00062 }
00063 pot[nextI][nextJ] = 0;
00064 }
00065 }
00066
00067 private static void print(int[][] pot) {
00068 for (int i = 0; i < pot.length; i++)
00069 System.out.println(Arrays.toString(pot[i]));
00070 System.out.println();
00071 }
00072
00073 public static void main(String[] args) {
00074 knightsTourMan(6, 7);
00075 }
00076
00077
00078
00079
00080
00084 public static Set<Cell> nqueens(int n) {
00085 int[] colAssignments = new int[n];
00086 boolean[] rowTaken = new boolean[n];
00087 boolean[] d45Taken = new boolean[2*n - 1];
00088 boolean[] d135Taken = new boolean[2*n - 1];
00089 boolean b = solveNQueens(n, 0, colAssignments, rowTaken, d45Taken, d135Taken);
00090 if (!b)
00091 return null;
00092 Set<Cell> result = new HashSet<Cell>();
00093 for (int col = 0; col < n; col++) {
00094 result.add(new Cell(colAssignments[col], col));
00095 }
00096 return result;
00097 }
00098
00099 private static boolean solveNQueens(int n, int col, int[] colAssignments, boolean[] rowTaken,
00100 boolean[] d45Taken, boolean[] d135Taken) {
00101 if (col >= n)
00102 return true;
00103 for (int row = 0; row < n; row++) {
00104 if (rowTaken[row]) continue;
00105 if (d45Taken[row + col]) continue;
00106 if (d135Taken[col - row + n - 1]) continue;
00107 colAssignments[col] = row;
00108 rowTaken[row] = true;
00109 d45Taken[row + col] = true;
00110 d135Taken[col - row + n - 1] = true;
00111 if (solveNQueens(n, col + 1, colAssignments, rowTaken, d45Taken, d135Taken))
00112 return true;
00113 rowTaken[row] = false;
00114 d45Taken[row + col] = false;
00115 d135Taken[col - row + n - 1] = false;
00116 }
00117 return false;
00118 }
00119
00120 }