[LeetCode] Sudoku Solver (Java)

문제

문제풀이 1. 무지성 For문 

- 일단 스도쿠 판의 배열이 9*9로 정해져 있고,
하나의 solution만 있는 것이 보장되기 때문에, 무지성 반복문을 계속 돌려서 값을 넣어보는 방식을 채택했다.

class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }

    private boolean solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (checkDup(board, i, j, c)) {
                            board[i][j] = c;
                            if (solve(board)) {
                                return true;
                            } else {
                                board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean checkDup(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if(board[i][col] == c || board[row][i] == c || 
            board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
                return false;
            }
        }
        return true;
    }
}

결과는 더헉..! 11초..? 미쳤다. 당장 단축해.
사실 위 방법을 사용하면, 이미 검색한 애들도 for문의 영향으로 또 돌기 때문에 굉장히 비효율적이다.

문제풀이2. 백트래킹을 통해서  재귀를 돌리자.

class Solution {
    
    public void solveSudoku(char[][] board) {
        solve(board, 0, 0);
    }

    private boolean solve(char[][] board, int row, int col) {
        // Entire board has been filled
        if (row == board.length) {
            return true;
        }

        // Move to next row
        if (col == board[0].length) {
            return solve(board, row + 1, 0);
        }

        // Skip cells
        if (board[row][col] != '.') {
            return solve(board, row, col + 1);
        }

        for (char c = '1'; c <= '9'; c++) {
            if (isValid(board, row, col, c)) {
                board[row][col] = c;
                if (solve(board, row, col + 1)) {
                    return true;
                }
                board[row][col] = '.';
            }
        }

        return false;
    }

    private boolean isValid(char[][] board, int row, int col, char c) {

        for (int i = 0; i < board.length; i++) {

            if (board[i][col] == c) {
                return false;
            }

            if (board[row][i] == c) {
                return false;
            }

            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
                return false;
            }
        }

        return true;
    }
}

죠큼 단축 됐지만.. 만족스럽지 않아.. 다시 방법을 탐구해보아야겠다.