Eight Queens problem :
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that none of them can capture any other using the standard chess queen's moves.
I really enjoyed solving Eight queens problem manually as well as programatically.
Initially my code was returning 98. I literally diged a mountain to find the small rat (A small condition issue was throwing extra 6 wrong combination). Now I am getting unique 92 combination :).
Thank you very much 'Ranga Vure' for pointing out the issue.
import java.util.Set;
import java.util.TreeSet;
public class Chess8Queens {
private static final int chessBoard[][] = {{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0}};
private static final Set<String> blockedList = new TreeSet<String>();
private static final Set<String> result = new TreeSet<String>();
private static void printBoard(boolean isSuccess) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
System.out.print(chessBoard[i][j] == 0 ?
blockedList.contains(i + "" + j) ? "B " : "O "
: chessBoard[i][j]+" ");
if(chessBoard[i][j] != 0 && isSuccess) sb.append(j).append("|");
}
System.out.println("");
}
if(isSuccess)
result.add(sb.toString());
sb = null;
System.out.println("Done :" + result.size());
}
private static void updateBlockedSet(int row, int col, boolean isAdd) {
int flag1 = 0, flag2 = 0;
boolean temp;
if (col > row) {
flag1 = col - row;
flag2 = col + row;
for (int i = 0; i < 8; i++) {
if (col < 8) {
temp = isAdd ? blockedList.add(i + "" + col + "")
: blockedList.remove(i + "" + col + "");
}
if (row < 8 && col < 8) {
temp = isAdd ? blockedList.add(row + "" + i + "")
: blockedList.remove(row + "" + i + "");
}
if ((flag1 + i) < 8) {
temp = isAdd ? blockedList.add(i + "" + (flag1 + i) + "")
: blockedList.remove(i + "" + (flag1 + i) + "");
}
if ((flag2 - i) < 8) {
temp = isAdd ? blockedList.add(i + "" + (flag2 - i) + "")
: blockedList.remove(i + "" + (flag2 - i) + "");
}
}
} else if (col < row) {
flag1 = row - col;
flag2 = col + row;
for (int i = 0; i < 8; i++) {
if (col < 8) {
temp = isAdd ? blockedList.add(i + "" + col + "")
: blockedList.remove(i + "" + col + "");
}
if (row < 8) {
temp = isAdd ? blockedList.add(row + "" + i + "")
: blockedList.remove(row + "" + i + "");
}
if ((flag1 + i) < 8) {
temp = isAdd ? blockedList.add((flag1 + i) + "" + (i) + "")
: blockedList.remove((flag1 + i) + "" + (i) + "");
}
if ((flag2 - i) < 8) {
temp = isAdd ? blockedList.add((flag2 - i) + "" + (i) + "")
: blockedList.remove((flag2 - i) + "" + (i) + "");
}
}
} else {
for (int i = 0; i < 8; i++) {
flag1 = col > 4 ? 7-col : col;
flag2 = col + flag1;
flag1 = col - flag1;
temp = isAdd ? blockedList.add(i + "" + col + "")
: blockedList.remove(i + "" + col + "");
temp = isAdd ? blockedList.add(row + "" + i + "")
: blockedList.remove(row + "" + i + "");
temp = isAdd ? blockedList.add(i + "" + i + "")
: blockedList.remove(i + "" + i + "");
if((flag2-i) >= 0 && (flag2-i) < 8 && (flag1 + i) >= 0 && (flag1 + i) < 8)
temp = isAdd ? blockedList.add((flag2-i) + "" + (flag1 + i))
: blockedList.remove((flag2-i) + "" + (flag1 + i));
}
}
}
private static boolean adjustBadPosition(int row) {
int tempj=0;
boolean changed = false;
for(int j= 0; j<8; j++ ) {
if(chessBoard[row][j] != 0) {
chessBoard[row][j] = 0;
tempj = j;
changed = true;
}
}
if(changed) {
for(int j=tempj+1; j<8; j++)
blockedList.remove(row+""+j);
for(int i=row+1; i<8; i++) {
for(int j= 0; j<8; j++ ) {
chessBoard[i][j] = 0;
blockedList.remove(i+""+j);
}
}
resetUpdateList();
blockedList.add(row+""+tempj);
return true;
}
return false;
}
private static void resetUpdateList() {
for(int i=0; i<8; i++) {
for(int j= 0; j<8; j++ ) {
if(chessBoard[i][j] != 0 ) {
updateBlockedSet(i,j,true);
}
}
}
}
public static Set<String> getPositions() {
if(result.isEmpty()) {
for( int row = 0; row < 8; row++) {
if(row < 0) break;
for(int col = 0; col< 8; col++) {
if(!blockedList.contains(row+""+col)) {
chessBoard[row][col] = row+1;
updateBlockedSet(row,col,true);
break;
} else if(col == 7){
adjustBadPosition(row-1);
row = row -2;
break;
}
}
if(row == 7) {
printBoard(true);
adjustBadPosition(row);
row--;
}
}
}
return result;
}
public static void main(String... arg) {
//System.out.println(result);
System.out.println(getPositions().size());
}
}
Sample output :
1 B B B B B B B
B B B B 2 B B B
B B B B B B B 3
B B B B B 4 B B
B B 5 B B B B B
B B B B B B 6 B
B 7 B B B B B B
B B B 8 B B B B
Done1
92 positions : I have listed only columns.
0|4|7|5|2|6|1|3| = 0,0 | 1,4| 2,7 | 3,5| 4,2| 5,6 | 6,1| 7,3 = Top Listed board
0|5|7|2|6|3|1|4|
0|6|3|5|7|1|4|2|
0|6|4|7|1|3|5|2|
1|3|5|7|2|0|6|4|
1|4|6|0|2|7|5|3|
1|4|6|3|0|7|5|2|
1|5|0|6|3|7|2|4|
1|5|7|2|0|3|6|4|
1|6|2|5|7|4|0|3|
1|6|4|7|0|3|5|2|
1|7|5|0|2|4|6|3|
2|0|6|4|7|1|3|5|
2|4|1|7|0|6|3|5|
2|4|1|7|5|3|6|0|
2|4|6|0|3|1|7|5|
2|4|7|3|0|6|1|5|
2|5|1|4|7|0|6|3|
2|5|1|6|0|3|7|4|
2|5|1|6|4|0|7|3|
2|5|3|0|7|4|6|1|
2|5|3|1|7|4|6|0|
2|5|7|0|3|6|4|1|
2|5|7|0|4|6|1|3|
2|5|7|1|3|0|6|4|
2|6|1|7|4|0|3|5|
2|6|1|7|5|3|0|4|
2|7|3|6|0|5|1|4|
3|0|4|7|1|6|2|5|
3|0|4|7|5|2|6|1|
3|1|4|7|5|0|2|6|
3|1|6|2|5|7|0|4|
3|1|6|2|5|7|4|0|
3|1|6|4|0|7|5|2|
3|1|7|4|6|0|2|5|
3|1|7|5|0|2|4|6|
3|5|0|4|1|7|2|6|
3|5|7|1|6|0|2|4|
3|5|7|2|0|6|4|1|
3|6|0|7|4|1|5|2|
3|6|2|7|1|4|0|5|
3|6|4|1|5|0|2|7|
3|6|4|2|0|5|7|1|
3|7|0|2|5|1|6|4|
3|7|0|4|6|1|5|2|
3|7|4|2|0|6|1|5|
4|0|3|5|7|1|6|2|
4|0|7|3|1|6|2|5|
4|0|7|5|2|6|1|3|
4|1|3|5|7|2|0|6|
4|1|3|6|2|7|5|0|
4|1|5|0|6|3|7|2|
4|1|7|0|3|6|2|5|
4|2|0|5|7|1|3|6|
4|2|0|6|1|7|5|3|
4|2|7|3|6|0|5|1|
4|6|0|2|7|5|3|1|
4|6|0|3|1|7|5|2|
4|6|1|3|7|0|2|5|
4|6|1|5|2|0|3|7|
4|6|1|5|2|0|7|3|
4|6|3|0|2|7|5|1|
4|7|3|0|2|5|1|6|
4|7|3|0|6|1|5|2|
5|0|4|1|7|2|6|3|
5|1|6|0|2|4|7|3|
5|1|6|0|3|7|4|2|
5|2|0|6|4|7|1|3|
5|2|0|7|3|1|6|4|
5|2|0|7|4|1|3|6|
5|2|4|6|0|3|1|7|
5|2|4|7|0|3|1|6|
5|2|6|1|3|7|0|4|
5|2|6|1|7|4|0|3|
5|2|6|3|0|7|1|4|
5|3|0|4|7|1|6|2|
5|3|1|7|4|6|0|2|
5|3|6|0|2|4|1|7|
5|3|6|0|7|1|4|2|
5|7|1|3|0|6|4|2|
6|0|2|7|5|3|1|4|
6|1|3|0|7|4|2|5|
6|1|5|2|0|3|7|4|
6|2|0|5|7|4|1|3|
6|2|7|1|4|0|5|3|
6|3|1|4|7|0|2|5|
6|3|1|7|5|0|2|4|
6|4|2|0|5|7|1|3|
7|1|3|0|6|4|2|5|
7|1|4|2|0|6|3|5|
7|2|0|5|1|4|6|3|
7|3|0|2|5|1|6|4|
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that none of them can capture any other using the standard chess queen's moves.
I really enjoyed solving Eight queens problem manually as well as programatically.
Initially my code was returning 98. I literally diged a mountain to find the small rat (A small condition issue was throwing extra 6 wrong combination). Now I am getting unique 92 combination :).
Thank you very much 'Ranga Vure' for pointing out the issue.
import java.util.Set;
import java.util.TreeSet;
public class Chess8Queens {
private static final int chessBoard[][] = {{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0}};
private static final Set<String> blockedList = new TreeSet<String>();
private static final Set<String> result = new TreeSet<String>();
private static void printBoard(boolean isSuccess) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
System.out.print(chessBoard[i][j] == 0 ?
blockedList.contains(i + "" + j) ? "B " : "O "
: chessBoard[i][j]+" ");
if(chessBoard[i][j] != 0 && isSuccess) sb.append(j).append("|");
}
System.out.println("");
}
if(isSuccess)
result.add(sb.toString());
sb = null;
System.out.println("Done :" + result.size());
}
private static void updateBlockedSet(int row, int col, boolean isAdd) {
int flag1 = 0, flag2 = 0;
boolean temp;
if (col > row) {
flag1 = col - row;
flag2 = col + row;
for (int i = 0; i < 8; i++) {
if (col < 8) {
temp = isAdd ? blockedList.add(i + "" + col + "")
: blockedList.remove(i + "" + col + "");
}
if (row < 8 && col < 8) {
temp = isAdd ? blockedList.add(row + "" + i + "")
: blockedList.remove(row + "" + i + "");
}
if ((flag1 + i) < 8) {
temp = isAdd ? blockedList.add(i + "" + (flag1 + i) + "")
: blockedList.remove(i + "" + (flag1 + i) + "");
}
if ((flag2 - i) < 8) {
temp = isAdd ? blockedList.add(i + "" + (flag2 - i) + "")
: blockedList.remove(i + "" + (flag2 - i) + "");
}
}
} else if (col < row) {
flag1 = row - col;
flag2 = col + row;
for (int i = 0; i < 8; i++) {
if (col < 8) {
temp = isAdd ? blockedList.add(i + "" + col + "")
: blockedList.remove(i + "" + col + "");
}
if (row < 8) {
temp = isAdd ? blockedList.add(row + "" + i + "")
: blockedList.remove(row + "" + i + "");
}
if ((flag1 + i) < 8) {
temp = isAdd ? blockedList.add((flag1 + i) + "" + (i) + "")
: blockedList.remove((flag1 + i) + "" + (i) + "");
}
if ((flag2 - i) < 8) {
temp = isAdd ? blockedList.add((flag2 - i) + "" + (i) + "")
: blockedList.remove((flag2 - i) + "" + (i) + "");
}
}
} else {
for (int i = 0; i < 8; i++) {
flag1 = col > 4 ? 7-col : col;
flag2 = col + flag1;
flag1 = col - flag1;
temp = isAdd ? blockedList.add(i + "" + col + "")
: blockedList.remove(i + "" + col + "");
temp = isAdd ? blockedList.add(row + "" + i + "")
: blockedList.remove(row + "" + i + "");
temp = isAdd ? blockedList.add(i + "" + i + "")
: blockedList.remove(i + "" + i + "");
if((flag2-i) >= 0 && (flag2-i) < 8 && (flag1 + i) >= 0 && (flag1 + i) < 8)
temp = isAdd ? blockedList.add((flag2-i) + "" + (flag1 + i))
: blockedList.remove((flag2-i) + "" + (flag1 + i));
}
}
}
private static boolean adjustBadPosition(int row) {
int tempj=0;
boolean changed = false;
for(int j= 0; j<8; j++ ) {
if(chessBoard[row][j] != 0) {
chessBoard[row][j] = 0;
tempj = j;
changed = true;
}
}
if(changed) {
for(int j=tempj+1; j<8; j++)
blockedList.remove(row+""+j);
for(int i=row+1; i<8; i++) {
for(int j= 0; j<8; j++ ) {
chessBoard[i][j] = 0;
blockedList.remove(i+""+j);
}
}
resetUpdateList();
blockedList.add(row+""+tempj);
return true;
}
return false;
}
private static void resetUpdateList() {
for(int i=0; i<8; i++) {
for(int j= 0; j<8; j++ ) {
if(chessBoard[i][j] != 0 ) {
updateBlockedSet(i,j,true);
}
}
}
}
public static Set<String> getPositions() {
if(result.isEmpty()) {
for( int row = 0; row < 8; row++) {
if(row < 0) break;
for(int col = 0; col< 8; col++) {
if(!blockedList.contains(row+""+col)) {
chessBoard[row][col] = row+1;
updateBlockedSet(row,col,true);
break;
} else if(col == 7){
adjustBadPosition(row-1);
row = row -2;
break;
}
}
if(row == 7) {
printBoard(true);
adjustBadPosition(row);
row--;
}
}
}
return result;
}
public static void main(String... arg) {
//System.out.println(result);
System.out.println(getPositions().size());
}
}
Sample output :
1 B B B B B B B
B B B B 2 B B B
B B B B B B B 3
B B B B B 4 B B
B B 5 B B B B B
B B B B B B 6 B
B 7 B B B B B B
B B B 8 B B B B
Done1
92 positions : I have listed only columns.
0|4|7|5|2|6|1|3| = 0,0 | 1,4| 2,7 | 3,5| 4,2| 5,6 | 6,1| 7,3 = Top Listed board
0|5|7|2|6|3|1|4|
0|6|3|5|7|1|4|2|
0|6|4|7|1|3|5|2|
1|3|5|7|2|0|6|4|
1|4|6|0|2|7|5|3|
1|4|6|3|0|7|5|2|
1|5|0|6|3|7|2|4|
1|5|7|2|0|3|6|4|
1|6|2|5|7|4|0|3|
1|6|4|7|0|3|5|2|
1|7|5|0|2|4|6|3|
2|0|6|4|7|1|3|5|
2|4|1|7|0|6|3|5|
2|4|1|7|5|3|6|0|
2|4|6|0|3|1|7|5|
2|4|7|3|0|6|1|5|
2|5|1|4|7|0|6|3|
2|5|1|6|0|3|7|4|
2|5|1|6|4|0|7|3|
2|5|3|0|7|4|6|1|
2|5|3|1|7|4|6|0|
2|5|7|0|3|6|4|1|
2|5|7|0|4|6|1|3|
2|5|7|1|3|0|6|4|
2|6|1|7|4|0|3|5|
2|6|1|7|5|3|0|4|
2|7|3|6|0|5|1|4|
3|0|4|7|1|6|2|5|
3|0|4|7|5|2|6|1|
3|1|4|7|5|0|2|6|
3|1|6|2|5|7|0|4|
3|1|6|2|5|7|4|0|
3|1|6|4|0|7|5|2|
3|1|7|4|6|0|2|5|
3|1|7|5|0|2|4|6|
3|5|0|4|1|7|2|6|
3|5|7|1|6|0|2|4|
3|5|7|2|0|6|4|1|
3|6|0|7|4|1|5|2|
3|6|2|7|1|4|0|5|
3|6|4|1|5|0|2|7|
3|6|4|2|0|5|7|1|
3|7|0|2|5|1|6|4|
3|7|0|4|6|1|5|2|
3|7|4|2|0|6|1|5|
4|0|3|5|7|1|6|2|
4|0|7|3|1|6|2|5|
4|0|7|5|2|6|1|3|
4|1|3|5|7|2|0|6|
4|1|3|6|2|7|5|0|
4|1|5|0|6|3|7|2|
4|1|7|0|3|6|2|5|
4|2|0|5|7|1|3|6|
4|2|0|6|1|7|5|3|
4|2|7|3|6|0|5|1|
4|6|0|2|7|5|3|1|
4|6|0|3|1|7|5|2|
4|6|1|3|7|0|2|5|
4|6|1|5|2|0|3|7|
4|6|1|5|2|0|7|3|
4|6|3|0|2|7|5|1|
4|7|3|0|2|5|1|6|
4|7|3|0|6|1|5|2|
5|0|4|1|7|2|6|3|
5|1|6|0|2|4|7|3|
5|1|6|0|3|7|4|2|
5|2|0|6|4|7|1|3|
5|2|0|7|3|1|6|4|
5|2|0|7|4|1|3|6|
5|2|4|6|0|3|1|7|
5|2|4|7|0|3|1|6|
5|2|6|1|3|7|0|4|
5|2|6|1|7|4|0|3|
5|2|6|3|0|7|1|4|
5|3|0|4|7|1|6|2|
5|3|1|7|4|6|0|2|
5|3|6|0|2|4|1|7|
5|3|6|0|7|1|4|2|
5|7|1|3|0|6|4|2|
6|0|2|7|5|3|1|4|
6|1|3|0|7|4|2|5|
6|1|5|2|0|3|7|4|
6|2|0|5|7|4|1|3|
6|2|7|1|4|0|5|3|
6|3|1|4|7|0|2|5|
6|3|1|7|5|0|2|4|
6|4|2|0|5|7|1|3|
7|1|3|0|6|4|2|5|
7|1|4|2|0|6|3|5|
7|2|0|5|1|4|6|3|
7|3|0|2|5|1|6|4|
No comments:
Post a Comment