当前位置：网站首页>Interview question: Queen eight question (Queen n question) [suggestions collection]

Interview question: Queen eight question (Queen n question) [suggestions collection]

2022-07-21 08:16:00 【Full stack programmer webmaster】

Hello everyone , I meet you again , I'm the king of the whole stack .

Preface

The eight queens problem is a problem based on chess ： How to be in 8×8 Eight queens are placed on the chess board , So that no queen can directly eat other queens ？ This topic can also be extended a little , Turn into N×N On the chessboard N A queen , Other conditions are the same . Here is a simple and easy to understand implementation .

Project download address

Text

Algorithm

Let's talk about the algorithm first , An improved breadth first search algorithm is used here . stay N×N On the chessboard , Let's first place the queen in the first position of the first row , Then we don't care about the first line , Because the queen cannot be placed in the first row . We find all the places where the queen can be placed on the second line . Similarly, we can now ignore the first two lines . For each of the second row, we can place the queen , Continue to look for the position where the queen can be placed in the third line , So back and forth , Until we traverse to the last line . At this time, we get a decomposition , These solutions are for the first queen to be placed in the first row and the first column . Next, for the first row and the second column 、 The third column … All columns go through this step , And you get all the answers .

Code

To be more intuitive , We simulated a N×N The chessboard of . We call the situation after placing a queen every time as a state (State). Here is State Class code :

import java.util.ArrayList;
import java.util.List;

public class State { 
     
    private List<Point> pointList = new ArrayList<Point>();
    private int lineNum;

    public List<Point> getPointList() {
        return pointList;
    }

    public int getLineNum(){
        return lineNum;
    }

    public void setLineNum(int lineNum){
        this.lineNum = lineNum;
    }

}

Every state Object has two properties ,pointList What is stored is the current state Under the coordinates of the queen that has been placed ,lineNum It is the present. state The number of rows traversed . Used in Point The class code is as follows ：

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;
    }

}

Every Point The object has a X Coordinates and a Y coordinate . The following is the main program ：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class EightQueen { 
     
    // Starting state list 
    public static List<State> startStates = new ArrayList<State>();

    // The number of rows and rows of the chessboard and the number of queens to be placed 
    public static final int lineNum = 4;

    // One N×N The chessboard of 
    public static Point[][] allPoints = new Point[lineNum][lineNum];

    // Solution quantity 
    public static int count = 0;

    public static void main(String[] args) {

        // Initialize chessboard 
        for(int i=0; i<lineNum; i++){
            for(int j=0; j<lineNum; j++){
                allPoints[i][j] = new Point(i, j);
            }
        }

        // Initialize the starting state list . Every State Of PointList The first row of 8 A coordinate , And set the first line to traverse the initial line 
        for(int i=0; i<lineNum; i++){
            State state = new State();
            state.getPointList().add(new Point(0, i));
            state.setLineNum(0);
            startStates.add(state);
        }

        // For initialization state Each in the list state, Traverse .
        for(State state : startStates){
            calculate(state);
        }
        System.out.println(" The total number is ：" + count); 
    }

    public static void calculate(State state)
    {
        Stack<State> stack = new Stack<State>();
        stack.push(state);
        while(!stack.isEmpty()){
            // from stack Take out a state 
            State state2 = stack.pop();
            // If you have traversed to the last line , Output this solution 
            if(state2.getLineNum() == lineNum - 1){
                for(Point goalpoint : state2.getPointList()){
                    for(int i=0; i<lineNum; i++){
                        if(i!=goalpoint.getY())
                            System.out.print("_ ");
                        else
                            System.out.print("Q ");
                    }
                    System.out.println(); 
                }
                System.out.println();
                count++;
                continue;
            }

            // Otherwise, find the next line where the queen can be placed 
            int currentLineNum = state2.getLineNum() + 1;
            for(Point point : allPoints[currentLineNum]){
                // If the queen can be placed at this point 
                if(isSatisfied(point, state2.getPointList()))
                {
                    // Create a state object 
                    State newState = new State();
                    // Put this new state Of pointList Set to the previous point pointList Add the coordinates of all points in the current point 
                    for(Point point2 : state2.getPointList()){
                        newState.getPointList().add(new Point(point2.getX(), point2.getY()));
                    }
                    newState.getPointList().add(point);
                    // Set up the new state The number of lines is the next line 
                    newState.setLineNum(currentLineNum);
                    // Push 
                    stack.push(newState);
                }
            }
        }
    }

    // Judge whether a point can place a queen 
    public static boolean isSatisfied(Point point, List<Point> list){
        for(Point point2 : list){
            // Two Queens can no longer be on the same horizontal line 、 A straight line 、 On the diagonal . Because we directly traverse the next line of points , So it certainly won't happen X When the coordinates are the same 
            if(point2.getY() == point.getY() 
                    || Math.abs(point2.getX() - point.getX()) == Math.abs(point2.getY() - point.getY()))
                return false;
        }
        return true;
    }

}

The output of the program is

_ Q _ _ 
_ _ _ Q 
Q _ _ _ 
_ _ Q _ 

_ _ Q _ 
Q _ _ _ 
_ _ _ Q 
_ Q _ _ 

 The total number is ：2

If we change lineNum by 6, Output is

_ Q _ _ _ _ 
_ _ _ Q _ _ 
_ _ _ _ _ Q 
Q _ _ _ _ _ 
_ _ Q _ _ _ 
_ _ _ _ Q _ 

_ _ Q _ _ _ 
_ _ _ _ _ Q 
_ Q _ _ _ _ 
_ _ _ _ Q _ 
Q _ _ _ _ _ 
_ _ _ Q _ _ 

_ _ _ Q _ _ 
Q _ _ _ _ _ 
_ _ _ _ Q _ 
_ Q _ _ _ _ 
_ _ _ _ _ Q 
_ _ Q _ _ _ 

_ _ _ _ Q _ 
_ _ Q _ _ _ 
Q _ _ _ _ _ 
_ _ _ _ _ Q 
_ _ _ Q _ _ 
_ Q _ _ _ _ 

 The total number is ：4

because lineNum = 8 The output is too long , There's no show here . The number of results is 92 Kind of . Here are different lineNum Number of corresponding solutions ：

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

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/108336.html Link to the original text ：https://javaforall.cn

原网站

版权声明
本文为[Full stack programmer webmaster]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/202/202207201239431311.html