<Hard> Sudoku Solver (LeetCode : C#)

https://leetcode.com/problems/sudoku-solver/

📕 문제 설명

스도쿠가 주어질 때 빈 칸 채워서 완성하기

스도쿠 규칙

1. 각 row, column에는 1~9의 숫자가 하나씩 채워진다.
2. 3x3 공간에 1~9의 숫자가 하나씩 채워진다.

'.' = 빈공간

• Input
  빈 스도쿠
• Output
  완성된 스도쿠 (void -> board만 채우면 됨)

예제

풀이

1. 재귀를 사용해 비어있는 모든 칸에 1~9까지 넣어본다.
2. 이때 스도쿠 조건 확인하는 조건도 확인 (행, 열, 3x3 내 겹치는 숫자 있는지)

public class Solution {
    public void SolveSudoku(char[][] board) {
        FillSudoku(board);
    }

    public bool FillSudoku(char[][] board)
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                // 비어있으면
                if (board[i][j] == '.')
                {
                	// 1~9 넣어보기
                    for (char c = '1'; c <= '9'; c++)
                    {
                        if (IsValid(board, c, i, j))
                        {
                            board[i][j] = c;
                            if (FillSudoku(board)) return true;
                            else board[i][j] = '.';
                        } 
                    }
					// 다른거 채우다 잘못된거 발견 (FillSudoku 재귀중)
                    return false;
                }
            }
        }

        return true;
    }

    public bool IsValid(char[][] board, char ch, int row, int col)
    {
        // 같은 행에 동일한 값 있는지 확인
        for (int i = 0; i < 9; i++)
        {
            if (board[row][i] == ch) return false;
        }
        // 같은 열에 동일한 값 있는지 확인
        for (int i = 0; i < 9; i++)
        {
            if (board[i][col] == ch) return false;
        }
        // 3 x 3 내에 동일한 값 있는지 확인
        int r = (row / 3) * 3;
        int c = (col / 3) * 3;

        for (int i = r; i < r + 3; i++)
        {
            for (int j = c; j < c + 3; j++)
            {
                if (board[i][j] == ch) return false;
            }
        }

        return true;
    }
}

결과