leetcode 노트: 유효한 스 도 쿠

제목 설명
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules： http://sudoku.com.au/TheRules.aspx . The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.
The following figure: A partially filled sudoku which is valid.

문제 분석
스 도 쿠 행렬 의 성질 에 대해 간단하게 요약 할 수 있다. 행렬 의 각 줄, 각 열 과 각 3×3 의 구 궁 격 구역 에 유일한 0~9 배열 조합 이 존재 하 는 지, 같은 요소 가 존재 한다 면 이 스 도 쿠 행렬 은 합 법 적 이지 않다.
이 문 제 는 스 도 쿠 행렬 의 모든 요 소 를 옮 겨 다 니 며 각 요소 가 스 도 쿠 의 성질 을 만족 시 키 는 지 확인 하 는 것 이 간단 하 다.한 요소 가 특정한 줄, 특정한 열 또는 특정한 작은 구역 에 있 는 지 판단 하 는 데 저 는 0 ~ 9 숫자 출현 횟수 를 저장 하 는 map 을 정 의 했 습 니 다. '1'，'2'，...，'9' 를 키워드 로 사용 하면 특정한 키워드 의 저장 대상 이 1 보다 크 면 이 줄, 열 또는 3×3 의 구 궁 격 구역 에 중복 되 는 키 가 있 음 을 나타 냅 니 다.이런 방식 으로 옮 겨 다 니 면 행렬 이 합 법 적 인지 아 닌 지 를 판단 할 수 있다.
예시 코드

#include <iostream>
#include <vector>
#include <map>
using namespace std;

class Solution
{
public:
    bool isValidSudoku(vector<vector<char> >& board)
    {
        map<char, int> sudokuMap;
        for (int i = 0; i < 9; i++)
        {
            sudokuMap.clear();
            for (int j = 0; j < 9; j++)
            {
                sudokuMap[board[i][j]]++;
                if ((board[i][j] != '.') && (sudokuMap[board[i][j]] > 1))
                    return false;
            }
        }

        for (int i = 0; i < 9; i++)
        {
            sudokuMap.clear();
            for (int j = 0; j < 9; j++)
            {
                sudokuMap[board[j][i]]++;
                if ((board[j][i] != '.') && (sudokuMap[board[j][i]] > 1))
                    return false;
            }
        }

        for (int i = 0; i < 9; i += 3)
        {
            for (int j = 0; j < 9; j += 3)
            {
                sudokuMap.clear();
                for (int k = i; k < i + 3; k++)
                {
                    for (int l = j; l < j + 3; l++)
                    {
                        sudokuMap[board[k][l]]++;
                        if ((board[k][l] != '.') && (sudokuMap[board[k][l]] > 1))
                            return false;
                    }
                }
            }
        }
        return true;
    }
};

실행 결 과 는 다음 과 같 습 니 다.
1. 정확 한 수 독 행렬:

2. 잘못된 수 독 행렬:

소결
이 문 제 는 어떤 알고리즘 을 실현 하 라 고 요구 하지 않 고 행렬 연산 만 설계 하고 map 을 사용 하여 각 줄, 각 열 또는 각 구 궁 격 1~9 에 나타 난 횟수 를 저장 합 니 다. 하나 이상 의 것 을 발견 하면 바로 이 스 도 쿠 를 부정 할 수 있 습 니 다. 전체 스 도 쿠 행렬 을 옮 겨 다 니 고 요구 에 부합 해 야 valid sudoku 로 판정 할 수 있 습 니 다.
관련 제목: 스 도 쿠 솔 버