solver

package
v0.0.0-...-3792e36 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 1, 2024 License: MIT Imports: 9 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	BoardSize      = 9
	BlockSize      = 3
	EmptyCellValue = Value(0)
	MinimumGivens  = 17
	Offset         = 1
	EOL            = 0x0A
)

Variables

View Source 
var Digits = roaring.BitmapOf(1, 2, 3, 4, 5, 6, 7, 8, 9)
View Source 
var HexMap = map[byte]Value{
	0x2e: 0x00,
	0x30: 0x00,
	0x31: 0x01,
	0x32: 0x02,
	0x33: 0x03,
	0x34: 0x04,
	0x35: 0x05,
	0x36: 0x06,
	0x37: 0x07,
	0x38: 0x08,
	0x39: 0x09,
}
View Source 
var Levels = map[Difficulty]string{
	Easy:   "Easy",
	Medium: "Medium",
	Hard:   "Hard",
	Expert: "Expert",
	Evil:   "Evil",
}
View Source 
var ValidInputs = roaring.BitmapOf(uint32(EmptyCellValue), 1, 2, 3, 4, 5, 6, 7, 8, 9)

Functions

func BackTrack 

func BackTrack(data [BoardSize][BoardSize]*Cell) (bool, [BoardSize][BoardSize]*Cell)

func BitmapPairs 

func BitmapPairs(in []uint32) []*roaring.Bitmap

BitmapPairs simply creates all unique ordered pair combinations in given uint32 array as roaring.Bitmap instance

func BitmapQuads 

func BitmapQuads(in []uint32) []*roaring.Bitmap

BitmapQuads simply creates all unique ordered quad combinations in given uint32 array as roaring.Bitmap instance

func BitmapSingles 

func BitmapSingles(in []uint32) []*roaring.Bitmap

BitmapSingles simply creates all unique ordered single combinations in given uint32 array as roaring.Bitmap instance

func BitmapTriplets 

func BitmapTriplets(in []uint32) []*roaring.Bitmap

BitmapTriplets simply creates all unique ordered triplet combinations in given uint32 array as roaring.Bitmap instance

func CloneData 

func CloneData(data [BoardSize][BoardSize]*Cell) [BoardSize][BoardSize]*Cell

func ColumnsHasAtLeast2TimesTheValue 

func ColumnsHasAtLeast2TimesTheValue(up *roaring.Bitmap, middle *roaring.Bitmap, down *roaring.Bitmap) bool

func EliminateHiddenPairs 

func EliminateHiddenPairs(units [][]*Cell) error

EliminateHiddenPairs eliminates the marks from the pairs which has exactly and only the same two candidates all over the unit. The other candidates could be removed safely from the pairs

func EliminateHiddenQuads 

func EliminateHiddenQuads(units [][]*Cell) error

func EliminateHiddenSingles 

func EliminateHiddenSingles(units [][]*Cell) error

func EliminateHiddenTriplets 

func EliminateHiddenTriplets(units [][]*Cell) error

EliminateHiddenTriplets eliminates the marks from the pairs which has exactly and only the same two candidates all over the unit. The other candidates could be removed safely from the pairs

func EliminateNakedPairs 

func EliminateNakedPairs(units [][]*Cell) error

EliminateNakedPairs creates pairs combinations of marks/candidates on each unit (row, col or box) if there are any pairs having the cardinality 2 (Unions of the three sets has exactly 2 different elements) Then the other cell candidates within the unit having one of these elements is safely eliminated Returns the number of eliminated candidates

func EliminateNakedQuads 

func EliminateNakedQuads(units [][]*Cell) error

EliminateNakedQuads creates quad combinations of marks/candidates on each unit (row, col or box) if there are any quads having the cardinality 4 (Unions of the three sets has exactly 4 different elements) Then the other cell candidates within the unit having one of these elements is safely eliminated Returns the number of eliminated candidates

func EliminateNakedTriplets 

func EliminateNakedTriplets(units [][]*Cell) error

EliminateNakedTriplets creates triple combinations of marks/candidates on each unit (row, col or box) if there are any triplets having the cardinality 3 (Unions of the three sets has exactly 3 different elements) Then the other cell candidates within the unit having one of these elements is safely eliminated

func EliminateSwordFish 

