C言語 8クイーン問題 解き方3パターン

8クイーンが成り立つ数を計算する。

2020/07/07追記
プログラムの実行結果を追記しました。

使ったツール: (C) | ブラウザでプログラミング・実行ができる「オンライン実行環境」| paiza.IO

解き方① 列挙する

#include <stdio.h>

/* 絶対値を返す関数 */
int abs(int a)
{
    if (a < 0)
        return a * -1;
    else
        return a;
}

/* 縦と斜めをチェックする(横軸は変数自体が示しているため横軸は重複することがない) */
int check(int q1, int q2, int q3, int q4, int q5, int q6, int q7, int q8)
{

    if (
        /* 縦をチェック */
        (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) &&

        /* 斜めをチェック */
        (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

解き方② ①を抽象化

#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 追記
Nクイーン対応のコードは@fujitanozomu さんがコメントしてくださいました。
コメント欄を御覧ください。
ありがとうございます。

解き方③ バックトラック法

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

/* 盤上の任意の点から縦横斜めにdを加える */
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;
    }

    /* チェスの盤上に座布団を重ねていくようなイメージ、三次元的な処理 */
    for (col = 0; col < 8; col++)
    {
        if (board[row][col] == 0)
        {
            /* board[row][col]の位置にクイーンを配置 */
            queen_position[row] = col;
            /* 縦横斜めを使用禁止にするためおけない場所に座布団を+1 */
            change_board(board, row, col, 1);
            /* 次の行のクイーンの位置を決める */
            set_queen(queen_position, board, row + 1);
            /* 重ねた座布団を-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

所感

①ですべての列にクイーンが存在するという前提がこの問題を考える上で重要だということがよくわかった。

③のchange_board関数、直感的にわかりやすいけど冗長。

二次元配列は三次的な処理をしていることにこの問題で気づくことができた。
true,falseだけじゃなくて、1を足していくことで、場合分けを減らすことができていてスマート。