puzzle

Documentation

Overview

Package puzzle provides a model for Sudoku puzzles and operations on them. It provides both a golang API and a web API to the puzzles.

Sudoku puzzles are made of squares which are either empty (represented with a 0 value) or have an assigned value between 1 and the side length of the puzzle (inclusive). The squares are designated by indices that start at 1 and increase left-to-right, top-to-bottom (English reading order).

For each empty square in a puzzle, the implementation maintains a set of possible values the square can be assigned without conflicting with other squares. Exactly which other squares might conflict depends on the puzzle's geometry, which determines which groups of squares are constrained to have the full range of possible values.

All Sudoku geometries have a group for each row and column. The standard geometry, called here the Sudoku geometry, additionally requires the side length of a puzzle to be a perfect square. This produces side-length non-overlapping sub-squares (aka tiles) in the the overall puzzle, each of which is also a group.

Another common Sudoku variant, called here the Dudoku geometry, instead uses rectangular tiles whose width is one greater than its height. This leads to sides of the overall square being equal in length to the area of one tile (e.g, 4x3 tiles and a 12x12 square).

Another Sudoku variant, not yet implemented, uses the Sudoku geometry but adds the diagonals as two additional groups.

If a square in a group is the only possible location for a needed value, we say that the square is bound by the group, and the implementation tracks these bound squares. If an assignment of some other value is made to that square, the puzzle will not be solvable, and is said to have errors. Errors in puzzles can also arise from assignments of the same value to multiple squares in a group. The implementation will not perform operations on puzzles with errors.

Index

• Constants
• type Choice
• type Content
• type Error
  • func (e Error) Error() string
• type ErrorAttribute
• type ErrorCondition
• type ErrorData
• type ErrorScope
• type ErrorStructure
• type GroupID
  • func (gid GroupID) String() string
• type Puzzle
  • func New(summary *Summary) (*Puzzle, error)
  • func NewHandler(w http.ResponseWriter, r *http.Request) (*Puzzle, error)
  • func (p *Puzzle) Assign(choice Choice) (*Content, error)
  • func (p *Puzzle) AssignHandler(w http.ResponseWriter, r *http.Request) (*Content, error)
  • func (p *Puzzle) Copy() (*Puzzle, error)
  • func (p *Puzzle) Solutions() ([]Solution, error)
  • func (p *Puzzle) SolutionsHandler(w http.ResponseWriter, r *http.Request) error
  • func (p *Puzzle) State() (*Content, error)
  • func (p *Puzzle) StateHandler(w http.ResponseWriter, r *http.Request) error
  • func (p *Puzzle) String() (result string)
  • func (p *Puzzle) Summary() (*Summary, error)
  • func (p *Puzzle) SummaryHandler(w http.ResponseWriter, r *http.Request) error
• type Solution
• type Square
• type Summary

Constants

const (
	SudokuGeometryName = "sudoku"
	DudokuGeometryName = "dudoku"
)

const (
	GtypeRow      = "row"
	GtypeCol      = "column"
	GtypeTile     = "tile"
	GtypeDiagonal = "diagonal"
)

GType (group type) constants. These are human-readable but not localized. As the implementation supports new geometries, more group types may be added.

Types

type Choice

type Choice struct {
	Index int `json:"index"`
	Value int `json:"value"`
}

A Choice assigns a value to a cell. The cell is referred to by its index.

type Content

type Content struct {
	Squares []Square `json:"squares"`
	Errors  []Error  `json:"errors,omitempty"`
}

A Content structure gives the details of the puzzle's squares and errors. When you ask for the Summary of a puzzle, you get a Content structure that contains all of the squares, and you get all of the known errors. When you assign to a puzzle, you get a Content structure with only the squares that were updated by the assignment, and any errors that were noticed during the assignment.

type Error

type Error struct {
	Scope     ErrorScope     `json:"scope"`
	Structure ErrorStructure `json:"structure,omitempty"`
	Condition ErrorCondition `json:"condition,omitempty"`
	Attribute ErrorAttribute `json:"attribute,omitempty"`
	Values    ErrorData      `json:"values,omitempty"`
	Message   string         `json:"message,omitempty"` // custom message
}

An Error describes a problem with a puzzle or a requested operation. It can produce an error message in English, but its main function is to support localized error messaging by clients. It tells the client "this thing failed to meet this condition", and provides supplemental details about the thing and the condition.

func (Error) Error

func (e Error) Error() string

Return an error string from an Error. If the Error has a pre-canned message, this will use it, otherwise it will produce an appropriate (English, non-localized) message.

type ErrorAttribute

