(cache)sudoku-cpp-practice/cli/src/main.cpp at main · wikinder/sudoku-cpp-practice · GitHub

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
/************************************************************
 * Sudoku CLI版
 *
 * このプログラムで学べること：
 *  - 2次元配列（9x9の数独盤）の扱い方
 *  - 再帰（バックトラック）による探索アルゴリズム
 *  - ランダムな数独盤の生成
 *  - 解が1つだけになるようにパズルを作る方法
 *  - C++での標準ライブラリの使い方（vector, array, random など）
 ************************************************************/

#include <array>     // std::array（固定長配列）
#include <vector>    // std::vector（可変長配列）
#include <random>    // 乱数生成（std::mt19937 など）
#include <chrono>    // 時刻を使って乱数の種を作る
#include <iostream>  // 標準入出力（std::cout, std::cin）
#include <algorithm> // std::shuffle など
#include <limits>    // std::numeric_limits（cin.ignore 用）

/************************************************************
 * Board 型
 * ----------------------------------------------------------
 *  - 数独の盤面を表す型。
 *  - 9行 × 9列の2次元配列。
 *  - int で各マスの数字を表す。
 *    0   → 空のマス（まだ数字が入っていない）
 *    1〜9 → 実際の数字
 ************************************************************/
using Board = std::array<std::array<int, 9>, 9>;

/************************************************************
 * is_valid()
 * ----------------------------------------------------------
 *  指定した位置 (row, col) に num を置いてよいかどうかを判定する。
 *
 *  チェックすることは3つ：
 *    1. 同じ「行」に同じ数字がないか
 *    2. 同じ「列」に同じ数字がないか
 *    3. 同じ 3x3 ブロックの中に同じ数字がないか
 *
 *  どれか1つでも同じ数字があれば「ダメ（false）」。
 *  すべて問題なければ「OK（true）」を返す。
 ************************************************************/
bool is_valid(const Board &board, int row, int col, int num) {
    // ---------- 1. 行チェック ----------
    // row 行の 0〜8 列を順番に見て、同じ数字がないか探す。
    for (int c = 0; c < 9; ++c) {
        if (board[row][c] == num) {
            // すでに同じ数字が行に存在する → ダメ
            return false;
        }
    }

    // ---------- 2. 列チェック ----------
    // col 列の 0〜8 行を順番に見て、同じ数字がないか探す。
    for (int r = 0; r < 9; ++r) {
        if (board[r][col] == num) {
            // すでに同じ数字が列に存在する → ダメ
            return false;
        }
    }

    // ---------- 3. 3×3 ブロックチェック ----------
    // (row, col) が属している 3×3 ブロックの左上のマスの座標を求める。
    // 例： row=5, col=7 の場合 → (row/3)=1, (col/3)=2 → (1*3, 2*3) = (3, 6)
    int box_r = (row / 3) * 3;
    int box_c = (col / 3) * 3;

    // ブロック内は 3行×3列 なので、0〜2の相対位置でチェックする。
    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < 3; ++c) {
            if (board[box_r + r][box_c + c] == num) {
                // 同じブロック内に同じ数字がある → ダメ
                return false;
            }
        }
    }

    // 行・列・ブロックのどこにも同じ数字が無かった → OK
    return true;
}

/************************************************************
 * find_empty()
 * ----------------------------------------------------------
 *  盤面の中から「まだ数字が入っていないマス（=0）」を探す。
 *
 *  探し方：
 *   - 行 0〜8
 *   - 列 0〜8
 *   を左上から順番に見ていく。
 *
 *  見つかったら：
 *   - 引数 row, col にその場所をセットして
 *   - true を返す
 *
 *  1つも見つからなかったら：
 *   - false を返す（＝盤面がすべて埋まっている）
 ************************************************************/
bool find_empty(const Board &board, int &row, int &col) {
    for (row = 0; row < 9; ++row) {     // 行を 0〜8 までループ
        for (col = 0; col < 9; ++col) { // 列を 0〜8 までループ
            if (board[row][col] == 0) {
                // 初めて見つけた空マス（0） → ここに次の数字を入れていく
                return true;
            }
        }
    }
    // どこにも 0 が無い → すべてのマスが埋まっている
    return false;
}

