News

It's 2009, and one of the goals I'm setting for myself this year, is investigating if it's possible to apply the RETE pattern matching algorithm to rule-based sudoku solving. And if it is, implementing it.

...when I find the time, that is. I have a few ideas and a basic architecture worked out, but RETE is quite complex and I'm not sure if it's suited for sudoku solving. Right now I'm thinking it is, because the fact set (basically this is a list of all possible candidates for each field) changes incrementally during the solving process, which is the premise on which RETE was built. We'll see what gives!

Oh yeah, I'm going to call it rudoku² (pronounced "rudoku squared"), because that looks pretty cool.

UPDATE: the Rudoku² project is now on GitHub.

Overview

Rudoku is a hybrid sudoku solver with a modular architecture, written in Ruby. It supports both human-style (rule based) solving and bruteforcing techniques (using Ariadne's Thread). It exposes a rich API for the description of solving rules and bruteforcing strategies, and allows them to be implemented and plugged in easily.

The primary goal of Rudoku is experimentation and research; it was not designed to be fast or efficient (in fact, it isn't).

The terminology used to describe the algorithms largely corresponds with the one used on Sudopedia.

Currently implemented strategies

Solving rules

• Hidden single (several implementations)
• Direct elimination
• Naked subset (pair, triple, quad and generalised)
• Hidden subset (pair and generalised)
• Locked candidates: pointing & claiming
• Almost locked pair: line & square
• Scanning (two variations)
• X-Wing: several implementations, including a generalised version that encompasses locked candidates
• Swordfish
• Jellyfish
• Generalised fish: encompasses generalised X-Wing, Locked candidates, swordfish and jellyfish; it's also very slow ;)
• XY-Wing: square-line

Field selector strategies

• Simple: first field with the least candidates (several implementations)
• Random
• First
• Last
• Naked subset: field that's part of a naked subset
• Uber: first field with the least candidates and with the smallest total number of candidates in the containing houses
• Minimal house: first field with the smallest total number of candidates in the containing houses
• Hidden: looks for "almost hidden singles"

Candidate selector strategies

• First
• Last
• Uber: candidate which occurs the least in the containing houses
• Least common: candidate which occurs the least in the entire grid
• Most common: candidate which occurs the most in the entire grid
• Hidden: looks for "almost hidden singles"

Try it

You can try out the code by checking it out from SVN or downloading a snapshot, and running the test.rb file with

$ cd rudoku
$ ruby test.rb

You can tinker with its contents (or write your own testing code) to try out some other options. A few example grids and solvers are provided. The basics of the API are explained under Usage. A few other testing scripts are also available (gordon_test.rb, step_solver.rb).

Rudoku was developed on a Linux system, but it should run on other OSses without problems as long as a recent version of Ruby is installed.

Usage

To solve a grid, you will need at least the Sudoku itself and a Solver.

The Sudoku object can be created in several ways, but the easiest method is to use Sudoku.from_str. This takes in a string in the following format: "000400100000705032032000700001080605070000020503010800008000560650803000007001000" and returns the constructed object. The string is interpreted as a sequence of 9 rows, where zeros represent the empty fields. This format is often used to exchange grids in the sudoku community.

A Solver is an object that attempts to fill out all empty fields in a Sudoku. It consists of a ruleset (an Array of Rules), a FieldSelector and a CandidateSelector. The ruleset consists of the rules that will be applied to the sudoku, in order to eliminate candidates and, eventually, to solve it.

The FieldSelector and the CandidateSelector constitute the bruteforcing strategy that will be used when applying the rules doesn't eliminate any more candidates. The FieldSelector selects a field whose value will be guessed. The CandidateSelector selects a candidate from the list of remaining candidates of this field. This is the "guess".

If you don't need your Solver to support bruteforcing, you may omit the selectors when creating it. This probably means that your Solver will not be able to solve many sudokus, however. It is also possible to create a Solver with an empty ruleset; this will attempt to solve the Sudoku purely by backtracking.

Example:

sudoku = Sudoku.from_str("708000300000201000500000000040000026300080000000100090090600004000070500000000000")
solver = Solver.new([HiddenSingle, DirectElimination, LockedCandidatesPointing], UberFieldSelector, UberCandidateSelector)
solver.solve(sudoku, true) # the second parameter enables bruteforcing

It's easy to define your own Rules and Selectors. A Rule contains a code block (logic) which eliminates candidates from the sudoku's fields with the eliminate and set methods. A FieldSelector contains a code block which selects a field. A CandidateSelector contains a code block which selects a candidate from the field.

Example:

rule {
  id :my_rule
  name "my rule"
  desc "this is my rule"
  reason "eliminated :candidate because foo is :foo"
  
  logic {
    # write rule logic, using the 'eliminate' and 'set' methods
    # ...
    eliminate(field, candidate, :foo => "bar")
  }
}

field_selector {
  id :my_field_selector
  name "my field selector"
  desc "this is my field selector"

  logic {
    # write selection logic, using 'select'
    # ...
    select(field)
  }
}

candidate_selector {
  id :my_candidate_selector
  name "my candidate selector"
  desc "this is my candidate selector"

  logic {
    # write selection logic, using 'select'
    # ...
    select(candidate)
  }
}

You can find all currently implemented strategies in rules.rb, selectors.rb and candidate_selectors.rb. Feel free to implement more or refine the current implementations :)