model

Documentation

Index

• Constants
• Variables
• type BitSet
  • func FromHex(s string) *BitSet
  • func (s *BitSet) And(o *BitSet) *BitSet
  • func (s *BitSet) AndNot(o *BitSet) *BitSet
  • func (s *BitSet) AsHex() string
  • func (s *BitSet) AsInts() []int
  • func (s *BitSet) Clear(pos int) *BitSet
  • func (s *BitSet) Clone() *BitSet
  • func (s *BitSet) Not() *BitSet
  • func (s *BitSet) Or(o *BitSet) *BitSet
  • func (s *BitSet) Set(pos int) *BitSet
  • func (s *BitSet) Size() int
  • func (s *BitSet) String() string
  • func (s *BitSet) Test(pos int) bool
• type Cell
  • func (c *Cell) Index() CellIndex
  • func (c *Cell) Neighbourhood(value int) *BitSet
  • func (c *Cell) NumConstraints() int
• type CellIndex
  • func (i CellIndex) BlockGroup() int
  • func (i CellIndex) BlockIndex() int
  • func (i CellIndex) ColumnGroup() int
  • func (i CellIndex) ColumnIndex() int
  • func (i CellIndex) GridIndex() int
  • func (i CellIndex) RowGroup() int
  • func (i CellIndex) RowIndex() int
  • func (i CellIndex) String() string
• type Coloring
  • func (c *Coloring) IsOn(cell *Cell) bool
  • func (c *Coloring) Set(cell *Cell, on bool, value int)
• type Grid
  • func NewGrid() *Grid
  • func (gd *Grid) Assert(i CellIndex, value int, reason string)
  • func (gd *Grid) Clone() *Grid
  • func (gd *Grid) Color(cell1 *Cell, cell2 *Cell, value int)
  • func (gd *Grid) Duration() time.Duration
  • func (gd *Grid) Enqueue(p Priority, f func())
  • func (gd *Grid) Reject(i CellIndex, value int, reason string)
  • func (gd *Grid) RemoveColoring(c *Coloring, cell *Cell, value int)
  • func (gd *Grid) ResetColoring(c *Coloring, value int)
  • func (gd *Grid) Solve() (bool, error)
  • func (gd *Grid) String() string
• type Group
  • func (g *Group) String() string
• type GroupType
• type Priority
• type ValueState

Constants

const (
	BLOCK_SIZE      = 3
	GROUP_SIZE      = 9
	NUM_CELLS       = 81
	NUM_GROUP_TYPES = 3
	NUM_GROUPS      = 27
	NUM_PRIORITIES  = 2
	MIN_CLUES       = 17
)

Variables

var (
	ColoringDisabled bool
)

var LogFile io.Writer = ioutil.Discard

var NoBacktracking = true

var Verbose bool = false

var VerifyUniqueness bool = true

Types

type BitSet

type BitSet struct {
	// contains filtered or unexported fields
}

A type that can efficiently perform logical operations on sets of 81 bits.

func FromHex

func FromHex(s string) *BitSet

Converts a hex representation into a bit set.

func (*BitSet) And

func (s *BitSet) And(o *BitSet) *BitSet

Answer a new bit set which contains the the intersection of the receiver and the specified set.

func (*BitSet) AndNot

func (s *BitSet) AndNot(o *BitSet) *BitSet

Answer a new bit set which includes only those bits of the receiver's set which are not in the specified set.

func (*BitSet) AsHex

func (s *BitSet) AsHex() string

Converts a bit set to a hex string in most-significant-bit first order.

func (*BitSet) AsInts

func (s *BitSet) AsInts() []int

Outputs the bit set as an array of the set bit positions

func (*BitSet) Clear

func (s *BitSet) Clear(pos int) *BitSet

Clear the specified but of the receiver

func (*BitSet) Clone

func (s *BitSet) Clone() *BitSet

Clone the bit set.

func (*BitSet) Not

func (s *BitSet) Not() *BitSet

Answer the complement of the receiving set.

func (*BitSet) Or

func (s *BitSet) Or(o *BitSet) *BitSet

Answer a new bit set which includes bits that are set in either of the receiver or the specified bit set.

func (*BitSet) Set

func (s *BitSet) Set(pos int) *BitSet

Set the specified bit of the receiver.

func (*BitSet) Size

func (s *BitSet) Size() int

The number of set bits.

func (*BitSet) String

func (s *BitSet) String() string

Outputs the bit set as a string of the set bit positions

func (*BitSet) Test

func (s *BitSet) Test(pos int) bool

True if the bit set contains the specified bit.

type Cell

