r++
BAN USERI like to hack.
I just cranked this out this morning after tinkering with the backtracking algorithm to better understand recursive enumeration. I hope this helps someone, I didn't see a similar solution here so I thought I would post. I understand "backtracking" as a metaheuristic containing 6 "black box" procedures: root, first, next, reject, accept and output (see wikipedia entry for backtracking.)
Can someone help me with theoretical running time? I think it is something like O(n^2*n*log(n)). n^2 for the "queenTakes()" and n*log(n) for the "bt" although I think it is better than that given the potential search tree (n^n see my "first" and "next" methods) is heavily pruned at the root.. Any help is appreciated. I have an interview with FB in two weeks.
package algorist;
import java.util.Collection;
import java.util.Vector;
import org.junit.Test;
public class BacktrackingAlgo {
private static int N = 20;
private static Vector<Integer> v() { return new Vector<Integer>(); } // new vector compact
private static Vector<Integer> v(Collection<Integer> u) { return new Vector<Integer>(u); } // new vector compact
private static <T> int lst(Vector<T> v) { return v.size()-1; } // last element index
public Vector<Integer> root(int P) { return v(); }
public Vector<Integer> first(Vector<Integer> candidate) {
Vector<Integer> v = v(candidate);
v.add(0);
return v;
}
public Vector<Integer> next(int N, Vector<Integer> candidate) {
Vector<Integer> v = v(candidate);
int i = lst(v);
int next = candidate.get(i) + 1;
if (next == N) return null;
v.set(i, next);
return v;
}
public boolean reject(int N, Vector<Integer> c) {
if (c.size() > N) return true;
if (c.size() < 2) return false;
for (int i = 0; i < c.size(); i++) {
for (int j = 0; j < c.size(); j++) {
if (i == j) continue; // same position
if (queenTakes(c, i, j)) return true;
}
}
return false;
}
public boolean queenTakes(Vector<Integer> c, int j, int i) {
int[] q1 = new int[] {j, c.get(j)};
int[] q2 = new int[] {i, c.get(i)};
// queen takes like a rook
if (q1[0] == q2[0] || q1[1] == q2[1]) return true;
// queen takes like a bishop
if (Math.abs(q1[0] - q2[0]) == Math.abs(q1[1]-q2[1])) return true;
// queen takes like a knight, remembering condition where q2 shares col/row eliminated above
if (Math.abs(q1[0]-q2[0])+Math.abs(q1[1]-q2[1]) == 3) return true;
return false;
}
public boolean accept(int N, Vector<Integer> c) {
if (c.size() == N) return true;
return false;
}
private int numSolutions = 0;
public void output(Vector<Integer> c) {
numSolutions += 1;
// System.out.println(c);
}
public void bt(Vector<Integer> c) {
if (reject(N, c)) return;
if (accept(N, c)) {
output(c);
return;
}
// else
Vector<Integer> s = first(c);
while (s != null) {
bt(s);
s = next(N, s);
}
}
@Test
public void testBt() {
bt(root(N));
}
}
Yes, that is N=20! And it is still running on my lame-o laptop. I'll post the finish time later.
- r++ April 18, 2015
Eclipse/java crapped out, I will likely have to tweak the heap space settings on my dev environment. I may run it and printout a running total and time before it craps out again, and determine if I should be using long or BigInteger. Might be good practice for code/algo optimization.
- r++ April 20, 2015