스도쿠라고 하는 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