Langage C 8 reine résolution de problèmes 3 modèles

Calculez le nombre de reines.

2020/07/07 postscript Ajout du résultat d'exécution du programme.

Les outils utilisés: (C) |"Environnement d'exécution en ligne" qui peut être programmé et exécuté avec un navigateur| paiza.IO

Comment résoudre ① Liste

#include <stdio.h>

/*Fonction qui renvoie une valeur absolue*/
int abs(int a)
{
    if (a < 0)
        return a * -1;
    else
        return a;
}

/*Vérifiez la verticale et la diagonale(Puisque l'axe horizontal est indiqué par la variable elle-même, l'axe horizontal ne se chevauche pas.) */
int check(int q1, int q2, int q3, int q4, int q5, int q6, int q7, int q8)
{

    if (
        /*Vérifier la verticale*/
        (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) &&

        /*Vérifier en diagonale*/
        (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

Comment résoudre ② ① est abstrait

#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

Post-scriptum 2020/06/11 @Fujitanozomu a commenté le code de N Queen. Veuillez consulter la section des commentaires. Merci beaucoup.

Comment résoudre ③ Méthode Backtrack

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

/*Ajouter d verticalement, horizontalement et en diagonale à partir de n'importe quel point du plateau*/
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;
    }

    /*Une image d'empilage de coussins sur un échiquier, traitement en trois dimensions*/
    for (col = 0; col < 8; col++)
    {
        if (board[row][col] == 0)
        {
            /* board[row][col]Placez la reine dans la position de*/
            queen_position[row] = col;
            /*Placez un coussin dans un endroit où vous ne pouvez pas l'utiliser verticalement, horizontalement et en diagonale.+1 */
            change_board(board, row, col, 1);
            /*Positionnez la reine sur la ligne suivante*/
            set_queen(queen_position, board, row + 1);
            /*Coussins empilés-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

Dans (1), il est devenu clair que l'hypothèse selon laquelle il y a des reines dans toutes les colonnes est importante pour considérer ce problème.

③ La fonction change_board est intuitive mais redondante.

J'ai pu remarquer à partir de ce problème que le tableau bidimensionnel effectue un processus tertiaire. Non seulement vrai et faux, mais en ajoutant 1, il est possible de réduire le nombre de cas et c'est intelligent.

Recommended Posts

Langage C 8 reine résolution de problèmes 3 modèles
Résolution du problème N Queen avec l'optimisation des combinaisons
File d'attente ALDS1_3_B langage C
[Algorithme de langage C] Endianness
[Algorithme de langage C] bloquer le mouvement
Intégration du langage machine en langage C
Recherche binaire ALDS1_4_B langage C
Tri de tas fait en langage C
AtCoder Beginner Contest # 002 Problème C
AtCoder Regular Contest # 002 Problème C
[Langage C] readdir () vs readdir_r ()
Recherche linéaire ALDS1_4_A en langage C
Résolution de 100 traitements linguistiques Knock 2020 (01. "Patatokukashi")