API Reference¶

Library with a builtin CLI frontend to solve sudoku puzzles using a backtracking algorithm.

In order to solve a sudoku puzzle efficiently Knuth’s Algorithm-X is used after the exact cover problem has been applied to it.

Even this library was actually written to solve sudokus, you can use the core modules to implement your own solver for any kind of exact cover problems.

Candidates and Constraints¶

A candidate in terms of sudokus is simply a number in one of the cells in the grid. Those candidates are related to one or more of the constraints of the sudoku. In total, there exists \(9^3 = 729\) candidates since each of the 81 cells can contain 9 numbers and \(9^2 * 4 = 324\) constraints that cover all four kind of constraints (Row-Number, Column-Number, Block-Numer and Row-Column).

The API doesn’t force you to use some dedicated data structures to describe the sudoku puzzle. Instead you can use simple strings that identify the candidate and constraints. When you want to use the core API to apply it to another exact cover problem, you can define your own format pattern. However, if you want to use it to solve a sudoku, you have to obey following pattern:

For candidates:

# e.g. first column, first row, number 1
# R1C1#1
R{rowNumber}C{columnNumber}#{number}

For constraints:

R{rowNumber}#{number}               # e.g. R#1
C{columnNumber}#{number}            # e.g. C#1
B{blockNumber}#{number}             # e.g. B#1
R{rowNumber}C{columnNumber}         # e.g. R1C1

sudokusolver.importer¶

Provides functions to parse sudoku puzzle from a text file written in following format:

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

5,9,3,  _,6,8,  2,_,1
_,7,2,  _,1,3,  _,_,9
6,1,_,  9,7,2,  _,3,5

_,8,6,  2,3,_,  9,1,4
1,5,4,  _,9,6,  8,2,3
_,3,9,  8,4,1,  5,_,_

sudokusolver.importer.imp_candidates(path: str) → tuple[source]¶

Parses a sudoku puzzle and returns the containing numbers as strings in the form of R{rowNumber}C{columnNumber}#{number}. For example R1C1# says that in the cell of the first row and first column the number one was written into.

Parameters:	path – path to the file containing the sudoku puzzle
Returns:	a tuple of strings containing the read numbers

sudokusolver.visualizer¶

Provides mechanism to visualize sudoku puzzles.

sudokusolver.visualizer.visualize(candidates: str)[source]¶

Prints the sudoku puzzle as given as a list of candidates (e.g. R1C1#1) on the standard output.

Parameters:	candidates – sequence of strings representing a number in a cell

sudokusolver.solver¶

Module used to solve sudoku puzzles.

sudokusolver.solver.solve(fixed_candidates, rule_description=None) → list[source]¶

Solves by default a sudoku puzzle by applying the exact cover problem to it and using the Algorithm-X by Donald Knuth. The puzzle is described here as sequence of strings describing the fixed candidates:

R{rowNumber}C{columnNumber}#{number}

The return value is also list of candidates which solve the sudoku.

Note

The second argument can be used to solve other exact cover problems than sudoku. See documentation for further information.

Parameters:	fixed_candidates – list of strings describing the filled in cells with their numbers rule_description – lookup for candidates and constraints of sudoku
Returns:	list of strings describing the candidates solving the sudoku puzzle

sudokusolver.model¶

Provides data structures to model an exact cover problem (e.g. sudoku).

node¶

Provides Nodes and ReferenceNodes being part of the ConstraintMatrix.

class sudokusolver.model.node.Node(candidate, covered_constraint, row_ref_node=None, column_ref_node=None)[source]¶

Simple data structure representing a node within a ConstraintMatrix. It know its left, bottom, right and top neighbour. In addition, it is also aware of the row and column it belongs to.

static connect(a: sudokusolver.model.node.Node, b: sudokusolver.model.node.Node, how: str)[source]¶: Joins the given nodes vertically or horizontally together.

static disconnect(node: sudokusolver.model.node.Node, how: str)[source]¶: Disjoins the given node vertically or horizontally from its neighbours.

class sudokusolver.model.node.RowReferenceNode(candidate)[source]¶

Special kind of node that refers another rode. Used by the ConstraintMatrix to address rows and iterate through their nodes.

get_last_node()[source]¶: Returns the last node of the row represented by this RowReferenceNode.

class sudokusolver.model.node.ColumnReferenceNode(covered_constraint)[source]¶

Special kind of node that refers another rode. Used by the ConstraintMatrix to address columns and iterate through their nodes.

get_last_node() → sudokusolver.model.node.Node[source]¶: Returns the last node of the column represented by this ColumnReferenceNode.

class sudokusolver.model.node.MatrixHeadReferenceNode[source]¶

Special kind of node that refers to ColumnReferenceNodes and RowReferenceNodes. Used by the ConstraintMatrix to itereate through its columns and rows.

get_column_ref_node_iterator()[source]¶: Returns iterator iterating through the ColumnRerefernceNodes

get_last_column_ref_node() → sudokusolver.model.node.Node[source]¶: Returns the last ColumnReferenceNode in the matrix otherwise itself

get_last_row_ref_node() → sudokusolver.model.node.Node[source]¶: Returns the last RowReferenceNode in the matrix otherwise itself

get_row_ref_node_iterator()[source]¶: Returns iterator iterating through the RowReferenceNodes

iterators¶

Provides iterators to iterate through the nodes of the rows and columns of the ConstraintMatrix.

class sudokusolver.model.iterators.ColumnIterator(start, reversed=False)[source]¶: Iterates through a sequence of vertically connected nodes.

class sudokusolver.model.iterators.RowIterator(start, reversed=False)[source]¶: Iterates through a sequence of horizontally connected nodes.

constraintmatrix¶

class sudokusolver.model.constraintmatrix.ConstraintMatrix[source]¶

A two dimensional matrix used to solve an exact cover problem. The constraints are mapped by the columns and the candidates by the rows. Each node in the matrix knows its top, left, bottom and right neighbour. A node exists only in case the candidate of the row fulfills the constraint of the column.

Special nodes, so called ReferenceNodes, point to the first node of a row or a column and are used to itereate through their nodes. Those ReferenceNodes can be accessed through the MatrixHeadReferenceNode which points on its right to the first ColumnReferenceNode and on its bottom to the first RowRefereneNode of the matrix.

add(candidate=None, covered_constraints=[])[source]¶

creates and adds a new node to the matrix labeled with the provided candidate and constraints.

Parameters:	candidate (str) – candidate name to be attached to the Node covered_constraints (list) – constraint names to be attached to the Node

candidates_exist() → bool[source]¶: Returs True if any candidate is left, otherwise False

cover(row_ref_node)[source]¶

Covers the candidate itself and all satisfiying constraints as well as the other candidates that would satisfy those.

Removes complete rows and columns according the Algorithm-X:

For each column j such that Ar, j = 1
  for each row i such that Ai, j = 1
      delete row i from matrix A
  delete column j from matrix A

Use uncover to undo the changes made by this operation.

get_next_constraints_candidates() → list[source]¶

Returns a sequence of RowReferenceNodes(candidates) fulfilling the next automatically chosen ColumnReferenceNode(constraint)

Returns:	list of RowReferenceNodes

has_satisfied_all_constraints() → bool[source]¶: Returns True of all contraints has been satisfied, otherwise False

head_ref_node¶: Returns the MatrixHeadReferenceNode. Can be used to iterate through the RowReferenceNodes and ColumnReferenceNodes

uncover()[source]¶: Reverts all changes done by cover operation