?
?
?
? ? ? ? ??
? ? ? ? ? ? 国际象棋棋盘 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?其中 一种解法
?
?
?
算法：
1.判断 是否是 在米字形 上
2. 递归查找 下一个，没有，返回上一行，换一个位置继续查找(n 盘 n 皇后问题，一行有且之有一个位置)
?
?
?
?
代码
class="java" name="code">
import java.util.concurrent.atomic.AtomicInteger;
public class EightQueue {
public static void main(String[] args) {
// testCheck();
for (int i = 4; i < 9; i++) {
int rows = i; //行 一排
int cols = i; //列
int [][] queue = new int[rows][cols];
AtomicInteger backtrack = backtrack(queue,0,new AtomicInteger(0));
System.out.println(i+"阶"+backtrack.get());
}
}
static AtomicInteger backtrack(int [][] queue,int row,AtomicInteger ai){
int rows = queue.length ;
int cols = queue[0].length ;
if (row == -1) {
return ai;
}
if (row == rows) {
ai.getAndIncrement();
//System.out.println("第"+ai.get()+"种解法");
//print(queue);
//System.out.println();
return backtrack(queue, row-1,ai);
}
int j = 0;
for (int i = 0 ; i< rows; i++) {
if (queue[row][i] == 1) {
j = i+1;
queue[row][i] = 0;
}
}
boolean flag =false;
for (; j < cols; j++) {
if (!flag && check(row, j, queue)) {
queue[row][j] = 1;
flag =true;
}
}
if (!flag) {
return backtrack(queue, row-1,ai);
}
return backtrack(queue, row+1,ai);
}
static void print(int [][] queue){
int rows = queue.length;
int cols = queue[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
System.out.print(queue[i][j]);
}
System.out.println();
}
}
static void testCheck(){
int rows = 8; //行 一排
int cols = 8; //列
int x= 1,y =1;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int [][] queue = new int[rows][cols];
queue[i][j] = 1;
boolean check = check(x, y, queue);
System.out.print(check +" ");
}
System.out.println();
}
// false false false true true true true true
// false false false false false false false false
// false false false true true true true true
// true false true false true true true true
// true false true true false true true true
// true false true true true false true true
// true false true true true true false true
// true false true true true true true false
}
static boolean check(int x,int y ,int [][] queue){
int rows = queue.length;
int cols = queue[0].length;
//判断四条线是否有冲突
//1.横向是否有冲突
for (int i = 0; i < cols; i++) {
if (queue[i][y] == 1) {
return false;
}
}
//2.纵是否有冲突
for (int i = 0; i < rows; i++) {
if (queue[x][i] == 1) {
return false;
}
}
//3.米撇是否有冲突
for (int i = 0; i < rows; i++) {
if ( y-i+x >= 0 && y-i+x <= rows-1 && queue[y-i+x][i] == 1) {
return false;
}
}
//4.米捺是否有冲突
for (int i = 0; i < rows; i++) {
if ( y-x+i >= 0 && y-x+i <= rows-1 && queue[i][ y-x+i] == 1) {
return false;
}
}
return true;
}
}
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
在兴趣的驱动下,写一个免费的东西，有欣喜，也还有汗水，希望你喜欢我的作品，同时也能支持一下。 当然，有钱捧个钱场（支持支付宝和微信 以及扣扣群），没钱捧个人场，谢谢各位。
?
个人主页：http://knight-black-bob.iteye.com/
?
?
?谢谢您的赞助，我会做的更好！
相关文章
