-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathQueenBoard.java
119 lines (115 loc) · 2.64 KB
/
QueenBoard.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
public class QueenBoard{
private int[][] board;
public QueenBoard(int size){
board = new int[size][size];
}
private boolean addQueen(int r, int c){
return changeQueen(r,c,1,-1);
}
private boolean removeQueen(int r, int c){
return changeQueen(r,c,-1,0);
}
private boolean changeQueen(int r, int c, int change, int queen){
if(board[r][c] > 0 || board[r][c] == queen){
return false;
}
for(int x = 0; x < board.length; x++){
board[r][x] += change;
}
for (int[] row: board) {
row[c] += change;
}
for(int row = r, col = c; col >= 0 && row >= 0; col--, row--){
board[row][col] += change;
}
for(int row = r, col = c; col < board[0].length && row >= 0; col++, row--){
board[row][col] += change;
}
for(int row = r, col = c; col < board[0].length && row < board.length; col++, row++){
board[row][col] += change;
}
for(int row = r, col = c; col >= 0 && row < board.length; col--, row++){
board[row][col] += change;
}
board[r][c] = queen;
return true;
}
public String toString(){
String s = "";
for (int a = 0; a < board.length; a++) {
for(int x = 0; x < board[a].length; x++){
if (board[a][x] > -1){
s+= "_";
} else{
s += "Q";
}
if(x < board[a].length -1){
s += " ";
}
}
if(a < board.length){
s+= "\n";
}
}
return s;
}
public String toStringDebug(){
String s = "";
for (int[] row: board) {
for (int x : row ) {
s += x;
s += " ";
}
s += "\n";
}
return s;
}
public boolean solve(){
for (int[] row: board) {
for (int val : row ) {
if(val != 0){
throw new IllegalStateException();
}
}
}
return solveR(0);
}
private boolean solveR(int col){
if (col >= board.length){
return true;
}
for(int x = 0; x < board.length; x++){
if(addQueen(x,col)){
if(solveR(col + 1)){
return true;
}
removeQueen(x,col);
}
}
return false;
}
public int countSolutions(){
for (int[] row: board) {
for (int val : row ) {
if(val != 0){
throw new IllegalStateException();
}
}
}
return countSolsR(0);
}
private int countSolsR(int col){
int sols = 0;
if (col >= board.length){
sols++;
return sols;
}
for(int x = 0; x < board.length; x++){
if(addQueen(x,col)){
sols += countSolsR(col + 1);
removeQueen(x,col);
}
}
return sols;
}
}