LC37. Sudoku Solver

작성일

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

  • 특별할 것이 없는 백트래킹 문제
  • 나름 코드를 간결하게 작성한것이 뿌듯했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool success = false;
    void solveSudoku(vector<vector<char>>& board, int x = 0, int y = 0) {
        if(x == 0 && y == 9) {
            success = true;
        } else if(board[x][y] != '.') {
            solveSudoku(board,(x==8?0:x+1),(x==8?y+1:y));
        } else {
            vector<int> candi(10);
            for(int i = 0; i < 9; i++) {
                if(board[x][i] != '.') candi[board[x][i]-'0']= 1;
                if(board[i][y] != '.') candi[board[i][y]-'0']= 1;
            }
            int sx = x/3*3, sy = y/3*3;
            for(int i = 0; i <3; i++) for(int j = 0; j < 3; j++)
                if(board[sx+i][sy+j] != '.') candi[board[sx+i][sy+j]-'0']= 1;
            for(int i = 1; i <= 9; i++){
                if(candi[i]) continue;
                board[x][y] = i+'0';
                solveSudoku(board,(x==8?0:x+1),(x==8?y+1:y));
                if(success) return;
                board[x][y] = '.';
            }
        }
    }
};