123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102 |
- #!/usr/bin/ruby
- # Recursive brute-force Sudoku solver.
- # See also:
- # https://rosettacode.org/wiki/Sudoku
- # https://en.wikipedia.org/wiki/Sudoku
- func check(i, j) is cached {
- var (id, im) = i.divmod(9)
- var (jd, jm) = j.divmod(9)
- jd == id && return true
- jm == im && return true
- (id//3 == jd//3) &&
- (jm//3 == im//3)
- }
- var lookup = []
- for i in (^81), j in (^81) {
- lookup[i][j] = check(i, j)
- }
- func solve_sudoku(callback, grid) {
- var digits = @(1..9)
- func {
- grid.each_kv {|i,v|
- v && next
- var t = Set(grid.grep_kv {|j| lookup[i][j] }...)
- digits.each {|d|
- t.has(d) && next
- grid[i] = d
- __FUNC__()
- grid[i] = 0
- }
- return nil
- }
- callback(grid)
- }()
- }
- func display_grid(grid) {
- say "Solution:"
- for i in ^grid {
- print "#{grid[i]} "
- print " " if ( 3 -> divides(i+1))
- print "\n" if ( 9 -> divides(i+1))
- print "\n" if (27 -> divides(i+1))
- }
- }
- var sudoku_board = %n(
- 5 3 0 0 2 4 7 0 0
- 0 0 2 0 0 0 8 0 0
- 1 0 0 7 0 3 9 0 2
- 0 0 8 0 7 2 0 4 9
- 0 2 0 9 8 0 0 7 0
- 7 9 0 0 0 0 0 8 0
- 0 0 0 0 3 0 5 0 6
- 9 6 0 0 1 0 3 0 0
- 0 5 0 6 9 0 0 1 0
- )
- sudoku_board = %n(
- 0 0 0 8 0 1 0 0 0
- 0 0 0 0 0 0 0 4 3
- 5 0 0 0 0 0 0 0 0
- 0 0 0 0 7 0 8 0 0
- 0 0 0 0 0 0 1 0 0
- 0 2 0 0 3 0 0 0 0
- 6 0 0 0 0 0 0 7 5
- 0 0 3 4 0 0 0 0 0
- 0 0 0 2 0 0 6 0 0
- ) if false
- sudoku_board = %n(
- 8 0 0 0 0 0 0 0 0
- 0 0 3 6 0 0 0 0 0
- 0 7 0 0 9 0 2 0 0
- 0 5 0 0 0 7 0 0 0
- 0 0 0 0 4 5 7 0 0
- 0 0 0 1 0 0 0 3 0
- 0 0 1 0 0 0 0 6 8
- 0 0 8 5 0 0 0 1 0
- 0 9 0 0 0 0 4 0 0
- ) if false
- solve_sudoku(display_grid, sudoku_board)
|