８人の女王にチャレンジ - 失敗、そして挫折 2007/06/28 2007/07/05

プログラムの教科書によくでている８人の女王にチャレンジ。
単純に縦の線、横の線、斜めの線をチェックして、
みると案の上だめ。女王は８人いないといけないのです。


で、まちがいコード。
いや、数学はだめだめなので。

しかし、大学一年生レベルらしいんですよね。

正解はまた別記事で。

ちょっと参考書みて、考えたけど、よくわからないです。

結果

1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0
0 0 0 1 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
count:5

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++) {
System.out.print((B[i][j] ? "1" : "0") + " ");
if (B[i][j])
cnt++;
}
System.out.println();
}
return cnt;
}
}

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

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

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board.check(i, j)) {
board.set(i, j);
}
}
}

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

}