java八皇后问题_面试题:八皇后问题(N皇后问题)

发布于:2021-10-28 09:39:47

前言


八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?这道题目也可以稍微延伸一下,变为 N×N的棋盘上放置N个皇后,其他条件相同。


下面介绍一种比较简单易懂的实现方式。


正文


算法


先说一下算法, 这里使用的是一个改良版的广度优先搜索算法。在N×N的棋盘上,我们先在第一行的第一个位置放置下皇后,接着我们就不去管第一行了,因为第一行已经不能放置皇后了。我们在第二行找到所有的可以放置皇后的位置。同理我们现在可以不用去管前两行了。我们对于第二行的每一个可以放置皇后的位置,都在第三行继续寻找可以放置皇后的位置,如此往复,直到我们遍历到最后一行。这个时候我们就得到了一部分解,这些解是对于第一个皇后放置在第一行第一列的位置而言。接下来对于第一行第二列、第三列…所有列都进行这个步骤,就得到了所有的解。


代码


为了更加直观,我们模拟出一个N×N的棋盘。我们把每次放置一个皇后之后的局面称为一个状态(State)。下面是State类的代码:


import java.util.ArrayList;


import java.util.List;


public class State {


private List pointList = new ArrayList();


private int lineNum;


public List getPointList() {


return pointList;


}


public int getLineNum(){


return lineNum;


}


public void setLineNum(int lineNum){


this.lineNum = lineNum;


}


}


每个state对象有两个属性,pointList存放的是当前的state下已经放置的皇后坐标,lineNum是当前state所遍历到的行数。其中用到的Point类代码如下:


public class Point{


private int X;


private int Y;


public Point(int x, int y){


this.X = x;


this.Y = y;


}


public int getX(){


return this.X;


}


public int getY(){


return this.Y;


}


public void setX(int x){


this.X = x;


}


public void setY(int y){


this.Y = y;


}


}


每个Point对象有一个X坐标和一个Y坐标。


下面是主程序:


import java.util.ArrayList;


import java.util.List;


import java.util.Stack;


public class EightQueen {


//起始状态列表


public static List startStates = new ArrayList();


//棋盘的行列数和要放置的皇后数量


public static final int lineNum = 4;


//一个N×N的棋盘


public static Point[][] allPoints = new Point[lineNum][lineNum];


//解法数量


public static int count = 0;


public static void main(String[] args) {


//初始化棋盘


for(int i=0; i


for(int j=0; j


allPoints[i][j] = new Point(i, j);


}


}


//初始化起始状态列表。每个State的PointList分别存放了第一行的8个坐标,并且设置第一行为遍历初始行


for(int i=0; i


State state = new State();


state.getPointList().add(new Point(0, i));


state.setLineNum(0);


startStates.add(state);


}


//对于初始化state列表中的每个state,进行遍历操作。


for(State state : startStates){


calculate(state);


}


System.out.println("总数为:" + count);


}


public static void calculate(State state)


{


Stack stack = new Stack();


stack.push(state);


while(!stack.isEmpty()){


//从stack里取出一个状态


State state2 = stack.pop();


//如果已经遍历到最后一行,输出这个解


if(state2.getLineNum() == lineNum - 1){


for(Point goalpoint : state2.getPointList()){


for(int i=0; i


if(i!=goalpoint.getY())


System.out.print("_ ");


else


System.out.print("Q ");


}


System.out.println();


}


System.out.println();


count++;


continue;


}


//否则寻找下一行可以放置皇后的位置


int currentLineNum = state2.getLineNum() + 1;


for(Point point : allPoints[currentLineNum]){


//如果该点可以放置皇后


if(isSatisfied(point, state2.getPointList()))


{


//创建一个state对象


State newState = new State();


//把这个新的state的pointList设置为前一个点的pointList里的所有点加上当前的点的坐标


for(Point point2 : state2.getPointList()){


newState.getPointList().add(new Point(point2.getX(), point2.getY()));


}


newState.getPointList().add(point);


//设置新的state的行数为下一行


newState.setLineNum(currentLineNum);


//入栈


stack.push(newState);


}


}


}


}


//判断一个点是否可以放置皇后


public static boolean isSatisfied(Point point, List list){


for(Point point2 : list){


//两个皇后不能再同一条横线、直线、斜线上。由于我们直接遍历的是下一行的点,所以肯定不会出现X坐标相同的情况


if(point2.getY() == point.getY()


|| Math.abs(point2.getX() - point.getX()) == Math.abs(point2.getY() - point.getY()))


return false;


}


return true;


}


}


程序的输出为


_ Q _ _


_ _ _ Q


Q _ _ _


_ _ Q _


_ _ Q _


Q _ _ _


_ _ _ Q


_ Q _ _


总数为:2


如果我们更改lineNum为6,输出为


_ Q _ _ _ _


_ _ _ Q _ _


_ _ _ _ _ Q


Q _ _ _ _ _


_ _ Q _ _ _


_ _ _ _ Q _


_ _ Q _ _ _


_ _ _ _ _ Q


_ Q _ _ _ _


_ _ _ _ Q _


Q _ _ _ _ _


_ _ _ Q _ _


_ _ _ Q _ _


Q _ _ _ _ _


_ _ _ _ Q _


_ Q _ _ _ _


_ _ _ _ _ Q


_ _ Q _ _ _


_ _ _ _ Q _


_ _ Q _ _ _


Q _ _ _ _ _


_ _ _ _ _ Q


_ _ _ Q _ _


_ Q _ _ _ _


总数为:4


由于lineNum = 8的时候输出太长,这里不做展示。结果的数量为92种。


这里附上不同lineNum对应的解法数量:


lineNum solution(lineNum)


1 1


2 0


3 0


4 2


5 10


6 4


7 40


8 92


9 352


10 724


11 2680


12 14200


13 73712


14 365596


15 2279184


16 14772512


17 95815104


18 666090624


19 4968057848


20 39029188884


21 314666222712


22 2691008701644


23 24233937684440


24 227514171973736


25 2207893435808352







相关资源:JAVA实现的八皇后问题

相关推荐

最新更新

猜你喜欢