[ LeetCode ][JAVA][37] Sudoku Solver (스도쿠 풀기)

leetcode.com/problems/sudoku-solver/submissions/

Sudoku Solver - LeetCode

문제

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character

...and its solution numbers marked in red.

제한사항

• The given board contain only digits 1-9 and the character '.'.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always 9x9.

접근

백트래킹을 이용해 스도쿠 문제를 해결한다.

코드

import java.util.Arrays;

class Solution {
	//백 트래킹
	//정답을 찾을 때 까지
	//	모든 경우의 수를 전진하면서, 스도쿠 유효성을 어기지 않는지 확인하면서 탐색
	//	더이상 나아갈길이 없으면
	//	한칸 뒤로 후퇴
	public void solveSudoku(char[][] board) {
		backtrack(board, 0);
	}
	

	public boolean backtrack(char[][] board, int idx) {
		if(idx==81) return true;
		int row = idx / 9;
		int col = idx % 9;
		char cur = board[row][col];
         // 숫자가 존재
		if(cur != '.') {
			return backtrack(board, idx+1);
		}else {	// 빈공간
			for(int i=1; i<=9; i++) {
				board[row][col] = Integer.toString(i).charAt(0);
                //System.out.println(board[row][col]);
				if(isValidSudoku(board)) {
					boolean b = backtrack(board, idx + 1);
					if(b) return b;
				}
			}
			board[row][col] = '.';
			return false;
		}
	}
	
	public boolean isValidSudoku(char[][] board) {
		boolean[] b = new boolean[9];
		//룰의 종류, 가로/세로/섭그리드
		for(int i=0; i<3; i++) {
			//한줄의 규칙
			for(int j=0; j<9; j++) {
				Arrays.fill(b, false);
				for(int k=0; k<9; k++) {
					char cur= '.';
					if(i == 0) {
						//가로
						cur=board[j][k];
					}else if(i == 1) {
						//세로
						cur=board[k][j];
					}else {
						//섭그리드
						cur = board[j/3*3 + k/3][j%3*3 + k%3];
					}
					if(cur=='.') continue;
					int val = Character.getNumericValue(cur);
                    //System.out.println("k-> "+k+"    cur->"+cur+"   val::::"+val);
					if(b[val-1]) return false;
					b[val-1] = true;
				}
			}
		}
		return true;
	}
}