８人の女王に再チャレンジ - 一応できたけど... 2007/07/05

8人の女王に再チャレンジ、一応ひとつ解をもとめることはできたけども、どうもいい感じではないです。

一応、コードは再帰しているのでそれっぽい感じにはなっています。

1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
count:8

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) {
fail_3();
}

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

fill(0, board);

board.disp();
System.out.println("count:" + board.countQueen());
}

public static boolean 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);
if (!fill(k + 1, board)) {
board.unset(k, i);
}
}
}

}
return board.countQueen() == board.N;

}
}