C言語でNクイーン問題の解き方を教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
Nクイーン問題の解き方
Nクイーン問題とは，チェスのエイトクイーン問題を一般化したものです．
エイトクイーンとは，チェスの盤とコマを使用したパズルの名称です，チェスの盤上に8個のクイーンを他のクイーンに取られるような場所に配置しない解法を見つけることです．
クイーンの動きは，上下左右斜めの8方向に遮る物がない限り進めます．
この性質を考慮してクイーンを配置します．
Nクイーン問題を総当たり法で解くコード
Nクイーン問題を総当たり法で解くコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define N 8 void print_queen(int row[], int *solutions) { int i, j; printf("\n[Solution %d]\n", *solutions); for (i = 0; i < N; i++) { for (j = 0; j < N; j++) if (row[i] == j) { printf(" Q"); } else { printf(" ."); } printf("\n"); } } bool check(int queen_position, int row[]) { int i, j; for (i = 1; i <= queen_position; i++) { for (j = 0; j < i; j++) { if (row[i] == row[j] || abs(row[i] - row[j]) == i - j) { return false; } } } return true; } void brute_force(int n, int queen_position, int row[], int *solutions) { for (row[n] = 0; row[n] <= queen_position; row[n]++) { if (n == queen_position) { if (check(queen_position, row)) { (*solutions)++; print_queen(row, solutions); } } else { brute_force(n + 1, queen_position, row, solutions); } } } int main(void) { int row[N]; int solutions = 0; brute_force(0, N - 1, row, &solutions); printf("solutions = %d\n", solutions); return 0; } |
実行結果は以下になります．
エイトクイーン（クイーンが8個）の場合は，92の解法があることがわかります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
$ gcc n_queens_brute_force.c $ a.out [Solution 1] Q . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . Q . . . . . . . . . . . Q . . Q . . . . . . . . . Q . . . . ... [Solution 92] . . . . . . . Q . . . Q . . . . Q . . . . . . . . . Q . . . . . . . . . . Q . . . Q . . . . . . . . . . . . Q . . . . . Q . . . solutions = 92 |
Nクイーン問題をバックトラック法で解くコード
Nクイーン問題をバックトラック法で解くコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define N 8 void print_queen(int row[], int *solutions) { int i, j; printf("\n[Solution %d]\n", *solutions); for (i = 0; i < N; i++) { for (j = 0; j < N; j++) if (row[i] == j) { printf(" Q"); } else { printf(" ."); } printf("\n"); } } bool check(int n, int row[]) { int i; for (i = 0; i < n; i++) { if (row[i] == row[n] || abs(row[i] - row[n]) == n - i) { return false; } } return true; } void backtracking(int n, int queen_position, int row[], int *solutions) { for (row[n] = 0; row[n] <= queen_position; row[n]++) { if (check(n, row)) { if (n == queen_position) { (*solutions)++; print_queen(row, solutions); } else { backtracking(n + 1, queen_position, row, solutions); } } } } int main(void) { int row[N]; int solutions = 0; backtracking(0, N - 1, row, &solutions); printf("solutions = %d\n", solutions); return 0; } |
実行結果は以下になります．
結果は総当たり法と同様ですが，バックトラック法の方が処理時間は短いです．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
$ gcc n_queens_backtracking.c $ a.out [Solution 1] Q . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . Q . . . . . . . . . . . Q . . Q . . . . . . . . . Q . . . . ... [Solution 92] . . . . . . . Q . . . Q . . . . Q . . . . . . . . . Q . . . . . . . . . . Q . . . Q . . . . . . . . . . . . Q . . . . . Q . . . solutions = 92 |
まとめ
C言語でNクイーン問題の解き方を紹介しました．
具体的には，総当たり法とバックトラック法を解説しました．
Nクイーン問題の解き方の高速化を知りたいあなたは，以下の記事を読みましょう！
- C言語：Ｎクイーン問題（解の個数を求める）
- C++言語：N-Queens 問題
- C++言語：Nクイーン【前編】，Nクイーン【後編】
- Python言語：N Queens Problem
- Python/Java/C/Lua言語，Bash：ステップバイステップでＮ−クイーン問題を最適化
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
