[data structure day15--N queen problem solving]

N-queens problem

Problem description

In n × N queens are placed on the n-grid chess so that they cannot attack each other, that is, they cannot be in the same column or line, nor on the same slash. How many kinds of placement methods are there?

example


The N-queen problem is a classic case of backtracking algorithm. Here we use recursive backtracking to solve it.

Algorithm idea

(1) Use a one-dimensional array to store the chessboard, clear the chessboard, and set the current row as row 1 and the current column as column 1.

(2) In the current row, judge whether the conditions are met from the I (1 < = I < = tempn) column (i.e. there are no two queens on the same row, column and slash). If yes, execute step (3). If not, add 1 to the current number of columns before judging whether the conditions are met.

(3) If column i of the current row meets the conditions, place a queen at the current position, add 1 to the current number of rows (tempT), and judge whether the current number of rows (tempT) is greater than the total number of rows (tempN). If greater, record a solution. Otherwise, execute step (2).

(4) A one-dimensional array solution is used to store the chessboard. The value of the ith element in the array represents the position of the queen in row i. This has the advantage of compressing the space scale of the problem to O(N).

The code implementation is as follows:

Determine whether to place

  • Determine whether it is on the same line

    Since only one queen is placed in a row, it is not necessary to judge whether two queens are in the same row.

  • Determine whether they are in the same column

    It is very simple to judge whether the queen of row J and row tempT are in the same column, that is, to judge whether tempSolution[j] is equal to tempSolution[tempT].

  • Judge whether it is on the same slash

    To judge whether the queen of row J and the queen of row tempT are on the same slash, only judge whether the number of rows of Queen of row J minus the number of rows of Queen of row tempT is equal to the number of columns of Queen of row J minus the number of columns of Queen of row tempT, that is, judge whether abs(tempT - j) is equal to abs(tempSolution[j] - tempSolution[tempT]). Since the slash has forward slash and backward slash, the absolute value of the result is taken.

/* Determine whether to place */
bool place(int* tempSolution, int tempT)
{
    for(int j = 1; j < tempT; ++j)
    {
        if((abs(tempT - j) == abs(tempSolution[j] - tempSolution[tempT]))/* Whether the queen position in line j is on the same slash as that in line tempT */ || (tempSolution[j] == tempSolution[tempT])/* Whether the queen position in row j is equal to the queen position in row tempT */)
        {
            return false;
        }
    }
    return true;
}

Backtracking

(1) In the current row, judge whether the conditions are met from the i (1 < = i < = tempn) column (that is, there are no two queens on the same row, column and slash). If yes, execute step (2). If not, add 1 to the current number of columns before judging whether the conditions are met.

(2) If column i of the current row meets the conditions, place a queen at the current position, add 1 to the current number of rows (tempT), and judge whether the current number of rows (tempT) is greater than the total number of rows (tempN). If greater, record a solution. Otherwise, execute step (1).

/* Backtracking */
void backTracking(int* tempSolution, int tempN, int tempT)
{
    if(tempT > tempN)
    {
        for(int i = 1; i <= tempN; ++i)
        {
            printf("% d",tempSolution[i]);
        }
        printf("\n");
    }else{
        for(int i = 1; i <= tempN; ++i) //Judge each column of row tempT
        {
            tempSolution[tempT] = i;
            if(place(tempSolution, tempT))
            {
                backTracking(tempSolution, tempN, tempT + 1);
            }
        }
    }
}

For example, the solution flow of Queen 4 is shown in the following figure:

4 queen problem solving

Full code

#include <stdio.h>
#include <malloc.h>
#include <math.h>

/* Determine whether to place */
bool place(int* tempSolution, int tempT)
{
    for(int j = 1; j < tempT; ++j)
    {
        if((abs(tempT - j) == abs(tempSolution[j] - tempSolution[tempT]))/* Whether the queen position in line j is on the same slash as that in line tempT */ || (tempSolution[j] == tempSolution[tempT])/* Whether the queen position in row j is equal to the queen position in row tempT */)
        {
            return false;
        }
    }
    return true;
}

/* Backtracking */
void backTracking(int* tempSolution, int tempN, int tempT)
{
    if(tempT > tempN)
    {
        for(int i = 1; i <= tempN; ++i)
        {
            printf("% d",tempSolution[i]);
        }
        printf("\n");
    }else{
        for(int i = 1; i <= tempN; ++i) //Judge each column of row tempT
        {
            tempSolution[tempT] = i;
            if(place(tempSolution, tempT))
            {
                backTracking(tempSolution, tempN, tempT + 1);
            }
        }
    }
}

/* N queens problem  */
void nQueen(int tempN)
{
    int* solution = (int*)malloc((tempN + 1) * sizeof(int));
    for(int i = 0; i <= tempN; ++i)
    {
        solution[i] = 0;
    }
    backTracking(solution, tempN, 1);
}

int main(){
	nQueen(4);
	return 0;
}

test result

2 4 1 3
3 1 4 2

Tags: C Algorithm data structure

Posted by aravind_mg on Mon, 30 May 2022 03:26:24 +0530