News

5 June, 2008

A complete rewrite is coming this summer! I've learnt some interesting stuff about rule-based inference this semester and I'm planning to implement some of these ideas in a new version of Rudoku.

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 :)