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

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

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

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

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

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

Sudoku 클래스 메소드

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

2. find_abl_num rn, cn : rn,cn 칸에 가능한 숫자 셋트 리턴

3. find_min_possible : 가장 가능한 숫자가 적은 칸을 찾아서 리턴

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

class Sudoku
   attr_accessor :run
   class Grid # 포인터like 사용을 위한 클래스
        attr_accessor :v
   end

   def initialize
       @r, @c, @s=3.times.map { 9.times.map { [[]]*9 } } # 행,열,구역
        9.times { |i| 9.times { |j| @c[j][i] = @r[i][j] = Grid.new } }
       (0..8).step(3) { |rn| (0..8).step(3) { |cn|
              3.times { |i| 3.times { |j|
                    @s[rn + (cn / 3)][i * 3 + j] = @r[rn + i][cn + j]
              } }
       } }
   end

   def find_abl_num rn, cn # 해당 칸의 가능한 숫자 세트 탐색
        nums, sn = Array.new(9, true), rn / 3 * 3 + cn / 3 # true로 초기화,섹터 번호 구함
        9.times { |i| # 행(*r),열(*c),섹터(*s) 탐색
               nums[@r[rn][i].v - 1] = false if @r[rn][i].v > 0 # 채워져 있으면 마킹
               nums[@c[cn][i].v - 1] = false if @c[cn][i].v > 0
              nums[@s[sn][i].v - 1] = false if @s[sn][i].v > 0
       }
       [rn, cn, nums]
   end

   def find_min_possible #가장 경우의 수가 적은칸의 세트 리턴
        size, minset = 10, nil
       9.times { |i| 9.times { |j|
              next if @r[i][j].v>0 # 채워진칸 무시
               temp = find_abl_num(i, j)
              nsize= temp[2].count(true)
              return [10, 10, 0] if nsize==0 # 빈칸인데 가능한 숫자가 없으면 오답 표시 리턴
               return temp if nsize==0 # 가능한 숫자가 하나일 경우 바로 리턴
               next unless nsize<size
              size, minset = nsize, temp
       } }
       minset
   end

   def solve
       rn, cn, nums = find_min_possible # 가장 경우의 수가 적은 칸 탐색
        return true if nums==nil # 더 이상 빈칸이 없음을 뜻함. 풀린것!
       return false if rn>9 # 불가능한 칸이 있음을 뜻함
        (1..9).each { |i|
              next unless nums[i-1] # 불가능한 숫자는 스킵
               @r[rn][cn].v = i # 가능한 숫자를 채움
               return true if solve # 채운걸 풀어봄 그게 풀렸으면 탈출
        }
       # 채울 수 있는 숫자가 없거나 다 채워봤는데 안된거니까
        @r[rn][cn].v = 0 # 지우고
        false # 오답 리턴
   end

   def run
       9.times { |i| gets.strip.chars.map(&:to_i).each_with_index { |n, j|
              @r[i][j].v=n
       } }
       puts solve ? '[Solved]' : '[No solution]'
       @r.each { |row| puts row.map(&:v).join }
   end
end

Sudoku.new.run

 

http://ideone.com/x0H3Ps

결과

표준입력

800000000

003600000

070090200

050007000

000045700

000100030

001000068

008500010

090000400

표준출력

[Solved]

812753649

943682175

675491283

154237896

369845721

287169534

521974368

438526917

796318452

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