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를 반환합니다.

• 스도쿠 보드용 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