type ErrorAttribute int

An ErrorAttribute names the attribute that has a problem.

const (
	UnknownAttribute ErrorAttribute = iota
	DecodeAttribute
	EncodeAttribute
	URLAttribute
	LocationAttribute
	NamedAttribute
	GeometryAttribute
	IndexAttribute
	ValueAttribute
	AssignedValueAttribute
	BoundValueAttribute
	RemovedValueAttribute
	RemovedValuesAttribute
	RetainedValuesAttribute
	PuzzleSizeAttribute
	SideLengthAttribute
	PuzzleAttribute
	SummaryAttribute
	MaxAttribute
)

Constants for the various attribute codes.

type ErrorCondition

type ErrorCondition int

The ErrorCondition is the predicate that the scope/attribute/value failed to satisfy. There are a bunch of known, named predicates and then a "general" (arbitrary English string) predicate for runtime errors.

const (
	UnknownCondition ErrorCondition = iota
	GeneralCondition
	TooLargeCondition
	TooSmallCondition
	DuplicateAssignmentCondition
	NotInSetCondition
	NoPossibleValuesCondition
	NoGroupValueCondition
	DuplicateGroupValuesCondition
	UnknownGeometryCondition
	NonSquareCondition
	NonRectangleCondition
	InvalidPuzzleAssignmentCondition
	WrongPuzzleSizeCondition
	InvalidArgumentCondition
	MismatchedSummaryErrorsCondition
	MaxCondition
)

Constants for the various error conditions

type ErrorData

type ErrorData []interface{}

The ErrorData provides details about the thing that failed to meet the predicate (such as the value of an attribute) as well as the predicate itself (such as minimum required values).

Every item in the slice of ErrorData is required to be JSON-serializable, so it can be returned to web clients. Sadly, there is no good way to express this condition in a way the compiler can check it, so we just have to rely on implementors to "do the right thing" and check the condition at runtime.

type ErrorScope

type ErrorScope int

An ErrorScope explains what type of thing the error is referring to. In the case of client errors, this is either a client-supplied argument or some aspect of the resulting puzzle. In the case of internal logic errors, this is where in the code the failure occurred.

const (
	UnknownScope ErrorScope = iota
	RequestScope
	ArgumentScope
	GeometryScope
	GroupScope
	SquareScope
	InternalScope
	MaxScope
)

Constants for the various error scopes.

type ErrorStructure

type ErrorStructure int

The ErrorStructure denotes whether the problem is in the overall Scope, an Attribute of the Scope, or the value of an Attribute of the Scope.

const (
	UnknownStructure ErrorStructure = iota
	ScopeStructure
	AttributeStructure
	AttributeValueStructure
	MaxStructure
)

Constants for the various structure codes.

type GroupID

type GroupID struct {
	Gtype string `json:"gtype"`
	Index int    `json:"index"`
}

A GroupID names a row, column, tile, diagonal, or other set of constrained squares, collectively called groups. The numbering and cardinality for each type of group is 1-based and determined by the puzzle geometry.

func (GroupID) String

func (gid GroupID) String() string

Group IDs implement Stringer

type Puzzle

type Puzzle struct {
	Metadata map[string]string
	// contains filtered or unexported fields
}

A Puzzle is our puzzle implementation. The puzzle's Metadata is a convenience for clients who manipulate puzzles; it is ignored by the puzzle operations.

The zero Puzzle value does not represent a valid puzzle; always use New to create one. Also, do not try to copy puzzles by assigning them, use Copy instead.

func New

func New(summary *Summary) (*Puzzle, error)

New takes a puzzle summary and returns the puzzle with that summary. In the case of puzzle summaries with no errors, this will actually produce a puzzle with exactly the same summary. But in the case of a puzzle summary with errors, that won't necessarily be true, because the summary may have come via incrementally building the puzzle assignment by assignment, and in that case rebuilding the puzzle from its current values will typically find more errors (because every constraint will be checked, not just the ones that were violated by the last assignment). So if you pass a summary with errors to this function, we will replace the constructed puzzle's errors with the summary's errors, to ensure that the resulting puzzle has the summary you expect.

func NewHandler

func NewHandler(w http.ResponseWriter, r *http.Request) (*Puzzle, error)

NewHandler is a POST handler that reads a JSON-encoded Summary value from the request body calls New on the argument values to create a new Puzzle. The new Puzzle's State is sent as a 200 response, and the new puzzle itself is returned to the golang caller. If the return value from New is an error, then the error is sent as a 400 response and also returned to the caller.

If we can't decode the posted Summary, we send a 400 reponse and return the error to the caller.

