[백준] 2580 스도쿠

우리가 흔히아는 스도쿠 문제다

옛날에 처음 풀때는 엄청 어렵게 푼 기억이 있는데 다시푸니까 생각보다 너무 쉽다

 

그냥 백트래킹으로 숫자 넣어보면서 되는지 안되는지 확인하면 된다

 

숫자를 넣는 조건은 같은 행,열 그리고 3X3 사각형안에 같은 숫자가 없다면 넣어볼 수 있다

그럼 3X3은 어떻게 확인할까?

 

현재 (x,y)에 있다고하면 우린 (3*(x/3),3*(y/3))을 포함하는 사각형 안에 들어가게 된다

총 /3을 한 9개의 사각형으로 들어가기 때문에 잘 생각해보면 저렇게 나온다

 

그래서 들어갈 수 있으면 true 아니라면 false로 return 시켜주면 된다!

 

소스코드 (C++)

#include <iostream>
#include <algorithm>
using namespace std;
int map[10][10];
 
bool check(int x, int y,int num) {
    for (int i = 0; i < 9; i++) if (map[x][i] == num || map[i][y]==num) return false;
    int r = 3 * (x / 3), l = 3 * (y / 3);
    for (int i = r; i < r + 3; i++) {
        for (int j = l; j < l + 3; j++) {
            if (map[i][j] == num) return false;
        }
    }
    return true;
}
 
bool solve(int pos) {
    if (pos == 81) return true;
    int x = pos / 9, y = pos % 9;
    if (map[x][y]) return solve(pos + 1);
    for (int i = 1; i <= 9; i++) {
        if (check(x, y, i)) {
            map[x][y] = i;
            if (solve(pos + 1)) return true;
            map[x][y] = 0;
        }
    }
    return false;
}
int main() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            scanf(" %d", &map[i][j]);
        }
    }
 
    solve(0);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            printf("%d ", map[i][j]);
        }puts("");
    }
}

 

소스코드(Java)

import java.util.Scanner;
 
public class Main {
    public static int[][] map = new int[10][10];
    public static boolean check(int x,int y,int num) {
        for(int i=0;i<9;i++) if(map[x][i]==num || map[i][y]==num)return false;
        int r= 3*(x/3),l=3*(y/3);
        for(int i=r;i<r+3;i++) {
            for(int j=l;j<l+3;j++) {
                if(map[i][j]==num) return false;
            }
        }
        return true;
    }
    public static boolean solve(int pos) {
        if(pos==81) return true;
        int x=pos/9,y=pos%9;
        if(map[x][y]!=0) return solve(pos+1);
        for(int i=1;i<=9;i++) {
            if(check(x,y,i)) {
                map[x][y]=i;
                if(solve(pos+1)) return true;
                map[x][y]=0;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) {
                map[i][j]=sc.nextInt();
            }
        }
        solve(0);
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) {
                System.out.print(map[i][j]+" ");
            }System.out.println();
        }
    }
}