數獨檢查器 - 如何檢查子網格中的重複項

Question

我正在閱讀這本書編程元素編程面試和我遇到了爲數獨檢查器編寫解決方案的問題。我能夠輕鬆找出如何檢查以確保當前元素在當前列和行的其他任何地方都沒有找到，但它已被證明是非常重要的，以檢查當前子網格中的重複項。

我很難搞清楚的問題是如何知道當前元素在哪個子網格中（在您遍歷2D數組時）以及子網格的起始位置。

書中的解決方法似乎就是檢查各做次網格如下：

bool isValidSudoku(const vector<vector<int>>& partial_assignment) { 
    //Code to check row constraints 
    //Code to check col constraints 

    //Check region constraints (I'm assuming this is to check each subgrid) 

    int region_size = sqrt(partial_assignment.size()); 
    for (int I = 0; I < region_size; ++I) { 
     for (int J = 0; J < region_size; ++J) { 
      if (HasDuplicate(partial_assignment, region_size * I), 
       region_size * (I + 1), region_size * J, 
       region_size * (J + 1)){ 
       return false; 

      } 
     } 
    } 
    return true; 

} 

//Return true if subarray partial_assignment[start_row : end_row - 1] 
//[start_col : end_col -1] contains any duplicates in {1,2,.... 
// partial_assignment.size()}; otherwise return false. 
bool HasDuplicate(const vector<vector<int>>& partial_assignment, 
    int start_row, int end_row, int start_col, int end_col) { 
    deque<bool> is_present(partial_assignment.size() + 1, false); 
    for (int i = start_row; i < end_row;++i) { 
     for (int j = start_col; j < end_col;++j) { 
      if (partial_assignment[i][j] != 0 && 
       is_present[partial_assignment[i][j]) { 
       return true; 
      } 
      is_present[partial_assignment[i][j]] = true; 
     } 
    } 
    return false; 
} 

所以，我有幾個問題在這裏：如果它在矩陣，爲什麼發現的區域（或子方格）是否需要爲該子方框中的每個元素調用has_duplicates()？我認爲你只需要遍歷該方塊中的每個元素，並簡單地檢查每個元素是否曾經被看到過。

我假設輸入電網將是一個正常的2-d格這樣，但也許這是情況並非如此：

vector<vector<int>> partial_assignment = { {5,3,4,6,7,8,9,1,2}, 
           {6,7,2,1,9,5,3,4,8}, 
           {1,9,8,3,4,2,5,6,7}, 
           {8,5,9,7,6,1,4,2,3}, 
           {4,2,6,8,5,3,7,9,1}, 
           {7,1,3,9,2,4,8,5,6}, 
           {9,6,1,5,3,7,2,8,4}, 
           {2,8,7,4,1,9,6,3,5}, 
           {3,4,5,2,8,6,1,7,9} 

    }; 

此外，什麼是使用std::deque檢查點當你可以使用std::unordered_map時可以重複使用嗎？

Answer 1

如果在矩陣中找到區域（或子方框），爲什麼需要爲該子方框中的每個元素調用has_duplicates（）？

不是。 isValidSudoku中的循環從0重複爲region_size - 1，s從標準的sudoko從0到2。然後將每個I和J乘以region_size以得到您的開始和結束行/列：0-2,3-5和6-8。 HasDuplicate被稱爲9次。

通過在每個循環中引入一串cout <<語句來分析代碼，以便在循環迭代時打印變量，這可能會有所幫助。