boj 2239 스도쿠

www.acmicpc.net/problem/2239

2239번: 스도쿠

백트래킹 기본문제 중 하나입니다.

우선 스도쿠는 9 * 9 배열이 있을 때 각 행, 열, 3 * 3구간에서 1 ~ 9가 한 번씩만 나오게 하는 문제입니다.

 

그럼 각 행, 열, 구간을 중복체크하는 배열을 세개 사용합니다.

(0, 0)부터 (8, 8)까지 한 칸씩 확인하며, list[x][y] != 0이면 수를 넣을 필요가 없으므로 바로 다음좌표를 탐색합니다.

list[x][y] == 0이면 1 ~ 9까지 넣을 수 있는지 확인합니다.

(x, y)에서 숫자 i가 x행에서 사용되었는지, y열에서 사용되었는지, 같은 구간에서 사용되었는지 각각 확인해줍니다.

세 구간 모두 사용되지 않은 숫자만 list[x][y]에 넣어주고 다음좌표로 넘겨줍니다.

모든 좌표를 탐색하였으면 답을 출력하고 리턴합니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static char div[][] = { { 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' },
            { 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' }, { 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' },
            { 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' }, { 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' },
            { 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' }, { 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' },
            { 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' }, { 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' }, };
    static boolean rowsChk[][] = new boolean[10][10];
    static boolean colsChk[][] = new boolean[10][10];
    static boolean divChk[][] = new boolean[10][10];
    static int list[][] = new int[10][10];
 
    static boolean func(int x, int y) {
        if (x == 9) {
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(list[i][j]);
                }
                sb.append("\n");
            }
            System.out.println(sb.toString());
            return true;
        }
 
        int nx = x;
        int ny = y + 1;
        if (ny == 9) {
            nx++;
            ny = 0;
        }
 
        if (list[x][y] != 0)
            return func(nx, ny);
        else {
            for (int i = 1; i <= 9; i++) {
                if (rowsChk[x][i] || colsChk[y][i] || divChk[div[x][y] - 'a'][i])
                    continue;
 
                rowsChk[x][i] = true;
                colsChk[y][i] = true;
                divChk[div[x][y] - 'a'][i] = true;
                list[x][y] = i;
                boolean chk = func(nx, ny);
                if (chk)
                    return true;
                list[x][y] = 0;
                divChk[div[x][y] - 'a'][i] = false;
                colsChk[y][i] = false;
                rowsChk[x][i] = false;
            }
        }
 
        return false;
    }
 
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        char ch[];
        for (int i = 0; i < 9; i++) {
            st = new StringTokenizer(br.readLine());
            ch = st.nextToken().toCharArray();
            for (int j = 0; j < 9; j++) {
                list[i][j] = ch[j] - '0';
                if (list[i][j] != 0) {
                    rowsChk[i][list[i][j]] = true;
                    colsChk[j][list[i][j]] = true;
                    divChk[div[i][j] - 'a'][list[i][j]] = true;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0, 0);
    }
}