func EliminateSwordFish(b *Board) error

func EliminateXWings 

func EliminateXWings(b *Board) error

func EliminateXYWings 

func EliminateXYWings(unsolved []*Cell, b *Board) error

func EliminateXYZWings 

func EliminateXYZWings(unsolved []*Cell, b *Board) error

func FindMarksOfUnit 

func FindMarksOfUnit(unit []*Cell) *roaring.Bitmap

FindMarksOfUnit finds marks/candidates of the given unit by getting the difference (XOR) of solved cells and all available digits

func IndexesBitmap 

func IndexesBitmap(cells []*Cell) *roaring.Bitmap

func IsCellInCollection 

func IsCellInCollection(cell *Cell, collection []*Cell) bool

IsCellInCollection is a helper function to report whether given cell is inside of collection or not

func IsCellInCollections 

func IsCellInCollections(cell *Cell, collection [][]*Cell) bool

IsCellInCollections is a helper function to report whether given cell is inside of collections or not

func IsCombinationHiddenWithinUnit 

func IsCombinationHiddenWithinUnit(bitmap *roaring.Bitmap, cells []*Cell, unit []*Cell) bool

func IsHiddenPair 

func IsHiddenPair(pair []*Cell, unit []*Cell) (bool, *roaring.Bitmap)

IsHiddenPair is a helper method to calculate the intersection of the giving pair and looping over the unit to get the diff of intersection and other cell marks, and if the final intersection of difference have some elements, then the given pair is a hidden pair. Function returns also the marks that has to be kept

func IsHiddenQuad 

func IsHiddenQuad(quad []*Cell, unit []*Cell) (bool, *roaring.Bitmap)

func IsHiddenSingle 

func IsHiddenSingle(single *Cell, unit []*Cell) (bool, *roaring.Bitmap)

func IsHiddenTriplet 

func IsHiddenTriplet(triplet []*Cell, unit []*Cell) (bool, *roaring.Bitmap)

IsHiddenTriplet is a helper method to calculate the intersection of the giving pair and looping over the unit to get the diff of intersection and other cell marks, and if the final intersection of difference have some elements, then the given pair is a hidden pair. Function returns also the marks that has to be kept

func IsPairRelated 

func IsPairRelated(pair []*Cell, board *Board) bool

func IsSolved 

func IsSolved(data [BoardSize][BoardSize]*Cell) (bool, int, int)

func IsTripletHasSameCardinality 

func IsTripletHasSameCardinality(triplet []*Cell, cardinality int) bool

func IsTripletUnionHasCardinality 

func IsTripletUnionHasCardinality(triplet []*Cell, cardinality int) bool

func IsTripletXYZWingBasedOnCardinality 

func IsTripletXYZWingBasedOnCardinality(triplet []*Cell) bool

func IsValidBuffer 

func IsValidBuffer(buffer []byte) bool

IsValidBuffer simply checks whether the current buffer holds valid board information or not

func IsValidValue 

func IsValidValue(data [BoardSize][BoardSize]*Cell, row int, col int, value Value) bool

func PairCombinations 

func PairCombinations(input []*Cell) [][]*Cell

PairCombinations simply creates all unique ordered pair combinations of given cell unit

func ParIntersect 

func ParIntersect(units ...*roaring.Bitmap) *roaring.Bitmap

ParIntersect returns the intersection of all given units

func ParIntersectCells 

func ParIntersectCells(cells []*Cell) *roaring.Bitmap

ParIntersectCells returns the intersection of all given cells

func ParUnion 

func ParUnion(units ...*roaring.Bitmap) *roaring.Bitmap

ParUnion returns the union of all given units

func ParUnionCells 

func ParUnionCells(cells []*Cell) *roaring.Bitmap

ParUnionCells returns the union of all given cells

func QuadCombinations 

func QuadCombinations(input []*Cell) [][]*Cell

QuadCombinations simply creates all unique ordered quad combinations of given cells unit

func SolvedCells 

func SolvedCells(cells []*Cell) *roaring.Bitmap

SolvedCells creates marks from the solved cells within the unit

func TripletCombinations 

func TripletCombinations(input []*Cell) [][]*Cell

TripletCombinations simply creates all unique ordered triple combinations of given cells unit

Types

