알고리즘 스터디 30일차

1. 스도쿠

1) 문제

문제 설명
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

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

2) 문제 분석 및 풀이

1) 설계, 분석

2) 풀이

#include<iostream>
#include<vector>
using namespace std;

bool check = false;
vector<vector<int>> board;

bool CanPlace(int x, int y, int num)
{
    for (int i=0; i<9; i++)
    {
        if (board[x][i] == num) return false;
        if (board[i][y] == num) return false;
    }

    int boxX = ( x / 3 ) * 3;
    int boxy = ( y / 3 ) * 3;

    for (int i=0; i<3; i++)
    {
        for (int j=0; j<3; j++)
        {
            if (board[boxX+i][boxy+j] == num) return false;
        }
    }
    return true;
}

void dfs(int x, int y) 
{
    if (check) return;
    for (int i=x; i<9; i++)
    {
        for (int j= (x==i ? y : 0) ; j < 9; j++)
        {
            if (board[i][j] == 0)
            {
                for (int k = 1; k <=9; k++)
                {
                    if (CanPlace(i,j,k))
                    {
                        board[i][j] = k;
                        dfs(i,j);
                        if (check) return;
                        board[i][j] = 0;
                    }
                }
                return;
            }
        }
    }
    check = true;
}

void sudoku() {
    for (int i = 0; i < 9; i++) 
    {
        board.push_back(vector<int>());
        for (int j = 0; j < 9; j++) 
        {
            int temp;
            cin >> temp;
            board[i].push_back(temp);
        }
    }

    dfs(0, 0);

    for (const auto& row : board) 
    {
        for (int n : row)
            cout << n << " ";
        cout << "\n";
    }

}

int main() 
{
  sudoku();
}