티스토리 뷰

이 알고리즘으로 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.times { |i9.times { |j@c[j][i@r[i][jGrid.new } }
       (
0..8).step(3) { |rn(0..8).step(3) { |cn|
              
3.times { |i3.times { |j|
                    
@s[rn (cn 3)][j@r[rn i][cn j]
              } }
       } }
   
end

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

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

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

   def 
run
       
9.times { |igets.strip.chars.map(&:to_i).each_with_index { |nj|
              
@r[i][j].v=n
       
} }
       puts solve 
'[Solved]' '[No solution]'
       
@r.each { |rowputs 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++글을 봐주세요.

'프로그래밍/알고리즘 > Ruby' 카테고리의 다른 글

[Ruby] 창작 스도쿠 푸는 알고리즘  (0) 2016.08.02
댓글
댓글쓰기 폼
공지사항
Total
335,555
Today
46
Yesterday
157
링크
«   2018/12   »
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          
글 보관함