[BOJ] 2580 스도쿠

문제보기

조건 1. 수평, 수직에 같은 숫자가 있는지 검사,

조건 2. 3x3안에 같은 숫자가 있는지 검사

=> 3x3행렬의 첫 숫자는 x/3*3, y/3*3으로 구할 수 있음.

map배열을 전부 돌면서 0인곳을 찾음,

0인곳에 1부터 9까지 대입하며 위 두 조건으로 검사.

맞는게 없으면 백트래킹 해서 다른 숫자를 넣어 다시 검사하기 위해 

map[x][y]에 0을 대입한다.

(0이 아니면 다른 좌표에서 검사할때 promising함수가 제대로 작동하지 않는다.)

---

#include <cstdio>

using namespace std;

int map[9][9];

void print_sudoku(){

for(int i = 0;i<9;i++){

for(int j = 0;j<9;j++){

printf("%d ",map[i][j]);

}

printf("\n");

}

}

bool promising(int x,int y,int n){

for(int i = 0;i<9;i++){

if(map[x][i] == n || map[i][y] == n)

return false;

}

int startX = (x/3)*3;

int startY = (y/3)*3;

for(int i = startX;i<startX+3;i++){

for(int j = startY;j<startY+3;j++){

if(map[i][j] == n)

return false;

}

}

return true;

}

void sudoku(){

int x = -1,y = -1;

for(int i = 0;i<9;i++){

for(int j = 0;j<9;j++){

if(map[i][j] == 0){

x = i,y = j;

break;

}

}

if(x != -1) break;

}

if(x == -1){

print_sudoku();

}

for(int i = 1;i<=9;i++){

if(promising(x,y,i)){

map[x][y] = i;

sudoku();

map[x][y] = 0;

}

}

}

int main(){

for(int i = 0;i<9;i++){

for(int j = 0;j<9;j++){

scanf("%d",&map[i][j]);

}

}

sudoku();

}