白俊2239号:斯多庫

問題の説明

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

数独を完了する必要があります.

方法

バックアップ追跡.

(x,y)に1、2、3、4、5、6、7、8、9のいずれかの数値を入力し、次のように入力します.

斯多庫規則を守らない場合は、戻って次の数字を入力してみてください.

は、その深さで出会った最初のスペースをチェックするだけで、残りのスペースはより深い深さでチェックするだけです.

a b c	// a,b,c는 모두 0을 의미하며, depth가 0일 때 -> a의 값만 1,2,3 해보면 됩니다.
1 2 3 
2 3 1

1 b c	2 b c	3 b c 
1 2 3	1 2 3	2 3 1
2 3 1	2 3 1	2 3 1  // 이렇게 3가지 경우만 고려하면 되지

a 1 c	a 2 c	a 3 c 
1 2 3	1 2 3	2 3 1
2 3 1	2 3 1	2 3 1  // 이러한 경우와(b를 고려)

a b 1	a b 2	a b 3 
1 2 3	1 2 3	2 3 1
2 3 1	2 3 1	2 3 1 // 이러한 경우(c를 고려)를 고려할 필요는 없습니다.

注意事項

項目を考慮しないと、長い時間がかかります.

スペースがNの場合、各スペースには9個の数字を含めることができるので、9^Nの時間がかかる場合があります.

この場所から可能な要素のリストを直接返すよりも、どの要素が有効かを決定します.

横、縦、四角から見ると、ここには{1,7}入ることができます.X

加えて

1~9は1か7だったのかなO

考慮すべき要素が多いため、

listを返すのは難しい.
例えば

では、「横方向検査」の{1,4}、「縦方向検査」の{1}、「矩形検査」の{1,2,3,4,5,6,7,8,9}が利用可能であれば、1しか返されません.

pseudocode

Validate(x,y,c,board){
	(x,y)의 가로줄에 c가 있다면 return false;
	(x,y)의 세로줄에 c가 있다면 return false;	
    (x,y)가 포함된 3x3사각형에 c가 있다면 return false;
    위 3 조건을 모두 피해왔다면 return true
}

BackT(){
	if(모든 빈칸을 규칙에 맞게 다 채웠다면){
    	정답출력
        return;
    }

	for(i->1~9){ // 가로
    	for(j->1~9){ // 세로
        	if(현재 칸에 숫자가 채워져 있다면) continue;
        	for(c->1~9){
            	if(Validate(i,j,c,board)){ // 현재의 빈칸을 c로 채울 수 있다면
                	(i,j)를 c로 채우고
                    BackT(depth+1,board) // 다음 빈칸을 채우러 갑니다.
                    현재 (i,j)에서 또 다른 c가 가능한지 확인하기 위해 0으로 리셋시킵니다.
                    
                }
            }
            return false; // depth하나당 하나의 빈칸만 채웁니다.
        } 
    }
}

正解

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

public class Main {
	static int N = 9;
	static int ZeroCnt = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		int[][] board = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			char[] temp = st.nextToken().toCharArray();
			for (int j = 0; j < N; j++) {
				if (temp[j] == '0')
					ZeroCnt++;
				board[i][j] = temp[j] - '0';
			}
		}
		BackT(0, board);
	}


	public static boolean Validate(int x, int y, int c, int[][] board) {
		for (int i = 0; i < N; i++) { // 가로검사와 세로검사
			if (board[x][i] == c) return false; 
			if (board[i][y] == c) return false;
		}
		
		// 사각형 검사
		int startX = 3 * (x / 3);
		int startY = 3 * (y / 3);
		for (int i = startX; i < startX + 3; i++) {
			for (int j = startY; j < startY + 3; j++) {
				if (board[i][j] == c)
					return false;
			}
		}
		return true;
	}

	public static boolean BackT(int depth, int[][] board) {
		if (depth == ZeroCnt) { // 모든 0을 규칙에 맞게 채웠다면
			for (int i = 0; i < board.length; i++) {
				StringBuffer sb = new StringBuffer();
				for (int j = 0; j < N; j++) {
					sb.append(board[i][j]);
				}
				System.out.println(sb.toString());
			}
			return true;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] != 0) continue; // 이미 채워진 공간은 고려하지 않습니다.
				for (int c = 1; c <= 9; c++) { // 어떠한 빈칸에서 1~9까지 숫자를 고려해 봅니다.
					if (Validate(i, j, c, board)) { // 숫자c를 넣었을 때 아무런 이상이 없다면
						board[i][j] = c; // c를 넣어봅니다
						if (BackT(depth + 1, board)) return true; // 다음 빈칸을 찾으러 갑니다.
						board[i][j] = 0; // 가능한 다른c를 넣기 위해 0으로 바꿔줍니다.
					}
				}
				// 처음 만나는 0만 채우고 다른 0은 depth가 더 깊은 곳에서 채우면 되기 때문에 return 합니다.
				return false;

			}
		}
		return false;
	}

}