数独检查器 - 如何检查子网格中的重复项

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 <<语句来分析代码，以便在循环迭代时打印变量，这可能会有所帮助。