백준 - 스도쿠

문제 설명

가로, 세로 그리고 현재 위치한 작은 사각형 내부에 숫자를 1-9까지 고유하게 존재해야하는 스도쿠 판을 완성하는 문제이다.

고유한 숫자가 나오기 위해서 이처럼 검사를 진행해야한다.

1) 행, 열 유일성 검사

2) 작은 사각형 내부 안에서의 숫자의 유일성 검사

시작점을 찾는 규칙을 찾아야하며 해당 시작점부터 +3,까지 숫자의 유일성을 검사해야한다.

풀이

static final int N = 9;
	static int[][] grids;

	public static void main(String[] args) throws IOException {
		grids = new int[N][N];

		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			for (int j = 0; j < N; j++) {
				grids[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		fill(0);
	}

	static void fill(int cnt) {
		if (cnt == N * N) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					System.out.print(grids[i][j]+" ");
				}
				System.out.println();
			}

			System.exit(0);
			return;
		}

		int r = cnt / N;
		int c = cnt % N;

		if (grids[r][c] != 0) {
			fill(cnt + 1);
		} else {
			for (int number = 1; number <= N; number++) {
				if (isPossible(r, c, number)) {
					grids[r][c] = number;
					fill(cnt + 1);
					grids[r][c] = 0;
				}
			}
		}
	}

	static boolean isPossible(int y, int x, int val) {
		for (int i = 0; i < N; i++) {
			if (grids[i][x] == val || grids[y][i] == val)//가로 세로 전체 탐색
				return false;
		}

		int sr = (y / 3) * 3;
		int sc = (x / 3) * 3;

		for (int i = sr; i < sr + 3; i++) {
			for (int j = sc; j < sc + 3; j++) {
				if (grids[i][j] == val)
					return false;
			}
		}

		return true;
	}