Written by Benoit Daloze @eregontp
on 

From an obfuscated Sudoku to Fibers and coroutines

TRICK is the Transcendental Ruby Imbroglio Contest for RubyKaigi, a contest for interesting & weird (transcendental, imbroglio) Ruby programs. I participated in the 2015 edition and won the 4th prize. In this article I explain my submission and detail interesting facts about it.

Not so obfuscated

This is my submission to TRICK 2015. It is actually now part of the ruby/ruby repository, like other winning entries of TRICK.

So what is this? Looks like a Sudoku puzzle in the middle. Running it shows:

1 9 4 2 3 8 7 6 5
3 7 2 6 5 1 4 8 9
8 5 6 7 4 9 2 3 1
7 8 1 3 6 4 5 9 2
4 2 3 9 7 5 8 1 6
5 6 9 8 1 2 3 7 4
6 4 8 1 2 7 9 5 3
9 3 5 4 8 6 1 2 7
2 1 7 5 9 3 6 4 8

1 9 7 2 3 8 4 6 5
3 4 2 6 5 1 7 8 9
8 5 6 7 4 9 2 3 1
7 1 8 3 6 4 5 9 2
4 2 3 9 7 5 8 1 6
5 6 9 8 1 2 3 7 4
6 8 4 1 2 7 9 5 3
9 3 5 4 8 6 1 2 7
2 7 1 5 9 3 6 4 8

Which are the 2 solutions to this specific Sudoku puzzle. Running after changing the puzzle also solves the modified puzzle. Giving an empty puzzle (all _), the program will print every possible completed sudoku puzzle. However, that might take a while.

So around the puzzle, in 302 characters, must be the code of the Sudoku solver. Let’s find out!

Mixing code and data

First we would like to separate the code (the solver) and the data (the puzzle). The first line shows how this is done. Here it is expanded:

class String
  def [](*a)
    $* << a
    b
  end
end

We redefine the [] operator on Strings. The code is in the String, and the data is the arguments of [].

The data is stored in $*, a global variable pointing to ARGV. So we push rows of digits to ARGV. Why on earth would we do that? It’s a code golf technique (minimizing the number of characters in the code) to use an array, without having to declare it (A=[] takes 4 characters).

The [] operator returns b, which is a method call to String#b, which returns the current String as binary. This is another code golf technique to return self for Strings but in only 1 character!

Next we have:

_=0;z="C=Fiber;s=$*;a=*0..8;l=C.new{e

_ is just a variable assigned to 0 to mark the holes in the puzzle input. More interesting, the variable z contains the concatenated code. And $* will be a two-dimensional array of the puzzle input.

The expanded code

Now we can print the code just before it is eval‘d, add spaces and indent it nicely:

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
32

C = Fiber
s = $*
a = *0..8
l = [
  C.new { exit },
  *a.product(a).select { |r,c|
    s[r][c] == 0
  }.map { |r,c|
    C.new {
      loop {
        (1..9).map { |n|
          C.yield(s[r][c] = n) if a.none? { |k|
            s[r][k] == n || s[k][c] == n || s[r-r%3+k%3][c-c%3+k/3] == n
          }
        }
        s[r][c] = 0
        C.yield
      }
    }
  },
  C.new {
    loop {
      puts s.map { |r| r * ' ' } << ''
      C.yield
    }
  }
]

c = l[i=1]
loop {
  c = l[i += c.resume ? 1 : -1]
}

That’s still quite hard to read. This is the time to introduce some fun facts about this solver:

This is interesting because a regular backtracking solver would recurse at least until its search depth, i.e., the number of empty cells in the input.

There is a big hint up there in line 1: Fiber. The solver uses Fibers (Ruby’s coroutines) to solve the Sudoku puzzle, one Fiber per empty cell.

Let’s dig further in small steps.

C = Fiber
s = $*
a = *0..8

So C is just a short name for Fiber, s is our Sudoku input and a is the same as (0..8).to_a, an Array of integers from 0 to 8 included.

The next chunk is the list of cells, commented inline:

