八皇后算法 回溯 递归 java
程序员文章站
2022-05-06 11:34:19
...
八皇后算法 回溯 递归 java
国际象棋棋盘 其中 一种解法
算法:
1.判断 是否是 在米字形 上
2. 递归查找 下一个,没有,返回上一行,换一个位置继续查找(n 盘 n 皇后问题,一行有且之有一个位置)
代码
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/
谢谢您的赞助,我会做的更好!
上一篇: PHP缓存之模块缓存(APC)