/************************************************************
 * solve()
 * ----------------------------------------------------------
 *  再帰的バックトラックで数独を解く関数。
 *
 *  アルゴリズムの流れ：
 *   1. 空きマスを1つ探す（find_empty）
 *   2. 見つからなかった → すべて埋まっている → クリア → true
 *   3. 1〜9 の数字を順番に試す
 *   4. その数字を置いてもよさそう（is_valid）なら
 *        - 実際に数字を置く
 *        - 再帰的に solve() を呼ぶ
 *        - もしそこで true が返ってきたら、そのまま true を返す
 *        - ダメだったら（falseが返ったら）数字を元に戻して次の数字へ
 *   5. 1〜9 すべて試してダメなら false を返して一段上に戻る
 ************************************************************/
bool solve(Board &board) {
    int row, col;

    // まず「まだ空いているマス」を探す。
    // 空きマスが見つからなければ、すべて埋まっている = 完成。
    if (!find_empty(board, row, col)) {
        // 空きがない → 解けている状態 → true を返して再帰を終了
        return true;
    }

    // 見つかった空きマス (row, col) に、1〜9 の数字を順番に試しで入れていく。
    for (int num = 1; num <= 9; ++num) {
        // その数字がルール上置いてよいかどうかチェック
        if (is_valid(board, row, col, num)) {
            // 仮にこのマスに num を置いてみる（試し置き）
            board[row][col] = num;

            // その状態で残りのマスも解けるかどうか、再帰的に solve() に任せる。
            if (solve(board)) {
                // どこかの深さで「全部解けた！」となったら、
                // そのまま true を返していく。
                return true;
            }

            // ここまで来る＝num を置いても解けなかった → もとに戻す
            board[row][col] = 0;
        }
    }

    // 1〜9 のどの数字を試してもダメだった → この盤面では解けない
    // 呼び出し元に「失敗」として false を返す。
    return false;
}

/************************************************************
 * solve_count()
 * ----------------------------------------------------------
 *  解の数を数えるための関数。
 *
 *  普通の solve() は「1個解が見つかったらそこで終了」だが、
 *  solve_count() は「何通り解があるか」を数える。
 *
 *  ただし、全部数えると時間がかかるので、
 *   - limit に達したらそれ以上は調べずに打ち切る。
 *
 *  ここでは「解が1通りだけかどうか」を判定したいので、
 *   - limit = 2 で呼び出すことが多い。
 *   → count が 2 になった時点で「複数解あり」と判断できる。
 ************************************************************/
void solve_count(Board &board, int &count, int limit = 2) {
    // すでに上限まで見つけていたら、これ以上探索しない。
    if (count >= limit) return;

    int row, col;
    if (!find_empty(board, row, col)) {
        // 空きマスがない → 1つ解を発見したということ
        ++count;
        return;
    }

    // 1〜9 の数字を試しながら、解の数を数えていく
    for (int num = 1; num <= 9; ++num) {
        if (is_valid(board, row, col, num)) {
            board[row][col] = num;
            solve_count(board, count, limit);
            board[row][col] = 0;

            // 上限に達したらこれ以上深掘りしない
            if (count >= limit) return;
        }
    }
}

/************************************************************
 * print_board()
 * ----------------------------------------------------------
 *  盤面をきれいにコンソール表示するための関数。
 *
 *  表示のルール：
 *   - 3列ごとに縦線（|）を入れて見やすくする
 *   - 3行ごとに横線（------）を入れて 3x3 ブロックの区切りを見せる
 *   - 0（空マス）は '.' で表示
 *   - 1〜9 はそのまま数字で表示
 ************************************************************/
void print_board(const Board &board) {
    std::cout << "-------------------------" << std::endl;

    for (int r = 0; r < 9; ++r) {
        for (int c = 0; c < 9; ++c) {
            // 3列ごとに区切り線を入れる（ブロック境界）
            if (c % 3 == 0) {
                std::cout << "| ";
            }

            if (board[r][c] == 0) {
                // まだ数字が入っていないマスは '.' で表示
                std::cout << ". ";
            } else {
                // 数字が入っているマスはその数字を表示
                std::cout << board[r][c] << " ";
            }
        }

        // 行の終わりにも閉じる '|' を入れる
        std::cout << "|" << std::endl;

        // 3行ごとに横線を入れて 3x3 ブロックを視覚的に区切る
        if (r % 3 == 2) {
            std::cout << "-------------------------" << std::endl;
        }
    }
}

