C language 8 queens problem solving 3 patterns

Calculate the number of 8 queens.

2020/07/07 postscript The execution result of the program was added.

Tools used: (C) |"Online execution environment" that can be programmed and executed with a browser| paiza.IO

How to solve ① List

#include <stdio.h>

/*Function that returns an absolute value*/
int abs(int a)
{
    if (a < 0)
        return a * -1;
    else
        return a;
}

/*Check vertical and diagonal(The horizontal axis is indicated by the variable itself, so the horizontal axis does not overlap.) */
int check(int q1, int q2, int q3, int q4, int q5, int q6, int q7, int q8)
{

    if (
        /*Check vertical*/
        (q1 != q2) &&
        (q1 != q3) &&
        (q1 != q4) &&
        (q1 != q5) &&
        (q1 != q6) &&
        (q1 != q7) &&
        (q1 != q8) &&

        (q2 != q3) &&
        (q2 != q4) &&
        (q2 != q5) &&
        (q2 != q6) &&
        (q2 != q7) &&
        (q2 != q8) &&

        (q3 != q4) &&
        (q3 != q5) &&
        (q3 != q6) &&
        (q3 != q7) &&
        (q3 != q8) &&

        (q4 != q5) &&
        (q4 != q6) &&
        (q4 != q7) &&
        (q4 != q8) &&

        (q5 != q6) &&
        (q5 != q7) &&
        (q5 != q8) &&

        (q6 != q7) &&
        (q6 != q8) &&

        (q7 != q8) &&

        /*Check diagonally*/
        (abs(q1 - q2) != 1) &&
        (abs(q2 - q3) != 1) &&
        (abs(q3 - q4) != 1) &&
        (abs(q4 - q5) != 1) &&
        (abs(q5 - q6) != 1) &&
        (abs(q6 - q7) != 1) &&
        (abs(q7 - q8) != 1) &&

        (abs(q1 - q3) != 2) &&
        (abs(q2 - q4) != 2) &&
        (abs(q3 - q5) != 2) &&
        (abs(q4 - q6) != 2) &&
        (abs(q5 - q7) != 2) &&
        (abs(q6 - q8) != 2) &&

        (abs(q1 - q4) != 3) &&
        (abs(q2 - q5) != 3) &&
        (abs(q3 - q6) != 3) &&
        (abs(q4 - q7) != 3) &&
        (abs(q5 - q8) != 3) &&

        (abs(q1 - q5) != 4) &&
        (abs(q2 - q6) != 4) &&
        (abs(q3 - q7) != 4) &&
        (abs(q4 - q8) != 4) &&

        (abs(q1 - q6) != 5) &&
        (abs(q2 - q7) != 5) &&
        (abs(q3 - q8) != 5) &&

        (abs(q1 - q7) != 6) &&
        (abs(q2 - q8) != 6) &&
        (abs(q1 - q8) != 7))
    {
        return 1;
    }
    return 0;
}

int main(void)
{
    int q1, q2, q3, q4, q5, q6, q7, q8;
    int count = 0;

    for (q1 = 0; q1 < 8; q1++)
        for (q2 = 0; q2 < 8; q2++)
            for (q3 = 0; q3 < 8; q3++)
                for (q4 = 0; q4 < 8; q4++)
                    for (q5 = 0; q5 < 8; q5++)
                        for (q6 = 0; q6 < 8; q6++)
                            for (q7 = 0; q7 < 8; q7++)
                                for (q8 = 0; q8 < 8; q8++)
                                    if (check(q1, q2, q3, q4, q5, q6, q7, q8))
                                        count++;

    printf("%d\n", count);
    return 0;
}

Build time: 0.08 Build exit code: 0 Build result: success Exit code: 0 Time: 0.14 Memory: 2112000 Result: success

How to solve ② ① is abstracted

#include <stdio.h>

int count;

int abs(int a)
{
    if (a < 0)
        return a * -1;
    else
        return a;
}

