백준 백트래킹 - 2580번 : 스도쿠

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

2580번: 스도쿠

---

import java.io.*;
import java.util.*;

class blank{
	int i;
	int j;
	public blank(int i, int j) {
		this.i = i;
		this.j = j;
	}
}
public class Main {
	static ArrayList<blank> b = new ArrayList<>();
	static int[][] board = new int[9][9];
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		for(int i=0; i<9; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<9;j++) {
				board[i][j] =  Integer.parseInt(st.nextToken());
				if(board[i][j]==0) {
					b.add(new blank(i,j));
				}
			}
		}
		func(0,b.size());
		
	}
	public static void func(int now, int target) {
		
		if(now==target) {
			for(int i=0; i<9; i++) {
				for(int j=0; j<9; j++) {
					System.out.print(board[i][j]+" ");
				}
				System.out.println();
			}
			
			System.exit(0);
		}
		int i = b.get(now).i;
		int j = b.get(now).j;
		for(int k=1; k<=9; k++) {
			if(check(i,j,k)) {
				board[i][j] = k;
				func(now+1,target);
				board[i][j] = 0;
			}
		}
	}
	public static boolean check(int i, int j, int num) {
		for(int k=0; k<9; k++) {
			if(board[i][k]==num) return false;
			if(board[k][j]==num) return false;
		}
		int k = -1;
		int l = -1;
		if(i/3>0) {
			k = i/3*3;
		}
		else k = 0;
		if(j/3>0) {
			l = j/3*3;
		}
		else l = 0;
		int itarget = k+3;
		int jtarget = l+3;
		for(; k<itarget; k++) {
			for(; l<jtarget; l++) {
				if(board[k][l]==num) return false;
			}
			l-=3;
		}
		return true;
	}
}