Board logo

標題: 資料結構 505 迷你數獨 [打印本頁]
作者: may    時間: 4 天前 22:57     標題: 資料結構 505 迷你數獨

資料結構 505 迷你數獨
1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。

2. 設計說明：
(1)迷你數獨遊戲由 4 個 2×2 的 4宮格組成，共 16 個格子，規則如下：

每一列（Row）、每一欄（Column）的數字均包含 1~4，不能缺少且不能重複。
每一宮（2×2 的4宮格）的數字均包含 1~4，不能缺少且不能重複。
(2) 迷你數獨的 16 個格子中，已提供 8 個正確數字，另外 8 個格子以「0」填入，表示需要推測的數字。至少有 2 列（或欄）的格子，只有一個「0」；其餘會有兩個以上的「0」。

(3) 請寫一個程式，將 8 個格子中的「0」，代換成正確數字，以滿足迷你數獨規則。

提示：請使用「貪心演算法（Greedy Algorithm）」。

3. 輸入輸出：
輸入說明
第 1 列：4 個 0~4 數字，中間以一個半形空白間隔。
第 2 列：4 個 0~4 數字，中間以一個半形空白間隔。
第 3 列：4 個 0~4 數字，中間以一個半形空白間隔。
第 4 列：4 個 0~4 數字，中間以一個半形空白間隔。

輸出說明
第 1 列：4 個 1~4 數字，中間以一個半形空白間隔。
第 2 列：4 個 1~4 數字，中間以一個半形空白間隔。
第 3 列：4 個 1~4 數字，中間以一個半形空白間隔。
第 4 列：4 個 1~4 數字，中間以一個半形空白間隔。

範例輸入1
0 0 0 0
0 2 3 1
0 3 2 4
2 0 0 3
範例輸出1
3 1 4 2
4 2 3 1
1 3 2 4
2 4 1 3
範例輸入2
2 0 0 3
3 0 2 1
0 2 3 0
0 0 0 2
範例輸出2
2 1 4 3
3 4 2 1
1 2 3 4
4 3 1 2
作者: may    時間: 4 天前 23:08

回復 1# may
  1. #include <bits/stdc++.h>
  2. //#include <iostream>
  3. //#include <vector>
  4. //#include <set>
  5. //#include <algorithm>

  7. using namespace std;

  9. const int N = 4; // 迷你數獨 4x4
  10. vector<vector<int>> grid(N, vector<int>(N));

  12. // 獲取某個 (r, c) 格子的可能數字
  13. set<int> get_candidates(int r, int c) {
  14.     set<int> candidates = {1, 2, 3, 4};
  15.    
  16.     // 移除同列數字
  17.     for (int i = 0; i < N; i++) {
  18.         candidates.erase(grid[r][i]);
  19.     }
  20.    
  21.     // 移除同欄數字
  22.     for (int i = 0; i < N; i++) {
  23.         candidates.erase(grid[i][c]);
  24.     }
  25.    
  26.     // 移除同 2x2 宮格內的數字
  27.     int sr = (r / 2) * 2, sc = (c / 2) * 2; // 計算所屬 2x2 宮格左上角座標
  28.     for (int i = 0; i < 2; i++) {
  29.         for (int j = 0; j < 2; j++) {
  30.             candidates.erase(grid[sr + i][sc + j]);
  31.         }
  32.     }
  33.    
  34.     return candidates;
  35. }

  37. // 使用貪心演算法填補 0
  38. bool solve() {
  39.     vector<pair<int, int>> zeros;
  40.    
  41.     // 找出所有 0 的位置
  42.     for (int r = 0; r < N; r++) {
  43.         for (int c = 0; c < N; c++) {
  44.             if (grid[r][c] == 0) {
  45.                 zeros.emplace_back(r, c);
  46.             }
  47.         }
  48.     }
  49.    
  50.     // 貪心策略：按「候選數字數量」排序（從少到多）
  51.     sort(zeros.begin(), zeros.end(), [](pair<int, int> a, pair<int, int> b) {
  52.         return get_candidates(a.first, a.second).size() < get_candidates(b.first, b.second).size();
  53.     });
  54.    
  55.     // 依序填入最適合的數字
  56.     for (auto [r, c] : zeros) {
  57.         set<int> candidates = get_candidates(r, c);
  58.         if (candidates.empty()) return false; // 無法填寫則返回失敗
  59.         grid[r][c] = *candidates.begin(); // 選擇集合中的最小數字
  60.     }
  61.     return true;
  62. }

  64. int main() {
  65.     // 讀取輸入
  66.     for (int i = 0; i < N; i++) {
  67.         for (int j = 0; j < N; j++) {
  68.             cin >> grid[i][j];
  69.         }
  70.     }
  71.    
  72.     // 嘗試解決迷你數獨
  73.     if (solve()) {
  74.         // 輸出結果
  75.         for (int i = 0; i < N; i++) {
  76.             for (int j = 0; j < N; j++) {
  77.                 if (j > 0) cout << " ";
  78.                 cout << grid[i][j];
  79.             }
  80.             cout << endl;
  81.         }
  82.     } else {
  83.         cout << "No solution found!" << endl;
  84.     }
  85.     return 0;
  86. }
