fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #define SIZE 9
  6.  
  7. int grid[SIZE][SIZE];
  8.  
  9. // シャッフル用
  10. void shuffle(int *array, int size) {
  11.     for (int i = size - 1; i > 0; i--) {
  12.         int j = rand() % (i + 1);
  13.         int tmp = array[i];
  14.         array[i] = array[j];
  15.         array[j] = tmp;
  16.     }
  17. }
  18.  
  19. // 指定のマスに値が置けるかどうかを判定
  20. int isSafe(int row, int col, int num) {
  21.     for (int x = 0; x < SIZE; x++) {
  22.         if (grid[row][x] == num || grid[x][col] == num)
  23.             return 0;
  24.     }
  25.  
  26.     int startRow = row - row % 3;
  27.     int startCol = col - col % 3;
  28.  
  29.     for (int i = 0; i < 3; i++) {
  30.         for (int j = 0; j < 3; j++) {
  31.             if (grid[startRow + i][startCol + j] == num)
  32.                 return 0;
  33.         }
  34.     }
  35.  
  36.     return 1;
  37. }
  38.  
  39. // 再帰的にナンプレを完成させる
  40. int fillGrid(int row, int col) {
  41.     if (row == SIZE - 1 && col == SIZE)
  42.         return 1;
  43.     if (col == SIZE) {
  44.         row++;
  45.         col = 0;
  46.     }
  47.  
  48.     if (grid[row][col] != 0)
  49.         return fillGrid(row, col + 1);
  50.  
  51.     int nums[SIZE];
  52.     for (int i = 0; i < SIZE; i++) nums[i] = i + 1;
  53.     shuffle(nums, SIZE);
  54.  
  55.     for (int i = 0; i < SIZE; i++) {
  56.         int num = nums[i];
  57.         if (isSafe(row, col, num)) {
  58.             grid[row][col] = num;
  59.             if (fillGrid(row, col + 1))
  60.                 return 1;
  61.             grid[row][col] = 0;
  62.         }
  63.     }
  64.  
  65.     return 0;
  66. }
  67.  
  68. // グリッドの表示
  69. void printGrid() {
  70.     for (int i = 0; i < SIZE; i++) {
  71.         for (int j = 0; j < SIZE; j++) {
  72.             printf("%d ", grid[i][j]);
  73.         }
  74.         printf("\n");
  75.     }
  76. }
  77.  
  78. int main() {
  79.     srand(time(NULL));
  80.  
  81.     // グリッド初期化
  82.     for (int i = 0; i < SIZE; i++)
  83.         for (int j = 0; j < SIZE; j++)
  84.             grid[i][j] = 0;
  85.  
  86.     if (fillGrid(0, 0)) {
  87.         printf("完成済みのナンプレ:\n");
  88.         printGrid();
  89.     } else {
  90.         printf("グリッドを生成できませんでした。\n");
  91.     }
  92.  
  93.     return 0;
  94. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
完成済みのナンプレ:
3 4 8 9 1 2 6 5 7 
5 6 7 8 3 4 1 9 2 
2 1 9 7 5 6 3 4 8 
6 7 5 3 8 1 4 2 9 
1 2 4 6 9 5 8 7 3 
9 8 3 2 4 7 5 6 1 
7 5 6 1 2 8 9 3 4 
8 3 2 4 6 9 7 1 5 
4 9 1 5 7 3 2 8 6
https://ideone.com/y5S0gm
language:
C (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!