[백준] 4056 - 스-스-스도쿠

[문제링크]

4056번: 스-스-스도쿠

 

0. 기존 스도쿠 코드의 활용(링크)

 

1. 기존 코드부터 true/false 리턴값으로 성공/실패를 알 수 있으니 함수 내부는 추가적 처리 불필요

 

2. 초기 입력값부터 규칙에 위배될 수 있으니, 시작하기 전 체크한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
	
	static int[][] map;
	static boolean[][]rowChk;
	static boolean[][]colChk;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			int N = 9;
			map = new int[N][N];
			boolean success=true;
			rowChk = new boolean[N][N+1];
			colChk = new boolean[N][N+1];
			for (int i = 0; i < N; i++) {
				String s = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j]=s.charAt(j)-'0';
					if(map[i][j]!=0) {
						if(!rowChk[i][map[i][j]])rowChk[i][map[i][j]]=true;
						else success=false;//row체크
						if(!colChk[j][map[i][j]])colChk[j][map[i][j]]=true;
						else success=false;//col체크
					}
				}
			}

			//block 체크
			for (int bx = 0; bx < 9; bx+=3) {
				for (int by = 0; by < 9; by+=3) {
					boolean[]blockChk=new boolean[N+1];
					for (int i = 0; i < 3; i++) {
						for (int j = 0; j < 3; j++) {
							if(map[bx+i][by+j]==0)continue; // 0일때는 넘어간다
							if(!blockChk[ map[bx+i][by+j] ])
								blockChk[ map[bx+i][by+j] ]=true;//0이 아닌 값을 처음 만나면 true
							else {
								success=false;//0이 아닌 값을 다시 만나면 실패한 스도쿠
							}
						}
					}
				}
			}
			
			//초기 입력값이 valid하다면
			if(success)success = rec(0);
			
			if(success) {
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						sb.append(map[i][j]);
					}sb.append('\n');
				}
			}
			else {
				sb.append("Could not complete this grid.\n");
			}sb.append('\n');
		}System.out.println(sb);
		
		
	}
	static boolean rec(int cur) {
		if(cur==81)return true;
		int x = cur/9;
		int y = cur%9;
		if(map[x][y]==0) {
			for (int i = 1; i <= 9; i++) {
				if(chk(x,y,(x/3)*3, (y/3)*3, i)) {
					rowChk[x][i]=true;
					colChk[y][i]=true;
					map[x][y]=i;
					
					if(rec(cur+1))return true;
					
					rowChk[x][i]=false;
					colChk[y][i]=false;
				}
			}
			map[x][y]=0;
		}
		else {
			//이미 뭔가 수가 있다
			return rec(cur+1);
		}
		return false;
	}
	
	static boolean chk(int row, int col, int x, int y, int val) {
		boolean ret=true;
		if(rowChk[row][val] || colChk[col][val])ret=false;
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				if(map[x+i][y+j]==val)ret=false;
		return ret;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면