複製代碼
----------------------------------------------------
這是一個「迷你數獨」解題問題，我們需要使用**貪心演算法（Greedy Algorithm）**來填補 8 個 0，確保每一列、每一欄以及每個 2×2 宮格內的數字皆為 1~4 且無重複。

解題思路
讀取輸入並存入 4×4 的矩陣

預處理：建立「可填入數字的候選集」

針對每個 0，列舉它所在的「列、欄、2×2 宮格」內已有的數字，從 {1,2,3,4} 中移除這些數字，得到候選數字集。

貪心策略：優先填寫可能選擇最少的格子

依照「候選數字數量最少的 0」開始填入，減少未來選擇的可能性，使得解法更容易成功。

填補數獨並輸出結果
---------------------------------------------------------
程式說明
get_candidates(int r, int c)

回傳 (r, c) 位置的可能數字。

先將 {1, 2, 3, 4} 作為候選數字，然後刪除：

該列已有的數字。

該欄已有的數字。

該 2x2 宮格內已有的數字。

solve()

找出所有 0 的位置。

按照「該格的候選數字數量」進行排序（貪心策略）。

依序填入「可能數字最少」的格子，優先解決最受限制的格子。

main()

讀取 4x4 輸入矩陣。

嘗試填寫 0，成功則輸出結果，失敗則回報「無解」。

時間複雜度分析
get_candidates() 需遍歷 O(4) 個數字，總計 O(12) ≈ O(1)。

solve() 會對 0 進行排序，最差情況 O(8 log 8) ≈ O(24)，之後依序填入，最壞情況 O(8 × 12) ≈ O(96)。

總體複雜度近乎 O(1)，運行速度快，適用於迷你數獨。
-------------------------------------------------------------
測資:
測資 00
輸入：
0 0 0 0
0 2 3 1
0 3 2 4
2 0 0 3
輸出：
3 1 4 2
4 2 3 1
1 3 2 4
2 4 1 3
測資 01
輸入：
2 0 0 3
3 0 2 1
0 2 3 0
0 0 0 2
輸出：
2 1 4 3
3 4 2 1
1 2 3 4
4 3 1 2
測資02
輸入：
0 3 0 0
0 4 2 0
0 0 0 4
3 0 4 0
輸出：
2 3 1 4
1 4 2 3
4 1 3 2
3 2 4 1
測資 03
輸入：
4 0 0 2
0 0 3 0
0 3 0 0
2 0 0 1
輸出：
4 3 1 2
1 2 3 4
3 1 4 2
2 4 1 3
測資 04
輸入：
0 2 0 4
0 0 3 0
4 0 0 2
0 3 0 0
輸出：
3 2 1 4
1 4 3 2
4 1 2 3
2 3 4 1
這些測試資料涵蓋了不同類型的情境，並且確保至少 2 行或 2 列僅有一個 0，符合題目條件。



歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2