[Java] 창작 스도쿠 푸는 알고리즘

이 알고리즘으로 UI를 구현한 Sudoku solver는 http://sunnyholic.com/100 여기 있습니다.

C++로 동일하게 작성한 코드는 http://sunnyholic.com/81 입니다.

빈 칸중 들어갈 수 있는 수의 경우가 제일 적은 칸을 선택하여 수를 삽입한 뒤 재귀적으로 풀고

오답이면 백트래킹 하고 정답이 나오면 종료하는 알고리즘 입니다.

함수 메인 제외 5개

1. 생성자 함수 : 간편하게 행 열 섹터를 순차적으로 순회하기 위해 미리 순회 순서를 찾아놓음.

2. sizeofNumset(Set set) : 가능한 숫자 셋트에서 그 숫자들을 세어 개수를 리턴

3. findAblNum(int rn,int cn) : (rn,cn)칸에 가능한 숫자 셋트 리턴

4. findMinPossible() : 가장 가능한 숫자가 적은 칸을 찾아서 리턴

5. solve() : 재귀함수로 문제 탐색. 정답시 true 오답시 false 리턴

import java.util.Scanner;

 

public class Sudoku_rec {

   class Grid {  //포인터like 사용을 위한 클래스

       public int v;

       Grid(int n) {v = n;}

   }

   class Set {

       int rn, cn;

       boolean[] num;

       Set(int rn, int cn) {

          this.rn = rn;

          this.cn = cn;

          num = new boolean[] { true, true, true, true, true, true, true,

                 true, true };

       }

   };

 

   Grid r[][] = new Grid[9][9]; // 행

   Grid c[][] = new Grid[9][9]; // 열

   Grid s[][] = new Grid[9][9]; // 구역

 

   /* 본격 스도쿠 풀이 함수 */

   Sudoku_rec() {   //열,행,섹터 포인터

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

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

              c[j][i] = r[i][j] = new Grid(0);

       for (int rn = 0; rn < 9; rn += 3)

          for (int cn = 0; cn < 9; cn += 3)

              for (int i = 0; i < 3; i++)

                 for (int j = 0; j < 3; j++)

                    s[rn + (cn / 3)][i * 3 + j] = r[rn + i][cn + j];

   }

 

   int sizeofNumset(Set set) { // 가능한 숫자 개수 카운터

       int cnt = 0;

       for (boolean b : set.num)

          if (b) cnt++;

       return cnt;

   }

 

   Set findAblNum(int rn, int cn) { // 해당 칸의 가능한 숫자 세트 탐색

       Set nums = new Set(rn, cn); // true로 초기화

       int sn = rn / 3 * 3 + cn / 3; // 섹터 번호 구함

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

          // 행(*r),열(*c),섹터(*s) 탐색

          if (r[rn][i].v > 0) // 채워져 있으면

              nums.num[r[rn][i].v - 1] = false; // 마킹

          if (c[cn][i].v > 0)

              nums.num[c[cn][i].v - 1] = false;

          if (s[sn][i].v > 0)

              nums.num[s[sn][i].v - 1] = false;

       }

       return nums;

   }

 

   Set findMinPossible() { // 가장 경우의 수가 적은칸의 세트 리턴

       int size = 10;

       Set minset = null;

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

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

              if (r[i][j].v > 0)

                 continue; // 채워진칸 무시

              Set temp = findAblNum(i, j);

              int nsize = sizeofNumset(temp);

              if (nsize == 0) // 빈칸인데 가능한 숫자가 없으면

                 return new Set(10, 10); // 오답 표시 리턴

              else if (nsize == 1) // 가능한 숫자가 하나일 경우 바로 리턴

                 return temp;

              else if (nsize < size) {

                 size = nsize;

                 minset = temp;

              }

          }

       }

       return minset;

   }

 

   boolean solve() {

       Set set = findMinPossible(); // 가장 경우의 수가 적은 칸 탐색

       if (set == null) // 더 이상 빈칸이 없음을 뜻함.

          return true; // 풀린것!

       if (set.rn > 9) // 불가능한 칸이 있음을 뜻함

          return false;

       for (int i = 1; i <= 9; i++) { // 숫자 1~9를 채우는 부분

          if (!set.num[i - 1])

              continue; // 불가능한 숫자는 스킵

          r[set.rn][set.cn].v = i; // 가능한 숫자를 채움

          if (solve()) // 채운걸 풀어봄

              return true; // 그게 풀렸으면 탈출

       }

       // 채울 수 있는 숫자가 없거나 다 채워봤는데 안된거니까

       r[set.rn][set.cn].v = 0; // 지우고

       return false; // 오답 리턴

   }

 

   void run() {

       Scanner sc = new Scanner(System.in);

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

          char input[] = sc.nextLine().toCharArray();

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

              r[i][j].v = input[j] - '0';

       }

       sc.close();

      

       System.out.println(solve() ? "[Solved]" : "[No solution]");

      

       //결과 출력

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

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

              System.out.print(r[i][j].v);

          System.out.println();

       }

   }

 

   public static void main(String[] args) {

       new Sudoku_rec().run();

   }

}

http://ideone.com/ab4xF8

결과

표준입력

800000000

003600000

070090200

050007000

000045700

000100030

001000068

008500010

090000400

표준출력

[Solved]

812753649

943682175

675491283

154237896

369845721

287169534

521974368

438526917

796318452

부연 설명은 C++글을 봐주세요.