Money is not everything. There’s MasterCard.


Money is not everything. there’s mastercard &visa.

background

The movie has been rewritten a hundred times. Every time I look at it, I feel it every time. If I could go back in time, I wouldn’t have… I regret it, I regret it.



Although there is no regret medicine in the world, but there is regret medicine in the algorithm world, it is — backtracking algorithm. Life can’t go back in time. I put my algorithm back in time.

The question of eight Queens was first put forward by the chess player Max Bethel in 1848, and now in the 21st century, how could eight queens satisfy me? I decided to have one N Queen, as many queens as I wanted.

All source code has been uploaded to Github: link

N queen

thinking

Every family has its faults, and a queen has her faults. This queen needs to be handled properly. We can’t let them fight. I can declare a one-dimensional array of size N to store my N queens. And then it’s divided into N stages.

  • The first stage is to pick a random position.
  • The second stage needs to judge whether my horizontal, vertical, left diagonal, right diagonal (only need to compare with the first stage and itself) has a queen. If not, continue down.
  • In the third stage, the queen is found, do not panic, it does not matter, go back in time, to the second stage, re-placed.
  • Stage N…. Until every queen is satisfied with the position.

That’s the general idea.

Initialize the

/** * private int[] queens; /** * n */ private int n; /** ** private int count; Private SolveNQueens(int N) {queens = new int[N]; this.n = n; count = 0; }Copy the code

recursive

The code is minimal, but the point is that the recursion is hard to understand. Recursion in a loop, very clever. You just have to follow it step by step.

The one-dimensional array stores the value of the queen’s position (0, n-1).

The default is to start from scratch, so you call this method calNQueens(0)

    private void calNQueens(int row) {
        if (row == n) {
            printQueens(queens);
            return;
        }
        for (int col = 0; col < n; col++) {
            if(isSatisfy(row, col)) { queens[row] = col; calNQueens(row + 1); }}}Copy the code

Whether the conditions are met

This method needs to determine whether there is a queen on the left and right diagonals.

So I’m going to put three ifs in the loop just to make it easier to understand.

    private boolean isSatisfy(int row, int col) {
//        System.out.println("(" + row + "," + col + ")");
        int leftUp = col - 1;
        int rightUp = col + 1;
        for (int i = row - 1; i >= 0; --i) {
            if (queens[i] == col) return false;
            if (leftUp >= 0 && queens[i] == leftUp) return false;
            if (rightUp < n && queens[i] == rightUp) return false;
            --leftUp;
            ++rightUp;
        }
        return true;
    }Copy the code

print

    private void printQueens(int[] queens) {
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (queens[row] == col) System.out.print("1");
                else System.out.print("0");
            }
            System.out.println();
        }
        System.out.println();
        ++count;
    }Copy the code

The test code

    public static void main(String[] args) {
        int n = 8;
        SolveNQueens solveNQueens = new SolveNQueens(n);
        solveNQueens.calNQueens(0);
        System.out.println("Total" + solveNQueens.count + "Kind of pendulum.");
    }Copy the code

The test results

4 the queen



Eight queens (here is the solution that includes the solution of rotation and symmetry, otherwise 12 pendulum methods)



end



Your likes and attention are my biggest support, thank you!