스도쿠

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

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

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

입력

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

출력

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

제한

• 12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
  - C++17: 180ms
  - Java 15: 528ms
  - PyPy3: 2064ms

예제 입력 1

103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

예제 출력 1

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

문제 풀이

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static int[][] map;
    static ArrayList<Point> list;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        char[][] tmp=new char[9][9];
        map=new int[9][9];
        list=new ArrayList<>();

        for(int i=0;i<9;i++){
            tmp[i]=br.readLine().toCharArray();
            for(int j=0;j<9;j++){
                map[i][j]=tmp[i][j]-'0';
                if(map[i][j]==0){
                    list.add(new Point(i,j));
                }
            }
        }

        //스도쿠 확인
        sudoku(0);

    }

    private static void sudoku(int depth) {
        if(depth==list.size()){
            for(int i=0;i<9;i++){
                for(int j=0;j<9;j++){
                    System.out.print(map[i][j]);
                }
                System.out.println();
            }
            System.exit(0);
        }


        int x=list.get(depth).x;
        int y=list.get(depth).y;

        boolean[] num=new boolean[10];
        //가로세로박스 숫자들을 체크해서 빈칸에 넣을 수 있는 숫자 후보 확인
        //가로
        for(int k=0;k<9;k++){
            if(map[x][k]!=0) {
                num[map[x][k]]=true;
            }
        }
        //세로
        for(int k=0;k<9;k++){
            if(map[k][y]!=0) {
                num[map[k][y]]=true;
            }
        }
        //박스
        for(int k=x/3*3;k<x/3*3+3;k++){
            for(int m=y/3*3;m<y/3*3+3;m++){
                if(map[k][m]!=0){
                    num[map[k][m]]=true;
                }
            }
        }

        //빈칸에 후보 숫자 넣어보기
        for(int k=1;k<10;k++){
            if(!num[k]){
                map[x][y]=k;
                sudoku(depth+1);
                map[x][y]=0;
            }
        }
    }
}

스도쿠의 특성상 가로, 세로, 3x3 박스 내에 있는 숫자들을 확인하고 빈칸에 들어갈 수 있는 숫자의 후보들을 추린다.

빈칸이 있는 위치를 ArrayList에 모두 담아주고 각 빈칸을 채워가면서 스도쿠를 맞춰본다. 빈칸이 채워지지않는 경우 백트래킹을 이용하여 스도쿠가 완성되는 때를 찾아본다.

가로,세로, 3x3 박스 확인

int x=list.get(depth).x;
int y=list.get(depth).y;

boolean[] num=new boolean[10];
//가로세로박스 숫자들을 체크해서 빈칸에 넣을 수 있는 숫자 후보 확인
//가로
for(int k=0;k<9;k++){
    if(map[x][k]!=0) {
        num[map[x][k]]=true;
    }
}
//세로
for(int k=0;k<9;k++){
    if(map[k][y]!=0) {
        num[map[k][y]]=true;
    }
}
//박스
for(int k=x/3*3;k<x/3*3+3;k++){
    for(int m=y/3*3;m<y/3*3+3;m++){
        if(map[k][m]!=0){
            num[map[k][m]]=true;
        }
    }
}

//빈칸에 후보 숫자 넣어보기
for(int k=1;k<10;k++){
    if(!num[k]){
        map[x][y]=k;
        sudoku(depth+1);
        map[x][y]=0;
    }
}

해당 좌표를 기준으로 가로, 세로, 3x3박스 내에 0을 제외한 숫자가 있는지 확인하고 체크해준다.

숫자 후보를 좌표에 모두 넣어보고 depth를 하나 추가하여 재귀호출을 한 뒤 백트래킹으로 값을 초기화해준다.

재귀함수 종료조건

if(depth==list.size()){
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            System.out.print(map[i][j]);
        }
        System.out.println();
    }
    System.exit(0);
}

depth가 빈칸의 개수와 같아지면 종료조건을 수행한다. 이 말은 모든 빈칸을 숫자로 채웠다는 이야기이므로 답을 출력해주면된다.