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"]]

出力 −正しい。

説明 −数独行列内のすべての数値は、有効な数独のパターンに従っているため、出力はTrueになります。

この問題を解決するためのアプローチ

最初に、指定された数独ボードに一意の番号の列があるかどうかを確認します。次に、行を確認します。各3*3ブロックには、その中で一意のすべての番号が含まれています。ブロック行とブロック列のそれぞれに重複する数値が含まれているかどうかを確認し、重複している場合はfalseを返し、そうでない場合はtrueを返します。

• 数独ボードの2次元配列を入力します。

• 行に存在する要素が一意であるかどうかをチェックするブール関数。

• 列に存在する要素が一意であるかどうかを列にチェックするブール関数。

• ブロック内に存在する要素が一意であるかどうかをブロックをチェックするブール関数。

例

#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