l = [
  Fiber.new {
    exit # no more solutions to be found
  },
  *a.product(a).select { |r,c| # For every empty cell
    s[r][c] == 0
  }.map { |r,c|
    Fiber.new { # create a Fiber
      loop {
        (1..9).each { |n| # try every possibility
          if (0..8).none? { |k| # if there is no duplicate
              s[r][k] == n || # horizontally
              s[k][c] == n || # vertically
              s[r - r%3 + k%3][c - c%3 + k/3] == n # in the 3x3 box
            }
            s[r][c] = n # optimistically set it
            Fiber.yield(n) # next cell can continue
          end
        }

        s[r][c] = 0 # reset to 0 and backtrack
        Fiber.yield
      }
    }
  },
  Fiber.new { # the end of the list, we found a solution
    loop {
      puts s.map { |r| r * ' ' } << '' # print it
      Fiber.yield # and backtrack for more solutions
    }
  }
]

Note the r * ' ' which is the same as r.join(' ') to format a row. On the same line, << '' adds an element to the array passed to puts so we get an empty line between solutions.

Let’s see how we walk through that list of Fibers:

i = 1 # start at the first empty cell (0 is end)
c = l[i]
loop {
  # if we succeed, go further
  # if we fail, go back one step
  i += c.resume ? 1 : -1
  c = l[i]
}

c.resume returns the value given to Fiber.yield. When Fiber.yield is called without argument, resume returns nil. So we use Fiber.yield without argument to mean failure and any true value for success.

Further optimizations

Going back to this code a couple of years later, I noticed there are a few ways to make this even better:

So I could not resist, here is a 2018-refactored version:

S = <<PUZZLE.lines(chomp: true).map { |l| l.chars.map(&:to_i) }
19___8__5
__2_5__89
8_674____
_____4_92
_23_7_81_
56_8_____
____279_3
93__8_1__
2__5___48
PUZZLE

next_fiber = Fiber.new {
  loop {
    puts S.map { |r| r * ' ' } << ''
    Fiber.yield
  }
}

[*0..8].product([*0..8]).select { |r,c|
  S[r][c] == 0
}.reverse_each { |r,c|
  succ, next_fiber = next_fiber, Fiber.new {
    loop {
      (1..9).each { |n|
        if (0..8).none? { |k|
            S[r][k] == n || S[k][c] == n ||
            S[r - r%3 + k%3][c - c%3 + k/3] == n
          }
          S[r][c] = n
          succ.resume # We found a digit that works, try the next cell
        end
      }

      S[r][c] = 0
      Fiber.yield
    }
  }
}

next_fiber.resume

Conclusion

So here it is, a backtracking Sudoku solver never going deeper than 9 stack frames, using only infinite loops and no break, with no state other than a single copy of the puzzle!

Fibers – Ruby’s coroutines – enable us to avoid keeping explicit state (such as the current digit being tried for an empty cell) and transparently switch between different tasks, even in the middle of a method or block. That sounds like concurrency and that’s exactly what Fibers are. Due to the lack of preemption, they switch on demand and deterministically, which makes it easy to reason about. Concurrency in this context enables us to structure the program in a new and different way. Fibers are a very powerful tool and an interesting alternative to solve many problems.

What do you think? Do you find this solution elegant?

Maybe this article made you want to use Fibers more? I got the original idea from an inspiring paper on coroutines: Revisiting Coroutines by Ana Lúcia De Moura and Roberto Ierusalimschy.

If you liked this post or got some ideas from it, consider submitting to TRICK 2018! The deadline for submissions is March 31, 2018. The judge panel is very impressive and even includes Matz!

Bonus

Here is an even shorter and cleaner version of the solver, based on @Maumagnaguagno’s comment:

next_fiber = Fiber.new {
  loop {
    puts S.map { |r| r * ' ' } << ''
    Fiber.yield
  }
}

[*0..8].product([*0..8]) { |r,c|
  succ, next_fiber = next_fiber, Fiber.new {
    loop {
      (1..9).each { |n|
        if (0..8).none? { |k|
            S[r][k] == n || S[k][c] == n ||
            S[r - r%3 + k%3][c - c%3 + k/3] == n
          }
          S[r][c] = n
          succ.resume # We found a digit that works, try the next cell
        end
      }

      S[r][c] = 0
      Fiber.yield
    }
  } if S[r][c] == 0
}

next_fiber.resume