type Board 

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

Board is the struct of the Sudoku board

func NewBoard 

func NewBoard(input [BoardSize][BoardSize]Value) (*Board, error)

NewBoard returns new Sudoku board with the given input matrix, if there are any issues it also returns error

func ParseFile 

func ParseFile(path string) ([]*Board, error)

ParseFile simply parses sudoku file and returns a sudoku board for each line

func (*Board) GetGivensAndBackTrack 

func (b *Board) GetGivensAndBackTrack() (int, bool)

GetGivensAndBackTrack returns the givens and backTrackUsed flag

func (*Board) Solve 

func (b *Board) Solve() *SolveResponse

Solve is a utility function to start the solving process of given sudoku board

type Cell 

type Cell struct {
	ID    int
	Row   int
	Col   int
	Value Value
	Marks *roaring.Bitmap
}

Cell is the struct of cell keeping unique id, row and col ids solved value and current marks/candidates

func Box 

func Box(data [BoardSize][BoardSize]*Cell, rowID int, colID int) []*Cell

Box returns the box cells in the given cell index by row and col ids

func Col 

func Col(data [BoardSize][BoardSize]*Cell, index int) []*Cell

Col returns the col in the given index

func HasSwordFishCandidates 

func HasSwordFishCandidates(row []*Cell) (bool, []*Cell, *roaring.Bitmap)

func HasXCandidates 

func HasXCandidates(row []*Cell) (bool, []*Cell, *roaring.Bitmap)

func HiddenPairs 

func HiddenPairs(unit []*Cell) (bool, []*Cell, *roaring.Bitmap)

HiddenPairs is a helper method to find any hidden pair over the unit by creating pair combinations and testing the pairs whether they are hidden pair or not

func HiddenQuads 

func HiddenQuads(unit []*Cell) (bool, []*Cell, *roaring.Bitmap)

func HiddenSingles 

func HiddenSingles(unit []*Cell) (bool, *Cell, *roaring.Bitmap)

func HiddenTriplets 

func HiddenTriplets(unit []*Cell) (bool, []*Cell, *roaring.Bitmap)

HiddenTriplets is a helper method to find any hidden pair over the unit by creating triplet combinations and testing the triplets whether they are hidden triplet or not

func IsMarkAppearsTwiceInRow 

func IsMarkAppearsTwiceInRow(mark *roaring.Bitmap, row []*Cell) (bool, []*Cell)

func IsMarkAppearsTwiceOrThreeInRow 

func IsMarkAppearsTwiceOrThreeInRow(mark *roaring.Bitmap, row []*Cell) (bool, []*Cell)

func IsNakedPairs 

func IsNakedPairs(combinations [][]*Cell) (bool, []*Cell)

IsNakedPairs simply checks whether there are any naked pairs or not in the given combination

func IsNakedQuad 

func IsNakedQuad(combinations [][]*Cell) (bool, []*Cell)

IsNakedQuad simply checks whether there are any naked quads or not in the given combination

func IsNakedTriplet 

func IsNakedTriplet(combinations [][]*Cell) (bool, []*Cell)

IsNakedTriplet simply checks whether there are any naked triplets or not in the given combination

func Row 

func Row(data [BoardSize][BoardSize]*Cell, index int) []*Cell

Row returns the row in the given index

func SearchSwordFishMiddlePart 

func SearchSwordFishMiddlePart(upCells []*Cell, mark *roaring.Bitmap, rowIndex int, b *Board) (bool, []*Cell, int)

func UnSolvedCells 

func UnSolvedCells(cells []*Cell) []*Cell

UnSolvedCells returns the unsolved cells within the unit

func (*Cell) CellUnits 

func (c *Cell) CellUnits(b *Board) [][]*Cell

CellUnits returns the related cells row, col and box

func (*Cell) ComputeCellMarks 

func (c *Cell) ComputeCellMarks(b *Board) *roaring.Bitmap

ComputeCellMarks computes the candidates/marks of the current cell

func (*Cell) IsSolved 

func (c *Cell) IsSolved() bool

IsSolved simply returns whether the cell is already solved or not

func (*Cell) IsValid 

func (c *Cell) IsValid(b *Board, v Value) bool

IsValid checks the validity of given v value to put in cell

func (*Cell) MarksLength 

