c++ - 用于检查我们是否拥有有效数独的辅助函数

Question

我正在阅读一本名为 Elements of Programming Interviews 的书，并且正在阅读第 79 页上名为 HasDuplicate 的辅助函数，但我无法理解它的工作原理。

代码如下:

// Return true if subarray partial_assignment[start_row]
// [end_row -  1][start_col, end_col - 1] contains any duplicate
// in {1, 2 ..., size(partial_assignemnt)}; 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(size(partial_assignment) + 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;
}

请注意，partial_assignment 是部分填充的数独网格。我只是不确定它如何检查是否有重复项。可能跟双端队列有关？

Answer 1

代码中的注释:

bool HasDuplicate(const vector<vector<int>>& partial_assignment, int start_row, 
                  int end_row, int start_col, int end_col)
{
   // this creates a container for bookkeeping of used numbers
   // size+1 because the number 1-x are used.
   deque<bool> is_present(size(partial_assignment) + 1, false);

   // The variables i and j are used to go through every coordinate on the
   // sudoku game board.
   for(int i = start_row; i < end_row; ++i)
   {
       for(int j = start_col; j < end_col; ++j)
       {
           // here it checks if the current number is already marked as used in "is_present"
           // if it is, then it's a duplicate and the function returns true.

           // The value 0 is used at coordinates where no number has been
           // selected.
           if(partial_assignment[i][j] != 0 && is_present[partial_assignment[i][j]])
               return true;

           // otherwise, mark the number as used
           is_present[partial_assignment[i][j]] = true;
       }

    }
    return false;
}