type Cell struct {
	GridIndex   int
	Maybes      int
	Bits        int
	Value       *int
	ValueStates [GROUP_SIZE]ValueState
	Groups      [NUM_GROUP_TYPES]*Group
	Coloring    [GROUP_SIZE]*Coloring
}

func (*Cell) Index

func (c *Cell) Index() CellIndex

func (*Cell) Neighbourhood

func (c *Cell) Neighbourhood(value int) *BitSet

Answer the set of all cells in the intersecting units that can contain the specified value, not including the cell itself.

func (*Cell) NumConstraints

func (c *Cell) NumConstraints() int

type CellIndex

type CellIndex struct {
	Row    int
	Column int
}

func (CellIndex) BlockGroup

func (i CellIndex) BlockGroup() int

func (CellIndex) BlockIndex

func (i CellIndex) BlockIndex() int

func (CellIndex) ColumnGroup

func (i CellIndex) ColumnGroup() int

func (CellIndex) ColumnIndex

func (i CellIndex) ColumnIndex() int

func (CellIndex) GridIndex

func (i CellIndex) GridIndex() int

func (CellIndex) RowGroup

func (i CellIndex) RowGroup() int

func (CellIndex) RowIndex

func (i CellIndex) RowIndex() int

func (CellIndex) String

func (i CellIndex) String() string

type Coloring

type Coloring struct {
	// contains filtered or unexported fields
}

This structure is used to support coloring.

Two cells are linked by a coloring if they are the only two possible cells that can contain a particular value in a particular unit (group).

A coloring relationship is transitive. If a and b are linked in a coloring and b and c are linked in a coloring then a and c are linked by the same coloring

A cell can be a member of at most one coloring for a given value. When two cells that are currently a member of different colorings are linked, one of the colorings is merged into the other.

func (*Coloring) IsOn

func (c *Coloring) IsOn(cell *Cell) bool

func (*Coloring) Set

func (c *Coloring) Set(cell *Cell, on bool, value int)

type Grid

type Grid struct {
	Groups [NUM_GROUPS]*Group
	Cells  [NUM_CELLS]*Cell
	Values [GROUP_SIZE]*BitSet
	// contains filtered or unexported fields
}

A grid consists of cells and groups and state that tracks the number of asserted clues and a queue of pending heuristics.

func NewGrid

func NewGrid() *Grid

Initialize a new grid. No clues are asserted. All cells are initialized with references to their intersecting groups and vice versa.

Counters are initialized to maximum values for the

• counts by value by group (Group.Counts)
• maybes by cell (Cell.Maybes)

func (*Grid) Assert

func (gd *Grid) Assert(i CellIndex, value int, reason string)

Assert that the grid contains the specified value at the specified index. 'reason' contains an English language justification for the belief.

func (*Grid) Clone

func (gd *Grid) Clone() *Grid

Creates a clone of the receiving dest which duplicates all the state except for the work queue.

func (*Grid) Color

func (gd *Grid) Color(cell1 *Cell, cell2 *Cell, value int)

Pre-condition: both cells are a member of the same unit (group) and the number of possible cells for that value in that group is exactly 2.

func (*Grid) Duration

func (gd *Grid) Duration() time.Duration

func (*Grid) Enqueue

func (gd *Grid) Enqueue(p Priority, f func())

Enqueue a heuristic to try with the specified priority

func (*Grid) Reject

func (gd *Grid) Reject(i CellIndex, value int, reason string)

Assert that the grid does not contain the specified value at the specified cell index. 'reason' contains am English language justification for the belief.

func (*Grid) RemoveColoring

func (gd *Grid) RemoveColoring(c *Coloring, cell *Cell, value int)

func (*Grid) ResetColoring

func (gd *Grid) ResetColoring(c *Coloring, value int)

func (*Grid) Solve

func (gd *Grid) Solve() (bool, error)

Solve the grid by iterating over the work queue until NUM_CELLS are obtained or until there is nothing else to try.

Work is prioritsed so that cheaper heuristics are tried first and more expensive heuristics are only tried if there are no more cheap heuristics to try. Returns true if the solution is obtained, false otherwise.

func (*Grid) String

func (gd *Grid) String() string

type Group

type Group struct {
	Name   string
	Values [GROUP_SIZE]*BitSet
	Cells  [GROUP_SIZE]*Cell
	Mask   *BitSet
	// contains filtered or unexported fields
}

func (*Group) String

func (g *Group) String() string

type GroupType

type GroupType int

const (
	ROW GroupType = 0 + iota
	COLUMN
	BLOCK
)

type Priority

type Priority int

const (
	IMMEDIATE Priority = iota
	DEFERRED
)

type ValueState

type ValueState int

const (
	MAYBE ValueState = 0 + iota
	NO
	YES
)