悩んでいる人
C言語で数独（ナンプレ）の解き方を教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴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社で自分に合うスクールを見つけましょう．後悔はさせません！
数独（ナンプレ）
数独（ナンプレ）とは，3×3のグループ（ブロック）に区切られた 9×9の正方形の枠内に1〜9までの数字を入れるパズルゲームです．
基本的なルールは以下の3つです．
- 空いているマスに，1〜9のいずれかの数字を入れる．
- 縦・横の各列に，同じ数字が重複して入ってはいけない．
- 太線で囲まれた3×3のグループ（以降「ブロック」と呼ぶ）内に，同じ数字が重複して入ってはいけない．
数独の遊び方は以下の動画がわかりやすいです．
C言語で総当たり法による数独の解き方
C言語で総当たり法による数独の解き方は以下になります．
|
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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdbool.h> #define N 9 void print_grid(int grid[N][N]) { int i, j; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { printf("%d ", grid[i][j]); } printf("\n"); } } bool check_row(int grid[N][N], int row, int val) { int j; for (j = 0; j < N; j++) { if (val == grid[row][j]) { return false; } } return true; } bool check_col(int grid[N][N], int col, int val) { int i; for (i = 0; i < N; i++) { if (val == grid[i][col]) { return false; } } return true; } bool check_box(int grid[N][N], int row, int col, int val) { int i, j; int r, c; r = (row / 3) * 3 + 1; c = (col / 3) * 3 + 1; for (i = -1; i <= 1; i++) { for (j = -1; j <= 1; j++) { if (grid[r + i][c + j] == val) { return false; } } } return true; } void find_unassigned(int *i, int *j, int grid[N][N]) { int x, y; for (y = 0; y < N; y++) { for (x = 0; x < N; x++) { if (grid[y][x] == 0) { *i = y; *j = x; return; } } } *i = *j = -1; } bool solve_sudoku(int grid[N][N]) { int i, j, num; find_unassigned(&i, &j, grid); if (i == -1 && j == -1) { return true; } for (num = 1; num <= N; num++) { if (check_row(grid, i, num) && check_col(grid, j, num) && check_box(grid, i, j, num)) { grid[i][j] = num; if (solve_sudoku(grid)) { return true; } grid[i][j] = 0; } } return false; } int main(void) { int grid[N][N] = { {3, 6, 0, 0, 1, 9, 4, 7, 8}, {9, 7, 0, 5, 0, 4, 6, 0, 0}, {0, 0, 0, 6, 3, 0, 2, 5, 0}, {8, 0, 0, 0, 2, 0, 7, 0, 1}, {1, 9, 7, 0, 0, 6, 0, 0, 4}, {2, 0, 0, 0, 7, 0, 5, 0, 6}, {0, 2, 4, 1, 0, 0, 8, 0, 7}, {0, 0, 1, 0, 4, 0, 9, 6, 0}, {0, 0, 0, 0, 0, 8, 0, 4, 0} }; if (solve_sudoku(grid)) { print_grid(grid); } else { fprintf(stderr, "Error: this grid has no solution!\n"); } return 0; } |
実行結果は以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 |
$ gcc sudoku_brute_force.c $ a.out 3 6 5 2 1 9 4 7 8 9 7 2 5 8 4 6 1 3 4 1 8 6 3 7 2 5 9 8 5 6 4 2 3 7 9 1 1 9 7 8 5 6 3 2 4 2 4 3 9 7 1 5 8 6 6 2 4 1 9 5 8 3 7 7 8 1 3 4 2 9 6 5 5 3 9 7 6 8 1 4 2 |
C言語でバックトラック法による数独の解き方
C言語でバックトラック法による数独の解き方は以下になります．
|
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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdbool.h> #define N 9 void print_grid(int grid[N][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { printf("%d ", grid[i][j]); } printf("\n"); } } bool is_safe(int grid[N][N], int row, int col, int num) { int i, j, x, y; int start_row = row - row % 3; int start_col = col - col % 3; for (x = 0; x < N; x++) { if (grid[row][x] == num) { return false; } } for (y = 0; y < N; y++) { if (grid[y][col] == num) { return false; } } for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { if (grid[i + start_row][j + start_col] == num) { return false; } } } return true; } bool solve_sudoku(int grid[N][N], int row, int col) { int num; if (row == N - 1 && col == N) { return true; } if (col == N) { row++; col = 0; } if (grid[row][col] > 0) { return solve_sudoku(grid, row, col + 1); } for (num = 1; num <= N; num++) { if (is_safe(grid, row, col, num) == 1) { grid[row][col] = num; if (solve_sudoku(grid, row, col + 1) == 1) { return true; } } grid[row][col] = 0; } return false; } int main(void) { int grid[N][N] = { {3, 6, 0, 0, 1, 9, 4, 7, 8}, {9, 7, 0, 5, 0, 4, 6, 0, 0}, {0, 0, 0, 6, 3, 0, 2, 5, 0}, {8, 0, 0, 0, 2, 0, 7, 0, 1}, {1, 9, 7, 0, 0, 6, 0, 0, 4}, {2, 0, 0, 0, 7, 0, 5, 0, 6}, {0, 2, 4, 1, 0, 0, 8, 0, 7}, {0, 0, 1, 0, 4, 0, 9, 6, 0}, {0, 0, 0, 0, 0, 8, 0, 4, 0} }; if (solve_sudoku(grid, 0, 0)) { print_grid(grid); } else { fprintf(stderr, "Error: this grid has no solution!\n"); } return 0; } |
実行結果は以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 |
$ gcc sudoku_backtracking.c $ a.out 3 6 5 2 1 9 4 7 8 9 7 2 5 8 4 6 1 3 4 1 8 6 3 7 2 5 9 8 5 6 4 2 3 7 9 1 1 9 7 8 5 6 3 2 4 2 4 3 9 7 1 5 8 6 6 2 4 1 9 5 8 3 7 7 8 1 3 4 2 9 6 5 5 3 9 7 6 8 1 4 2 |
まとめ
C言語で数独（ナンプレ）の解き方を紹介しました．
具体的には，数独の総当たり法とバックトラック法のコードを解説しました．
数独の解き方の高速化を知りたいあなたはこちらからどうぞ．
数独の解き方の上級者版は以下の動画でわかります．高速化のヒントになるかもしれません．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