int check(int queen_position[8])
{
    int i;
    int j;

    i = 0;
    while (i < 8 - 1)
    {
        j = i + 1;
        while (j < 8)
        {
            if (queen_position[i] == queen_position[j] || abs(queen_position[i] - queen_position[j]) == j - i)
            {
                return 0;
            }
            j++;
        }
        i++;
    }
    return 1;
}

void set_queen(int queen_position[8], int queen_count)
{
    if (queen_count == 8)
    {
        if (check(queen_position))
        {
            count++;
        }
        return;
    }

    for (int j = 0; j < 8; j++)
    {
        queen_position[queen_count] = j;
        set_queen(queen_position, queen_count + 1);
    }
}

int main(void)
{
    int queen_position[8];

    set_queen(queen_position, 0);
    printf("%d\n", count);
    return 0;
}

Build time: 0.08 Build exit code: 0 Build result: success Exit code: 0 Time: 0.08 Memory: 2120000 Result: success

2020/06/11 postscript @Fujitanozomu commented on the code for N Queens. Please see the comment section. Thank you very much.

How to solve ③ Backtrack method

#include <stdio.h>

int count;

void init_board(int board[8][8])
{
    int row;
    int col;

    row = 0;
    while (row < 8)
    {
        col = 0;
        while (col < 8)
        {
            board[row][col] = 0;
            col++;
        }
        row++;
    }
}

/*Add d vertically, horizontally and diagonally from any point on the board*/
void change_board(int board[8][8], int row, int col, int d)
{
    int i;
    int j;

    i = 0;

    while (i < 8)
    {
        board[row][i] += d;
        board[i][col] += d;
        i++;
    }

    i = row;
    j = col;
    while (i < 8 && j < 8)
    {
        board[i][j] += d;
        i++;
        j++;
    }

    i = row;
    j = col;
    while (i >= 0 && j >= 0)
    {
        board[i][j] += d;
        i--;
        j--;
    }

    i = row;
    j = col;
    while (i < 8 && j >= 0)
    {
        board[i][j] += d;
        i++;
        j--;
    }

    i = row;
    j = col;
    while (i >= 0 && j < 8)
    {
        board[i][j] += d;
        i--;
        j++;
    }
}

void set_queen(int queen_position[8], int board[8][8], int row)
{
    int col;

    if (row == 8)
    {
        count++;
        return;
    }

    /*An image of stacking cushions on a chess board, three-dimensional processing*/
    for (col = 0; col < 8; col++)
    {
        if (board[row][col] == 0)
        {
            /* board[row][col]Place the queen in the position of*/
            queen_position[row] = col;
            /*Place a cushion in a place where you cannot use it vertically, horizontally and diagonally.+1 */
            change_board(board, row, col, 1);
            /*Position the queen on the next line*/
            set_queen(queen_position, board, row + 1);
            /*Stacked cushions-1 */
            change_board(board, row, col, -1);
        }
    }
}

int main(void)
{
    int queen_position[8];
    int board[8][8];
    init_board(board);
    set_queen(queen_position, board, 0);

    printf("%d\n", count);

    return 0;
}

Build time: 0.08 Build exit code: 0 Build result: success Exit code: 0 Time: 0.00 Memory: 2104000 Result: success

Impressions

In (1), it became clear that the premise that there are queens in all columns is important in considering this problem.

③ change_board function is intuitive but redundant.

I was able to notice from this problem that the two-dimensional array is doing a tertiary process. Not only true and false, but by adding 1 it is possible to reduce the number of cases and it is smart.

Recommended Posts

C language 8 queens problem solving 3 patterns
Solving the N Queens problem with combinatorial optimization
C language ALDS1_3_B Queue
[C language algorithm] Endianness
[C language algorithm] Block movement
Machine language embedding in C language
C language ALDS1_4_B Binary Search
Heapsort made in C language
ABC163 C problem with python3
AtCoder Beginner Contest # 002 C Problem
AtCoder Regular Contest # 002 C Problem
[C language] readdir () vs readdir_r ()
C language ALDS1_4_A Linear Search
Solving 100 Language Processing Knock 2020 (01. "Patatokukashi")
ABC188 C problem with python3
ABC187 C problem with python