【C言語】数独（ナンプレ）の解き方【総当たり法，バックトラック法】

悩んでいる人

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社で自分に合うスクールを見つけましょう．後悔はさせません！

: 元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社

こういった悩みにお答えします．こういった私が解説していきます．私が大学の授業で初めてC言語を勉強した時は全然できませんでしたが，先生やTA，友人に相談しながら一生懸命C言語を勉強してできるようにな ...

続きを見る

数独（ナンプレ）

数独（ナンプレ）とは，3×3のグループ（ブロック）に区切られた 9×9の正方形の枠内に1〜9までの数字を入れるパズルゲームです．

基本的なルールは以下の3つです．

空いているマスに，1〜9のいずれかの数字を入れる．
縦・横の各列に，同じ数字が重複して入ってはいけない．
太線で囲まれた3×3のグループ（以降「ブロック」と呼ぶ）内に，同じ数字が重複して入ってはいけない．

数独の遊び方は以下の動画がわかりやすいです．

C言語で総当たり法による数独の解き方

C言語で総当たり法による数独の解き方は以下になります．

/*
 * 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;
}

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;

}

実行結果は以下になります．

$ 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

$ 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言語でバックトラック法による数独の解き方は以下になります．

/*
 * 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;
}

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;

}

実行結果は以下になります．

$ 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

$ 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++言語】数独の高速化

数独の解き方の上級者版は以下の動画でわかります．高速化のヒントになるかもしれません．

C言語を独学で習得することは難しいです．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

: 元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社

こういった悩みにお答えします．こういった私が解説していきます．私が大学の授業で初めてC言語を勉強した時は全然できませんでしたが，先生やTA，友人に相談しながら一生懸命C言語を勉強してできるようにな ...

続きを見る