java - sudoku 코딩.

여기서 스도쿠는 9X9 사이즈로 한다. 

스도쿠 규칙 

1) 같은 열에 같은 숫자가 중복되면 안됨.

2) 같은 행에 같은 숫자가 중복되면 안됨.

3) 3X3 정사각형 안에 같은 숫자가 중복되면 안됨.

 

[아이디어]

 

우선 back tracking 알고리즘을 사용하기로 한다.

0으로 초기화 되 있는 9X9 사이즈의 배열을 선언하고, 그 배열을 스도쿠 규칙에 맞게 채우는

함수를 호출 시킨다. 이 함수의 역할은 배열에서 0의 값을 갖는 좌표를 찾아 그 안에 수를 대입해보고

이 때 이 수가 promising한지 판단. promising하다면 이 수를 채운 배열을 가지고 재귀호출하여 다음 단계로 넘어간다.

이때 중요한 것은 숫자를 채우는 조건이 값이 비어있는 경우 이므로 몇번의 단계 호출 후에 잘못된 것을 알았을 때 그 지점에서 함수가 종료된다면 잘못된 값으로 채워진 배열은 남게 되므로 다음단계로 넘어갈때 어떤 수를 채운 배열을 보냈다면 넘어간 후 다시 그 수를 0으로 초기화 시켜서 backtracking이 가능하도록 설계한다.

promising의 조건은 스도쿠 규칙과 맞게 짜면된다. 이때 promising 함수는 promising한 경우에 대해 참값을 반환하는 boolean함수이다.

 

 

 

 

import java.util.*;
public class Mainapp {

static final int M = 9;

static int[][] a = new int[M][M]; //M x M 행렬 만듬.

static boolean stop;

static boolean promising(int num, int x, int y) { //어떤 숫자 num이 들어왔을 때 좌표 x,y에 대해서 promising 한지 조사.
int rx = x / 3 * 3, ry = y / 3 * 3; // 3 X 3의 배열 내에서 x ,y 좌표가 속한 사각형의 시작 위치를 나타냄. ex) 2,3의 경우 0,3이 시작 위치
for (int i = 0; i < 9; i++)
if (a[x][i] == num || a[i][y] == num) return false; //정해진 좌표 x,y 에 대해서 그 행과 열에 대해 주어진 num과 같은 경우가 있는지 비교. 있으면 false
for (int i = rx; i < rx + 3; i++)
for (int j = ry; j < ry + 3; j++)
if (a[i][j] == num) return false; //3x3 사각형 범위 내에서 같은것이 있는지 비교. 있으면 false.
return true; // 모든 case에 대해 비교 결과 promising 한 경우 true 반환.
}
static void sudoku() {
if (stop) return;
int x = -1, y = -1; //x,y를 -1로 설정한 이유는 빈공간을 찾지 못했을 경우를 표시하기 위함.

boolean find =true;

for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (a[i][j] == 0) { //현재 a값이 0인 경우에 값이 들어올 수 있는 상태이므로 0의 값을 갖는 좌표를 x,y에 기록.
x = i;
y = j;
find =false;
break;
}
}
if(!find){break;}
}

if (x==-1) {
stop = true; // 비어진 공간이 없는경우 스도쿠가 완성 된 것이므로 다시 함수가 호출 되었을 때 작업을 수행하지 않고 끝내야함. 따라서 stop시킴.
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
System.out.print(a[i][j]+" ");
System.out.println();
}
return;
}

for (int i = 1; i < M+1; i++) { // 찾은 좌표애 대해 1부터 M까지의 값을 대입하면서 promising 한지 조사.
if (promising(i,x,y)) {
a[x][y] = i; //만약 promisng 한 경우 그 값을 a에 저장하고
sudoku(); //다음 단계로 보냄.
a[x][y] = 0; //다음 단계를 타고 올라가서 만약 실패할 경우 현재 위치로 돌아와서 다른 값을 넣어 봐야 하므로 a를 0으로 초기화.
}
}
}
public static void main(String[] args) {

for(int i=0; i<M; i++)
for(int j=0; j<M; j++)
a[i][j] = 0;
sudoku();

}
}