[GO] C Sprache 8 Königin Problem lösen 3 Muster

8 Berechnen Sie die Anzahl der Königinnen.

Nachtrag 2020/07/07 Das Ausführungsergebnis des Programms wurde hinzugefügt.

Benutztes Werkzeug: (C) |"Online-Ausführungsumgebung", die mit einem Browser programmiert und ausgeführt werden kann| paiza.IO

So lösen Sie ① Liste

#include <stdio.h>

/*Funktion, die einen absoluten Wert zurückgibt*/
int abs(int a)
{
    if (a < 0)
        return a * -1;
    else
        return a;
}

/*Überprüfen Sie vertikal und diagonal(Da die horizontale Achse durch die Variable selbst angezeigt wird, überlappt sich die horizontale Achse nicht.) */
int check(int q1, int q2, int q3, int q4, int q5, int q6, int q7, int q8)
{

    if (
        /*Vertikal prüfen*/
        (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) &&

        /*Diagonal prüfen*/
        (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

Wie man ② ① löst, ist abstrahiert

#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

Nachtrag 2020/06/11 @Fujitanozomu kommentierte den Code für N Queen. Bitte beachten Sie den Kommentarbereich. Vielen Dank.

So lösen Sie ③ Backtrack-Methode

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

/*Fügen Sie d vertikal, horizontal und diagonal von jedem Punkt auf der Platine hinzu*/
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;
    }

    /*Ein Bild des Stapelns von Kissen auf einem Schachbrett, dreidimensionale Verarbeitung*/
    for (col = 0; col < 8; col++)
    {
        if (board[row][col] == 0)
        {
            /* board[row][col]Platziere die Königin in der Position von*/
            queen_position[row] = col;
            /*Platzieren Sie ein Kissen an einem Ort, an dem Sie es nicht vertikal, horizontal und diagonal verwenden können.+1 */
            change_board(board, row, col, 1);
            /*Positioniere die Königin in der nächsten Zeile*/
            set_queen(queen_position, board, row + 1);
            /*Gestapelte Kissen-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

Impressionen

In (1) wurde klar, dass die Annahme, dass es in allen Spalten Königinnen gibt, wichtig ist, um dieses Problem zu betrachten.

③ Die Funktion change_board ist intuitiv, aber redundant.

Ich konnte anhand dieses Problems feststellen, dass das zweidimensionale Array einen tertiären Prozess ausführt. Nicht nur wahr und falsch, sondern durch Hinzufügen von 1 ist es möglich, die Anzahl der Fälle zu reduzieren, und es ist klug.

Recommended Posts

C Sprache 8 Königin Problem lösen 3 Muster
Lösen des N Queen-Problems mit Kombinationsoptimierung
C-Sprache ALDS1_3_B Warteschlange
[C-Sprachalgorithmus] Endianness
[C-Sprachalgorithmus] Blockbewegung
Einbettung der Maschinensprache in die Sprache C.
C-Sprache ALDS1_4_B Binäre Suche
Heap-Sortierung in C-Sprache
AtCoder Beginner Contest # 002 C Problem
AtCoder Regular Contest # 002 C Problem
[C Sprache] readdir () vs readdir_r ()
C-Sprache ALDS1_4_A Lineare Suche
Lösen von 100 Sprachverarbeitungsklopfen 2020 (01. "Patatokukashi")