What's new? | Help | Directory | Sign in
Google
rudoku
Modular hybrid sudoku solver
  
  
  
  
    
Show all Featured Downloads:
rudoku260320082335.zip
Join project
Project owners:
  sanderdieleman

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

Field selector strategies

Candidate selector strategies

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