C++ 中的有效数独

假设我们给出了一个称为数独的 9×9 矩阵。任务是检查给定的数独模式是否有效。

一般来说，数独板看起来像这样，

数独规则-

• 每行包含一个 1-9 范围内的数字

• 每列包含 1-9 范围内的数字。

• 每个 3×3 的块中都包含唯一的数字。

• 特定行不能具有相同的编号。

• 特定列不能具有相同的编号。

例如

输入 1 -

sudoku[]=
   [["3","5",".",".","2",".",".",".","."]
   ,["7",".",".","1","6","5",".",".","."]
   ,[".","9","8",".",".",".",".","6","."]
   ,["8",".",".",".","6",".",".",".","3"]
   ,["4",".",".","5",".","4",".",".","1"]
   ,["7",".",".",".","2",".",".",".","6"]
   ,[".","6",".",".",".",".","2","8","."]
   ,[".",".",".","4","1","9",".",".","5"]
   ,[".",".",".",".","8",".",".","7","9"]]

输出- 真。

解释- 由于数独矩阵中的所有数字都遵循有效数独的模式，因此输出为真。

解决这个问题的方法

最初，我们将检查给定的数独板是否具有唯一编号的列。然后我们将检查该行。每个 3*3 块包含所有唯一的数字。我们将检查每个块行和块列，如果它包含任何重复的数字，我们将返回 false，否则返回 true。

• 为数独板输入一个二维数组。

• 用于检查行中存在的元素是否唯一的布尔函数不是。

• 用于检查列中存在的元素是否唯一的布尔函数不是。

• 用于检查块中存在的元素是否唯一的布尔函数不是。

示例

#include<bits/stdc++.h>
using namespace std;
bool validSudoku(vector<vector<char>>& sudoku) {
   int row = 0, col = 0, i = 0, block = 0;
   int count[9];
   for (row = 0; row < 9; ++row){
      memset(count, 0, 9 * sizeof(int));
      for (col = 0; col < 9; ++col){
         if (sudoku[row][col] != '.')
            ++count[sudoku[row][col]-'1'];
      }
      for (i = 0; i < 9; ++i)
         if (count[i] > 1)
            return false;
   }
   for (col = 0; col < 9; ++col){
      memset(count, 0, 9 * sizeof(int));
      for (row = 0; row < 9; ++row){
         if (sudoku[row][col] != '.')
            ++count[sudoku[row][col]-'1'];
      }
      for (i = 0; i < 9; ++i)
         if (count[i] > 1)
            return false;
   }
   int block_row = 0, block_col = 0;
   for (block = 0; block < 9; ++block){
      block_row = (block / 3) * 3, block_col = (block % 3) * 3;
      memset(count, 0, 9 * sizeof(int));
      for (row = block_row; row < (block_row + 3); ++row)
      for (col = block_col; col < (block_col + 3); ++col)
         if (sudoku[row][col] != '.')
            ++count[sudoku[row][col] - '1'];
      for (i = 0; i < 9; ++i)
            if (count[i] > 1)
         return false;
   }
   return true;
}
int main(){
   vector<vector<char> > sudoku= {
      {'5','3','.','.','7','.','.','.','.'},
      {'6','.','.','1','9','5','.','.','.'},
      {'.','9','8','.','.','.','.','6','.'},
      {'8','.','.','.','6','.','.','.','3'},
      {'4','.','.','8','.','3','.','.','1'},
      {'7','.','.','.','2','.','.','.','6'},
      {'.','6','.','.','.','.','2','8','.'},
      {'.','.','.','4','1','9','.','.','5'},
      {'.','.','.','.','8','.','.','7','9'}
   };
   bool ans= validSudoku(sudoku);
   if(ans){
      cout<<"True"<<endl;
   } else {
      cout<<"false"<<endl;
   }
   return 0;
}

True