#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// ------- 可変設定 --------
#define SIZE 8         // グリッド全体のサイズ（例: 4, 6, 9）
#define BLOCK_H 2      // ブロックの縦のサイズ（例: 2）
#define BLOCK_W 4      // ブロックの横のサイズ（例: 3）
// -------------------------

int grid[SIZE][SIZE];

// ランダムな順番に並び替え
void shuffle(int *array, int size) {
    for (int i = size - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

// num を (row, col) に置いていいか判定
int isSafe(int row, int col, int num) {
    for (int x = 0; x < SIZE; x++) {
        if (grid[row][x] == num || grid[x][col] == num)
            return 0;
    }

    int startRow = row - row % BLOCK_H;
    int startCol = col - col % BLOCK_W;

    for (int i = 0; i < BLOCK_H; i++) {
        for (int j = 0; j < BLOCK_W; j++) {
            if (grid[startRow + i][startCol + j] == num)
                return 0;
        }
    }

    return 1;
}

// 再帰的に埋めていく
int fillGrid(int row, int col) {
    if (row == SIZE - 1 && col == SIZE)
        return 1;
    if (col == SIZE) {
        row++;
        col = 0;
    }

    if (grid[row][col] != 0)
        return fillGrid(row, col + 1);

    int nums[SIZE];
    for (int i = 0; i < SIZE; i++) nums[i] = i + 1;
    shuffle(nums, SIZE);

    for (int i = 0; i < SIZE; i++) {
        int num = nums[i];
        if (isSafe(row, col, num)) {
            grid[row][col] = num;
            if (fillGrid(row, col + 1))
                return 1;
            grid[row][col] = 0;
        }
    }

    return 0;
}

// 出力関数
void printGrid() {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%2d ", grid[i][j]);
        }
        printf("\n");
    }
}

int main() {
    srand(time(NULL));

    // 初期化
    for (int i = 0; i < SIZE; i++)
        for (int j = 0; j < SIZE; j++)
            grid[i][j] = 0;

    if (fillGrid(0, 0)) {
        printf("完成済みのナンプレ (%dx%d, %dx%dブロック):\n", SIZE, SIZE, BLOCK_H, BLOCK_W);
        printGrid();
    } else {
        printf("グリッドを生成できませんでした。\n");
    }

    return 0;
}