catalogue

1, Understand the background of the eight queens problem (the eight queens problem Baidu Encyclopedia)

2, General idea

3, Analyze key details

IV. labeling

1, Understand the background of the eight queens problem( Eight queens problem_ Baidu Encyclopedia)

in short:

At 8 × Eight queens are placed on the 8-grid chess so that they can't attack each other,

That is, any two Queens can't be in the same row, column or slash. How many kinds of pendulum methods are there.

2, General idea

Exhaustive must have a big head. It is required to think of an 8 * 8 chessboard, each line must have and only one queen. Now is the problem of how to sort these 8 lines (each line only has a queen in a certain position). Thus, two more intelligent ideas can be developed:

1. Linear Algebra: use the elimination matrix to multiply the identity matrix to the left, and then use the line generation method (there cannot be two identical numbers identifying the queen on the diagonal of the matrix block) 2 Recursion (used in this example): after determining the Queen's position in each line, continue to determine the Queen's position in the next line according to the search method of the line

2. Let's start with a small one. Use the 4 * 4 matrix, set the placeable point to 0 and the non placeable point to non-0 (for code simplification), and then imagine the creation sequence and destruction sequence of the "tree" branch (that is, the sequence of the end of the exploration route). At each point, put the point straight down, and add restriction marks in the lower left and right directions of 45 degrees. After the data is transmitted to the next branch, restore it to its original state

3, Analyze key details

First of all, we can imagine that according to the advance of time, the search process forms a node bifurcation and then bifurcation similar to a binary tree Therefore, different branches from the same node (i.e. a determined queen position on the chessboard) cannot affect each other. Therefore, it should be noted that during recursion, the parameters of the function should try to avoid the operation of the same memory by reference and pointer, It is also not recommended to use heap memory replication to solve this problem (the tree structure is very large. If memory is not released properly, the memory will be tight after a few adjustments (it should be like this))

In addition, when switching between multiple available points in the same line, we should not only eliminate the impact caused by the previous point, but also prevent the constraints left by the previous lines to the subsequent points from being destroyed in the process of restoration

In addition, when a row is all restricted (there is no place to place), it means that all branches below the corresponding starting node position in the upper row of the full row have no solution, so switch directly to the next available node of the starting node to continue the search

IV. labeling

#include <iostream>
#Define nquens 8 / / any queen
short count_lastRow(short *s)
{
    short fd = 0;
    for (short d = 0; d < NQueens; d++)
        fd += *(s + d) ? 0 : 1;
    return fd;
}
#include <malloc.h>
using namespace std;
//Set and remove restrictions on diagonal elements
void setDian1(short *ss, short row, short column, short dir/*The lower left / right 45 degree line identifies the unavailable direction*/, short ax/*Mark whether to add restriction or cancel restriction*/) //0 represents the left and non-zero represents the right
{                                                                      
//Note that both row and column start with 1
    if (row < NQueens + 1 && column > 0 && column < NQueens + 1)
    {
        *(ss + (row - 1) * NQueens + column - 1) += ax ? 1 : -1;
        setDian1(ss, row + 1, column + (dir ? 1 : -1), dir, ax);
    }
}
//Display array
void print(short ss[][NQueens])
{
    printf("-------one posibility-------\n");
    for (short d = 0; d < NQueens; d++)
    {
        for (short a = 0; a < NQueens; a++)
            cout << ss[d][a] << "  ";
        cout << endl;
    }
    printf("---------------------------\n");
}
//Principal recursive function
void k(short x, short pt[NQueens][NQueens], register short &total)
{
    if (x == NQueens)
    {
        total += count_lastRow(pt[NQueens - 1]);
        print(pt);
        return;
    }
    for (short as = 0; as < NQueens; as++)
    {
        if (pt[x - 1][as] == 0) //Only 0 represents vacancy, and the other conditions are limited by > = 1
        {
            for (short w = x - 1; w < NQueens; w++)
                pt[w][as] += 1;
            setDian1(&pt[0][0], x, as + 1, 0, 1);
            setDian1(&pt[0][0], x, as + 1, 1, 1); //The last parameter is mark write and delete, 1 write 0 delete
            pt[x - 1][as] = 5;
            k(x + 1, pt, total);
//Pass the restricted data matrix to the next branch and clear the restrictions imposed in this round
            for (short w = x - 1; w < NQueens; w++)
                pt[w][as] += -1;
            setDian1(&pt[0][0], x, as + 1, 0, 0);
            setDian1(&pt[0][0], x, as + 1, 1, 0);
            pt[x - 1][as] = 0;
        }
    }
}
int main()
{
    register short total = 0;
    short w[NQueens][NQueens];
    for (short d = 0; d < NQueens; d++)
    {
        for (short a = 0; a < NQueens; a++)
            w[d][a] = 0;
    }
    k(1, w, total);
    printf("All posibilities total up to %d\n", total);
    return 0;
}

PS: if you have a symmetrical chessboard, you need to divide the result by 2. After calculating the ten queens for nearly 30 seconds, you can get 724 asymmetric solutions for reference