[백준] 2239 - 스도쿠

1. 문제

2239번: 스도쿠

2. 개요

풀다 만 스도쿠가 주어진다. 비어있는 칸은 0으로 주어진다.

이 스도쿠를 완성하는 문제. 정답이 여러개가 될 수 있다면 사전순으로 가장 앞서는 답을 출력한다.

3. 풀이 및 코드

3-1. 풀이

빈 칸을 탐색하면서 1 ~ 9 까지 대입해보면서 가로, 세로, 포함된 3x3칸에 해당 숫자가 있는지 확인한다. 없다면 해당 숫자를 넣고 다음 빈칸으로 넘어간다.

중간에 완성될 수 없는 경우가 있으므로 다음 숫자를 넣어보기 위해 다시 돌아올 경우 해당 칸을 0으로 되돌려준다.

이렇게 가장 먼저 모든 칸을 채운 스도쿠 판이 사전순으로 가장 앞서는 스도쿠 판이 되므로 이를 출력하고 프로그램을 종료한다.

3-2. Python

import sys

board = []
blank = []

for i in range(9):
    board.append(list(map(int, sys.stdin.readline().rstrip())))

    for j in range(9):
        if board[i][j] == 0:
            blank.append([i, j])

def hor(y, k):
    for i in range(9):
        if board[y][i] == k:
            return False
        
    return True

def ver(x, k):
    for i in range(9):
        if board[i][x] == k:
            return False
        
    return True

def sqr(y, x, k):
    for i in range(y//3*3, y//3*3+3):
        for j in range(x//3*3, x//3*3+3):
            if board[i][j] == k:
                return False
            
    return True

def bt(idx = 0):
    if idx == len(blank):
        for i in range(9):
            for j in range(9):
                print(board[i][j], end = '')
            print()
        sys.exit()
    
    else:
        y, x = blank[idx][0], blank[idx][1]

        for i in range(1, 10):
            if hor(y, i) and ver(x, i) and sqr(y, x, i):
                board[y][x] = i
                bt(idx+1)
                board[y][x] = 0

bt()

3-3. C#

namespace boj_2239
{
    internal class Program
    {
        static List<int[]> board;
        static List<int[]> blank;

        static void Main(string[] args)
        {
            board = new List<int[]>();
            blank = new List<int[]>();

            for (int i = 0; i < 9; i++)
            {
                string row = Console.ReadLine();
                char[] tmp = row.ToCharArray();
                board.Add(Array.ConvertAll(tmp, x => x - '0'));

                for (int j = 0; j < 9; j++)
                {
                    if (board[i][j] == 0)
                        blank.Add(new int[] { i, j });
                }
            }

            BT(0);
        }

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

            for (int i = y / 3 * 3; i < y / 3 * 3 + 3; i++)
            {
                for (int j = x / 3 * 3; j < x / 3 * 3 + 3; j++)
                {
                    if (board[i][j] == num)
                        return false;
                }
            }

            return true;
        }

        static void BT(int idx)
        {
            if (idx == blank.Count)
            {
                for (int i = 0; i < 9; i++)
                {
                    for (int j = 0; j < 9; j++)
                    {
                        Console.Write(board[i][j]);
                    }
                    Console.WriteLine();
                }
                Environment.Exit(0);
            }

            else
            {
                int y = blank[idx][0];
                int x = blank[idx][1];

                for (int i = 1; i < 10; i++)
                {
                    if (chk(y, x, i))
                    {
                        board[y][x] = i;
                        BT(idx + 1);
                        board[y][x] = 0;
                    }
                }
            }
        }
    }
}