BJ2239 스도쿠

https://www.acmicpc.net/problem/2239

가능한 경우를 하나씩 확인하며 순차적으로 확인하다 사전식으로 가장 빠른 경우가 완성되면 출력하고 시스템을 종료한다.

package day0406;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class sudoku {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int[][] map;
	static boolean[] b = new boolean[10]; 

	static boolean check(int x, int y, int val) {
		for(int i = 1; i <= 9; i++) {
			b[i] = false;
		}
		for (int i = (x / 3) * 3; i < (x / 3) * 3 + 3; i++) {
			for (int j = (y / 3) * 3; j < (y / 3) * 3 + 3; j++) {
				if (map[i][j] != 0)
					b[map[i][j]] = true;
			}
		}
		for (int i = 0; i < 9; i++) {
			if (map[i][y] != 0)
				b[map[i][y]] = true;
		}

		for (int i = 0; i < 9; i++) {
			if (map[x][i] != 0)
				b[map[x][i]] = true;
		}

		if(b[val]) return false;
		else return true;

	}

	static void printmap() {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
		System.exit(0);
	}
	static void func(int x, int y) {
		if(y == 9) {
			func(x + 1, 0);
			return;
		}
		if(x == 9) {
			printmap();
		}
		if(map[x][y] == 0) {
			for(int i = 1; i <= 9; i
					++) {
				if(check(x,y,i)) {
					map[x][y] = i;
					func(x, y + 1);
				}
			}
			map[x][y] = 0;
			return;
		}
		func(x, y + 1);
	}
	public static void main(String[] args) throws IOException {
		map = new int[9][9];
		for (int i = 0; i < 9; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			char[] tmp = st.nextToken().toCharArray();
			for (int j = 0; j < 9; j++) {
				map[i][j] = tmp[j] - 48;
			}
		}
		func(0, 0);
	}
}

좋은 웹페이지 즐겨찾기