/************************************************************
 * rng()
 * ----------------------------------------------------------
 *  乱数生成器（std::mt19937）を1つだけ作って使い回す関数。
 *
 *  static 変数として mt を定義することで、
 *  プログラム全体で同じ乱数エンジンを共有する。
 *
 *  シード（初期値）には「現在時刻からの経過時間」を使うことで、
 *  実行するたびに異なる乱数の流れになる。
 ************************************************************/
std::mt19937 &rng() {
    // high_resolution_clock::now() で「今の時刻」を取り出し、
    // time_since_epoch().count() で「開始（epoch）からの経過時間」を整数値で取得。
    static std::mt19937 mt(
        static_cast<unsigned int>(
            std::chrono::high_resolution_clock::now()
                .time_since_epoch().count()
        )
    );
    // static なので、最初に呼ばれたときにだけ初期化され、
    // 2回目以降は同じ mt がそのまま使われる。
    return mt;
}

/************************************************************
 * fill_board()
 * ----------------------------------------------------------
 *  完成済みの数独盤（すべてのマスが埋まった状態）を、
 *  ランダムに生成する関数。
 *
 *  やっていることは solve() とほぼ同じだが、
 *   - 1〜9 を決まった順番ではなく、ランダムな順に試す
 *  というところがポイント。
 *  これによって毎回違う完成盤が生成される。
 ************************************************************/
bool fill_board(Board &board) {
    int row, col;
    if (!find_empty(board, row, col)) {
        // もう空きマスがない → 完成
        return true;
    }

    // 1〜9 の数字をベクターに詰める
    std::vector<int> nums(9);
    for (int i = 0; i < 9; ++i) {
        nums[i] = i + 1;
    }

    // 数字の順番をランダムに並べ替える
    std::shuffle(nums.begin(), nums.end(), rng());

 *  やっていること：
 *   - メニュー表示
 *   - 「新しいパズルを生成」か「終了」を選んでもらう
 *   - パズルと解答を順番に表示する
 ************************************************************/
void game_loop() {
    while (true) {
        std::cout << "\n==== Sudoku C++ ====\n";
        std::cout << "1) Generate new puzzle\n";
        std::cout << "2) Exit\n";
        std::cout << "Choice: ";

        int choice;
        if (!(std::cin >> choice)) {
            // 数字以外が入力された場合などに備えた簡単なエラー処理
            std::cout << "Input error. Exiting.\n";
            return;
        }

        if (choice == 2) {
            // ユーザーが 2 を選んだ → 終了
            std::cout << "Bye.\n";
            return;
        } else if (choice == 1) {
            // 新しいパズルを生成するモード
            try {
                // 1. パズル生成
                Board puzzle = generate_puzzle();

                std::cout << "\n[Puzzle]\n";
                print_board(puzzle);

                // 2. Enter キー待ち → 解答表示
                wait_enter();

                // 3. 解答盤を求める（puzzle から解を探す）
                Board solution = puzzle;
                if (solve(solution)) {
                    std::cout << "\n[Solution]\n";
                    print_board(solution);
                } else {
                    // ここに来ることはほぼ無いが、万が一 solver がバグったとき用
                    std::cout << "No solution found (bug?).\n";
                }

            } catch (const std::exception &ex) {
                // 生成中に例外（エラー）が飛んできたときの処理
                std::cout << "Error: " << ex.what() << "\n";
            }
        } else {
            // 1 と 2 以外が入力されたときのフォロー
            std::cout << "Please choose 1 or 2.\n";
        }
    }
}

/************************************************************
 * main()
 * ----------------------------------------------------------
 *  プログラムのエントリーポイント（入り口）。
 *  try-catch をつけておくことで、
 *  予期せぬ例外が起きたときもメッセージを出せるようにしている。
 ************************************************************/
int main() {
    try {
        // 実際の処理は game_loop() に任せる
        game_loop();
    } catch (const std::exception &ex) {
        // 予期しない例外が発生したときの最終的な保険
        std::cerr << "Fatal error: " << ex.what() << std::endl;
        return 1;
    }
    return 0;
}