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
- type ErrorAttribute
- type ErrorCondition
- type ErrorData
- type ErrorScope
- type ErrorStructure
- type GroupID
- type Puzzle
- 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.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Content ¶
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.
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 ¶
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.
type Puzzle ¶
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 ¶
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 ¶
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 ¶
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 ¶
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) Solutions ¶
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 ¶
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 ¶
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 ¶
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 ¶
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) SummaryHandler ¶
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 ¶
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.
Source Files