3 분 소요

[2580] 스도쿠

Algorithm: 백트래킹 Created: Jan 28, 2020 5:42 PM DoubleChk: No Type: 백준 link: https://www.acmicpc.net/problem/2580

문제

스도쿠는 18세기 스위스 수학자가 만든 ‘라틴 사각형’이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

https://www.acmicpc.net/upload/images/jF1kwmQaGGRM3t9ESvpTvW34kCnB2.png

나머지 빈 칸을 채우는 방식은 다음과 같다.

  1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
  2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

https://www.acmicpc.net/upload/images/iWqN5AZPf4h.png

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

https://www.acmicpc.net/upload/images/A9FWbU92T9v2Fjr9U6Qsg.png

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

https://www.acmicpc.net/upload/images/fjCQBE3QI9BMGeiClrtwkHy3jeGPNi.png

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

예제 입력 1

0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0

예제 출력 1

1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <string.h>
    using namespace std;
    int sudoku[10][10];
    int checkRow[10][10];
    int checkCol[10][10];
    int checkSquare[10][10];
    int cnt;
    void print(){
    
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                cout << sudoku[i][j] << ' ';
            }
            cout << endl;
        }
    
    }
    
    bool valid(int row, int col, int num){
        if(checkRow[row][num] || 
    				checkCol[num][col] || 
    				checkSquare[row/3 * 3 + col/3][num]) return false;
        return true;
    }
    void solve(int cnt){
        if(cnt >= 81){
            print();
            exit(0);
        }
    
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(sudoku[i][j] == 0){
                    for(int k=1; k<10; k++){
                        if(valid(i, j, k)){
                            sudoku[i][j] = k;
                            checkRow[i][k] = 1;
                            checkCol[k][j] = 1;
                            checkSquare[i/3*3 + j/3][k] = 1;
                            solve(cnt + 1);
    
                            sudoku[i][j] = 0;
                            checkRow[i][k] = 0;
                            checkCol[k][j] = 0;
                            checkSquare[i/3*3 + j/3][k] = 0;
                        }
                    }
                    return;
                }
            }
        }
    }
    int main(){
    
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                int num;
                cin >> num;
                sudoku[i][j] = num;
                checkRow[i][num] = 1;
                checkCol[num][j] = 1;
                checkSquare[i/3*3 + j/3][num] = 1;
                if(num != 0) cnt++;
            }
        }
    
        solve(cnt);
        return 0;
    }

  • 문제 풀이

    스도쿠를 풀려면 3가지 조건이 충족되어야 한다.

    1. 가로 줄에 숫자가 중복이 안되어야 함
    2. 세로 줄에 숫자가 중복이 안되어야 함
    3. 3*3 사각형에 숫자가 중복이 안되어야 함

    그래서 배열이 3개 필요하다! → 가로 체크, 세로 체크, 사각형 체크

    일단 입력을 받으면서 0이 아닌 입력들을 체크 해 준다.

    그리고 재귀 함수에 센 숫자를 인자로 보내준다.

    스도쿠 판이 9*9이기 때문에 함수 내에서 기저 조건을 81이랑 cnt랑 같으면 끝내게 해 주었다.

    이제 스도쿠 판을 돌면서 0에 1부터 10까지 하나씩 넣어보면서 재귀를 돈다.

    숫자를 넣어 볼 때 이미 가로, 세로, 사각형에 들어가 있는 숫자인지 체크 해 준다 (valid 함수)

    스도쿠 답은 여러개가 될 수 있지만, 1개만 출력 하라고 했기 때문에 exit(0)으로 탈출한다.

    Square 체크 할 때, i/3 *3 + j/3에 대해서 설명을 하겠다. 예시를 들면 더 쉽기 때문에 예시를 보면서 설명하겠다. _2020-01-28__6 42 22

    i, j가 0일 때에 각각의 값들은 다음과 같다.

    checkSquare[0][num] = 1 의 의미는 → 해당 square 칸(0)에 num이 있다고 표시 해 준다.

    따라서 i3/3+j3은 해당 square의 가장 왼쪽 위를 가리킨다.

    그 값으로 어떤 칸인지 체크 하는 것이다.

    다음 예시를 보겠다. _2020-01-28__6 44 12

    i*3/3+j/3의 값은 3이다.

    3은 2번째 칸의 시작 인덱스이다!

    4, 1도 똑같이 나온다.

    해당 칸 안에 있는 것들은 다 3이 나오게 될 것이다. → 이걸로 square안에 num을 체크 해주는것!

  • 후기

    스도쿠 풀어본적도 없는데 알고리즘으로 배웠다 인생 모를..

    휴대폰 게임도 스도쿠는 안하고 걸렀는데

    수포자 승리하자

카테고리:

업데이트:

참고