fork download
copy 
  1. class Sudoku
  2. 	attr_accessor :run
  3. 	class Grid # 포인터like 사용을 위한 클래스
  4. 		attr_accessor :v
  5. 	end
  6.  
  7. 	def initialize
  8. 		@r, @c, @s=3.times.map { 9.times.map { [[]]*9 } } # 행,열,구역
  9. 		9.times { |i| 9.times { |j| @c[j][i] = @r[i][j] = Grid.new } }
  10. 		(0..8).step(3) { |rn| (0..8).step(3) { |cn|
  11. 			3.times { |i| 3.times { |j|
  12. 				@s[rn + (cn / 3)][i * 3 + j] = @r[rn + i][cn + j]
  13. 			} }
  14. 		} }
  15. 	end
  16.  
  17. 	def find_abl_num rn, cn # 해당 칸의 가능한 숫자 세트 탐색
  18. 		nums, sn = Array.new(9, true), rn / 3 * 3 + cn / 3 # true로 초기화,섹터 번호 구함
  19. 		9.times { |i| # 행(*r),열(*c),섹터(*s) 탐색
  20. 			nums[@r[rn][i].v - 1] = false if @r[rn][i].v > 0 # 채워져 있으면 마킹
  21. 			nums[@c[cn][i].v - 1] = false if @c[cn][i].v > 0
  22. 			nums[@s[sn][i].v - 1] = false if @s[sn][i].v > 0
  23. 		}
  24. 		[rn, cn, nums]
  25. 	end
  26.  
  27. 	def find_min_possible #가장 경우의 수가 적은칸의 세트 리턴
  28. 		size, minset = 10, nil
  29. 		9.times { |i| 9.times { |j|
  30. 			next if @r[i][j].v>0 # 채워진칸 무시
  31. 			temp = find_abl_num(i, j)
  32. 			nsize= temp[2].count(true)
  33. 			return [10, 10, 0] if nsize==0 # 빈칸인데 가능한 숫자가 없으면 오답 표시 리턴
  34. 			return temp if nsize==0 # 가능한 숫자가 하나일 경우 바로 리턴
  35. 			next unless nsize<size
  36. 			size, minset = nsize, temp
  37. 		} }
  38. 		minset
  39. 	end
  40.  
  41. 	def solve
  42. 		rn, cn, nums = find_min_possible # 가장 경우의 수가 적은 칸 탐색
  43. 		return true if nums==nil # 더 이상 빈칸이 없음을 뜻함. 풀린것!
  44. 		return false if rn>9 # 불가능한 칸이 있음을 뜻함
  45. 		(1..9).each { |i|
  46. 			next unless nums[i-1] # 불가능한 숫자는 스킵
  47. 			@r[rn][cn].v = i # 가능한 숫자를 채움
  48. 			return true if solve # 채운걸 풀어봄 그게 풀렸으면 탈출
  49. 		}
  50. 		# 채울 수 있는 숫자가 없거나 다 채워봤는데 안된거니까
  51. 		@r[rn][cn].v = 0 # 지우고
  52. 		false # 오답 리턴
  53. 	end
  54.  
  55. 	def run
  56. 		9.times { |i| gets.strip.chars.map(&:to_i).each_with_index { |n, j|
  57. 			@r[i][j].v=n
  58. 		} }
  59. 		puts solve ? '[Solved]' : '[No solution]'
  60. 		@r.each { |row| puts row.map(&:v).join }
  61. 	end
  62. end
  63.  
  64. Sudoku.new.run
Success #stdin #stdout 3.26s 10160KB
comments (?)
stdin
copy 
800000000
003600000
070090200
050007000
000045700
000100030
001000068
008500010
090000400
stdout
copy 
[Solved]
812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452
https://ideone.com/x0H3Ps
Sudoku solver
language:
Ruby (ruby 2.5.5)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!