func (c *Cell) MarksLength() int

MarksLength simply returns the length of the current marks bitmap

type Difficulty 

type Difficulty int
const (
	Easy Difficulty = iota
	Medium
	Hard
	Expert
	Evil
)

type SolveResponse 

type SolveResponse struct {
	Difficulty       string
	Givens           int
	InitialState     string
	Solution         string
	Duration         float64
	IsSolved         bool
	BackTrackingUsed bool
	StrategiesUsed   []string
	Error            error
}

func (*SolveResponse) Print 

func (r *SolveResponse) Print() string

type Strategy 

type Strategy string
const (
	NakedQuadsStrategy     Strategy = "Naked Quads"
	NakedTriplesStrategy   Strategy = "Naked Triples"
	NakedPairsStrategy     Strategy = "Naked Pairs"
	XYWingsStrategy        Strategy = "XY Wings"
	XYZWingsStrategy       Strategy = "XYZ Wings"
	XWingsStrategy         Strategy = "X Wings"
	SwordFishStrategy      Strategy = "Sword Fish"
	HiddenSingleStrategy   Strategy = "Hidden Single"
	HiddenQuadsStrategy    Strategy = "Hidden Quads"
	HiddenTripletsStrategy Strategy = "Hidden Triplets"
	HiddenPairsStrategy    Strategy = "Hidden Pairs"
)

func (Strategy) ToString 

func (s Strategy) ToString() string

type SwordFish 

type SwordFish struct {
	Up     []*Cell
	Middle []*Cell
	Down   []*Cell
	Mark   *roaring.Bitmap
}

func SearchSwordFishDownPart 

func SearchSwordFishDownPart(upCells []*Cell, middleCells []*Cell, mark *roaring.Bitmap, rowIndex int, b *Board) (bool, *SwordFish)

func (*SwordFish) ColsUnion 

func (s *SwordFish) ColsUnion() []uint32

func (*SwordFish) Eliminate 

func (s *SwordFish) Eliminate(b *Board) error

func (*SwordFish) Print 

func (s *SwordFish) Print()

type Value 

type Value byte

Value is the value type of the solved cell which is simply a byte

type XWing 

type XWing struct {
	Up   []*Cell
	Down []*Cell
	Mark *roaring.Bitmap
}

func SearchDownPart 

func SearchDownPart(upCells []*Cell, mark *roaring.Bitmap, rowIndex int, b *Board) (bool, *XWing)

func (*XWing) Eliminate 

func (x *XWing) Eliminate(b *Board) error

func (*XWing) LeftCol 

func (x *XWing) LeftCol(b *Board) ([]*Cell, error)

func (*XWing) Print 

func (x *XWing) Print()

func (*XWing) RightCol 

func (x *XWing) RightCol(b *Board) ([]*Cell, error)

type XYWing 

type XYWing struct {
	Pivot *Cell
	Wings []*Cell
}

func IsTripletXYWingCandidate 

func IsTripletXYWingCandidate(triplet []*Cell, b *Board) (bool, *XYWing)

func (*XYWing) Eliminate 

func (xy *XYWing) Eliminate(b *Board) error

func (*XYWing) Print 

func (xy *XYWing) Print()

func (*XYWing) Triplet 

func (xy *XYWing) Triplet() []*Cell

func (*XYWing) Union 

func (xy *XYWing) Union() *roaring.Bitmap

func (*XYWing) WingsIntersect 

func (xy *XYWing) WingsIntersect(b *Board) []*Cell

type XYZWing 

type XYZWing struct {
	Pivot *Cell
	Wings []*Cell
}

func IsTripletXYZWingCandidate 

func IsTripletXYZWingCandidate(triplet []*Cell, b *Board) (bool, *XYZWing)

func (*XYZWing) Eliminate 

func (xyz *XYZWing) Eliminate(b *Board) error

func (*XYZWing) Intersect 

func (xyz *XYZWing) Intersect() *roaring.Bitmap

func (*XYZWing) Print 

func (xyz *XYZWing) Print()

func (*XYZWing) Triplet 

func (xyz *XYZWing) Triplet() []*Cell

func (*XYZWing) XYZIntersect 

func (xyz *XYZWing) XYZIntersect(b *Board) []*Cell

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.