８人の女王に再再チャレンジ - 一応バックトラック 2007/07/06

８人の女王はバックトラックの例題でよくでてくるようです。

バックトラッキング - Wikipedia

バックトラックとは、だめだったらひとつもどって再チャレンジという感じです。


８Ｘ８で９２みつかりましたので、正解だと思います。

下記のコードは一応バックトラックしてます。
８人の女王はほかにビットをつかったりして計算させる方法など、高速化の方法もあるようです。

package queen8;

public class TestQueen8 {

static class Board {

boolean[][] B;
int N;

public Board(int N) {
this.N = N;

B = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
B[i][j] = false;
}
}

}

public void set(int x, int y) {
B[x][y] = true;
}

public boolean check(int x, int y) {

// check H
if (!checkHLine(x, y)) {
return false;
}

// check V
if (!checkVLine(x, y)) {
return false;
}

// check cross
if (!checkCross(x, y)) {
return false;
}

return true;
}

public void unset(int x, int y) {
B[x][y] = false;
}

public boolean checkHLine(int x, int y) {
for (int i = 0; i < N; i++) {
if (get(i, y) && !(x == i)) {
return false;
}
}
return true;
}

public boolean checkVLine(int x, int y) {
for (int i = 0; i < N; i++) {
if (get(x, i) && !(y == i))
return false;
}
return true;
}

public boolean checkCross(int x, int y) {
if (get(x, y))
return false;

int ux, uy;
ux = x;
uy = y;

// up left
for (;;) {
ux -= 1;
uy -= 1;
if (!(0 <= ux && 0 <= uy))
break;
if (B[ux][uy])
return false;
}
// up right
ux = x;
uy = y;

for (;;) {
ux += 1;
uy -= 1;
if (!(ux < N && 0 <= uy))
break;
if (B[ux][uy])
return false;
}
// down left
ux = x;
uy = y;
for (;;) {
ux -= 1;
uy += 1;
if (!(0 <= ux && uy < N))
break;
if (B[ux][uy])
return false;
}

// down right
ux = x;
uy = y;
for (;;) {
ux += 1;
uy += 1;
if (!(ux < N && uy < N))
break;
if (B[ux][uy])
return false;
}
return true;
}

public boolean get(int x, int y) {
return B[x][y];
}

public int size() {
return N;
}

public int countQueen() {
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (B[i][j])
cnt++;
}
}
return cnt;
}

public void disp() {
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print((B[i][j] ? "1" : "0") + " ");
if (B[i][j])
cnt++;
}
System.out.println();
}
}
}

public static void main(String[] args) {
a();
}

public static void a() {
int N = 8;
Board board = new Board(N);

fill(0, board);

System.out.println();
System.out.println("total:"+cnt);
}
public static int cnt = 0;

public static void fill(int k, Board board) {
if (k < board.N) {
for (int i = 0; i < board.N; i++) {
if (board.check(k, i)) {
board.set(k, i);
fill(k + 1, board);
board.unset(k, i);

}
}
} else {
board.disp();
System.out.println("count:" + board.countQueen());
cnt++;
}
return;
}
}