스도쿠 - 2239번(백트래킹)

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

package a1006;

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

public class Main_boj_스도쿠 {

	
	//빈칸에 1~9까지 넣어보고 조건 맞는지 알아보면 되는 백트래킹 문제인데 너무 복잡하게 생각해서 
	//permutation을 해보고 이중 10개를 고르는식으로 했더니 시간 초과가 났다 
	

	static int[][]arr;
	static ArrayList<Pair>blanklist; //비어있는 리스트
	
	static class Pair{
		
		int x,y;
		Pair(int x, int y){
			
			this.x=x;
			this.y=y;
			
		}
	}
	
	public static boolean chksquare(int x , int y, int num) { //x,y가 포함된 3X3에 num 과 중복된경우 없는지 보기
		
	
		
		int sx=0;
		int sy=0;
		
		boolean tg = false;
		for(int i=sx; i<9; i+=3) {
			for(int j=sy; j<9; j+=3) {
				
				if(x>=i && x<i+3 && y>=j && y<j+3) {
					
					for(int p=i; p<i+3; p++) {
						for(int q=j; q<j+3; q++) {
							
							if(!(p==x && q==y)&&arr[p][q]==num) {
							
								return false;
							}
							
						}
					}
					tg = true;
					break;
				}
				
				
			}
			
			if(tg)break;
		}
		
		
		return true;
		
		
	}
	
	
	public static boolean check(int x, int y, int num) { //x,y가 포함된 세로와 가로에 중복된 숫자 있는지 본다
		
		

		
	
		
		 int i=x;
	
			for(int j=0; j<9; j++) {
				
				if(y!=j) {
					if(arr[i][y]==arr[i][j]) { return false;}
				}
				
			}
		
		
			int j = y;
	
			
			for( i=0; i<9; i++) {
				
				
				if(x!=i) {
					if(arr[x][y]==arr[i][j]) {return false;}
				}
			}
	
		
		return true;
		
		
	}
	
	static boolean tg = false;
	public static void go(int idx) {
		
		if(idx == blanklist.size()) {
			
		
			
			tg=true;
			return;
		}
		
		int x = blanklist.get(idx).x;
		int y = blanklist.get(idx).y;
		
		for(int i=1; i<=9; i++) { //비어있는숫자에 1부터 9까지 넣어본다
			arr[x][y]=i; 
			if(check(x,y,i) && chksquare(x,y,i)) { //가로세로에 중복되는 숫자 없고, 3x3박스에도 중복된 숫자가 없을때 다음 빈칸으로 넘어간다
				
				
				go(idx+1);
				
				
				
			}
			
			if(tg)return;
			arr[x][y]=0;
		
		}
		
		
		
	}
	
	
	public static void main(String[]args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		arr= new int[9][9];
		blanklist = new ArrayList<>();
		
		for(int i=0; i<9; i++) {
			
			String s = br.readLine();
			for(int j=0; j<9; j++) {
				
				arr[i][j]=s.charAt(j) -'0';
				if(arr[i][j]==0) {
					
					blanklist.add(new Pair(i,j));
					
				}
				
			}
			
			
		}
		
		go(0);
		for(int i=0; i<9; i++) {
			for(int j=0; j<9; j++) {
				System.out.print(arr[i][j]);
				
			}
			System.out.println();
			
		}
		
	}
	
	
}