66 lines
1.1 KiB
Dart
66 lines
1.1 KiB
Dart
/**
|
|
Return true if queen placement q[n] does not conflict with
|
|
other queens q[0] through q[n-1]
|
|
*/
|
|
isConsistent(List q, int n) {
|
|
for (int i=0; i<n; i++) {
|
|
if (q[i] == q[n]) {
|
|
return false; // Same column
|
|
}
|
|
|
|
if ((q[i] - q[n]) == (n - i)) {
|
|
return false; // Same major diagonal
|
|
}
|
|
|
|
if ((q[n] - q[i]) == (n - i)) {
|
|
return false; // Same minor diagonal
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
/**
|
|
Print out N-by-N placement of queens from permutation q in ASCII.
|
|
*/
|
|
printQueens(List q) {
|
|
int N = q.length;
|
|
for (int i=0; i<N; i++) {
|
|
StringBuffer sb = new StringBuffer();
|
|
for (int j=0; j<N; j++) {
|
|
if (q[i] == j) {
|
|
sb.write("Q ");
|
|
} else {
|
|
sb.write("* ");
|
|
}
|
|
}
|
|
print(sb.toString());
|
|
}
|
|
print("");
|
|
}
|
|
|
|
/**
|
|
Try all permutations using backtracking
|
|
*/
|
|
enumerate(int N) {
|
|
var a = new List(N);
|
|
_enumerate(a, 0);
|
|
}
|
|
|
|
_enumerate(List q, int n) {
|
|
if (n == q.length) {
|
|
printQueens(q);
|
|
} else {
|
|
for (int i = 0; i < q.length; i++) {
|
|
q[n] = i;
|
|
if (isConsistent(q, n)){
|
|
_enumerate(q, n+1);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
void main() {
|
|
enumerate(4);
|
|
}
|