#codingexercise
Position eight queens on a chess board without conflicts:
public static void positionEightQueens(int[][] B, int[][] used, int row) throws Exception {
if (row == 8) {
if (isAllSafe(B)) {
printMatrix(B, B.length, B[0].length);
}
return;
}
for (int k = 0; k < 8; k++) {
if ( isSafe(B, row, k) && isAllSafe(B)) {
B[row][k] = 1;
positionEightQueens(B, used, row + 1);
B[row][k] = 0;
}
}
}
public static boolean isSafe(int[][] B, int p, int q) {
int row = B.length;
int col = B[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i == p && j == q) { continue; }
if (B[i][j] == 1) {
boolean notSafe = isOnDiagonal(B, p, q, i, j) ||
isOnVertical(B, p, q, i, j) ||
isOnHorizontal(B, p, q, i, j);
if(notSafe){
return false;
}
}
}
}
return true;
}
public static boolean isAllSafe(int[][] B) {
for (int i = 0; i < B.length; i++) {
for (int j = 0; j < B[0].length; j++) {
if (B[i][j] == 1 && !isSafe(B, i, j)) {
return false;
}
}
}
return true;
}
public static boolean isOnDiagonal(int[][] used, int r1, int c1, int r2, int c2) {
boolean result = false;
int row = used.length;
int col = used[0].length;
for (int k = 0; k < 8; k ++) {
if (r2 - k >= 0 && c2 - k >= 0 && r1 == r2 - k && c1 == c2 - k) {
return true;
}
if (r2 + k < row && c2 + k < col && r1 == r2 + k && c1 == c2 + k) {
return true;
}
if (r2 - k >= 0 && c2 + k < col && r1 == r2 - k && c1 == c2 + k) {
return true;
}
if (r2 + k < row && c2 - k >= 0 && r1 == r2 + k && c1 == c2 - k) {
return true;
}
}
return result;
}
public static boolean isOnVertical(int[][] used, int r1, int c1, int r2, int c2) {
boolean result = false;
int row = used.length;
int col = used[0].length;
for (int k = 0; k < 8; k++) {
if (c2 - k >= 0 && c1 == c2 - k && r1 == r2 ) {
return true;
}
if (c2 + k < row && c1 == c2 + k && r1 == r2) {
return true;
}
}
return result;
}
public static boolean isOnHorizontal(int[][] used, int r1, int c1, int r2, int c2) {
boolean result = false;
int row = used.length;
int col = used[0].length;
for (int k = 0; k < 8; k++) {
if (r2 - k >= 0 && r1 == r2 - k && c1 == c2 ) {
return true;
}
if (r2 + k < row && r1 == r2 + k && c1 == c2) {
return true;
}
}
return result;
}
Sample output:
1 1 2 1 1 1 1 1
1 1 1 1 1 2 1 1
1 1 1 2 1 1 1 1
1 2 1 1 1 1 1 1
1 1 1 1 1 1 1 2
1 1 1 1 2 1 1 1
1 1 1 1 1 1 2 1
2 1 1 1 1 1 1 1
No comments:
Post a Comment