If we can't encode the response to the client (which should never happen), then the client gets an error response and the golang caller gets both the puzzle and the encoding Error (as a signal that the client didn't get the correct response).

func (*Puzzle) Assign

func (p *Puzzle) Assign(choice Choice) (*Content, error)

Assign a choice to a puzzle, returning an Content for the puzzle. If the puzzle is already unsolvable, the target square is already assigned, or the assigned index or value are out of range, the puzzle isn't updated and an Error is returned.

func (*Puzzle) AssignHandler

func (p *Puzzle) AssignHandler(w http.ResponseWriter, r *http.Request) (*Content, error)

AssignHandler is a POST handler that assigns a posted choice to a puzzle. The poster and the caller both get the Content object returned from the assignment (or the error).

If we can't decode the posted choice, we send a 400 reponse and return the error to the caller.

If we can't encode the response to the client (which should never happen), then the client gets an error response and the golang caller gets both the update and the encoding Error (as a signal that the client didn't get the update).

func (*Puzzle) Copy

func (p *Puzzle) Copy() (*Puzzle, error)

Copy returns a copy of the wrapped puzzle (no shared structure)

func (*Puzzle) Solutions

func (p *Puzzle) Solutions() ([]Solution, error)

Solutions finds all solutions to a given puzzle. The puzzle is copied first, so it's not altered during the solutions process

func (*Puzzle) SolutionsHandler

func (p *Puzzle) SolutionsHandler(w http.ResponseWriter, r *http.Request) error

SolutionsHandler responds with the Puzzle's solutions (or the Error produced by computing the puzzle's solutions). If we can't encode the response to the client successfully, we give both the client and the golang caller an Error response.

func (*Puzzle) State

func (p *Puzzle) State() (*Content, error)

State returns the entire content of the puzzle. The return value does not share underlying storage with the puzzle, so future changes to the puzzle do not affect prior returns from this function.

func (*Puzzle) StateHandler

func (p *Puzzle) StateHandler(w http.ResponseWriter, r *http.Request) error

StateHandler responds with the Puzzle's content. If we can't encode the response to the client successfully, we give both the client and the golang caller an Error response.

func (*Puzzle) String

func (p *Puzzle) String() (result string)

The String form of a puzzle is a pretty-printed grid with assigned squares, bound squares, and 2-choice squares showing their values.

func (*Puzzle) Summary

func (p *Puzzle) Summary() (*Summary, error)

Summary returns the current summary of the puzzle.

func (*Puzzle) SummaryHandler

func (p *Puzzle) SummaryHandler(w http.ResponseWriter, r *http.Request) error

SummaryHandler responds with the Puzzle's summary. If we can't encode the response to the client successfully, we give both the client and the golang caller an Error response.

type Solution

type Solution struct {
	Values  []int    `json:"values"`
	Choices []Choice `json:"choices,omitempty"`
}

A Solution is a filled-in puzzle (expressed as its values) plus the sequence of choices for empty squares that were made to get there. Solutions tend to have far fewer choices than originally empty squares, because most of the empty squares in most puzzles have their values forced (bound) by puzzle structure. These bound values are present only in the solved puzzle, not in the choice list.

type Square

type Square struct {
	Index int       `json:"index"`
	Aval  int       `json:"aval,omitempty"`
	Bval  int       `json:"bval,omitempty"`
	Bsrc  []GroupID `json:"bsrc,omitempty"`
	Pvals intset    `json:"pvals,omitempty"`
}

A Square in a puzzle gives the square's index, assigned value (if any), bound value (if any, with sources), and possible values (if more than one). Puzzle squares are numbered left-to-right, top-to-bottom, starting at 1, and the sequence of squares is returned in that order.

Only required fields are specified in a Square, so as to minimize the Square's JSON-encoded form (which is used for transmission of puzzle data from server to client). If an Aval (user-assigned value) is specified, no other fields should be present. If the square has a Bval (bound value) and Bsrc (bound value source) then the Pvals should not be present.

type Summary

type Summary struct {
	Metadata   map[string]string `json:"metadata,omitempty"`
	Geometry   string            `json:"geometry"`
	SideLength int               `json:"sidelen"`
	Values     []int             `json:"values,omitempty"`
	Errors     []Error           `json:"errors,omitempty"`
}

A Summary gives just the data needed to reconstruct a puzzle in its current state. Because the order in which values are assigned to an unsolvable puzzle determines its errors, the summary of such puzzles includes their errors.

For compactness of encoding, an empty values array indicates an empty puzzle; that is, all squares are unassigned.