1 // Package sudoku is a generic solver for sudoku type puzzles. It can solve a puzzle of any shape and size. 2 package sudoku // import "vimagination.zapto.org/sudoku" 3 4 var ( 5 s4 = []Constraint{ 6 Unique{0, 1, 2, 3}, 7 Unique{4, 5, 6, 7}, 8 Unique{8, 9, 10, 11}, 9 Unique{12, 13, 14, 15}, 10 Unique{0, 4, 8, 12}, 11 Unique{1, 5, 9, 13}, 12 Unique{2, 6, 10, 14}, 13 Unique{3, 7, 11, 15}, 14 Unique{0, 1, 4, 5}, 15 Unique{2, 3, 6, 7}, 16 Unique{8, 9, 12, 13}, 17 Unique{10, 11, 14, 15}, 18 } 19 s9 = []Constraint{ 20 Unique{0, 1, 2, 3, 4, 5, 6, 7, 8}, 21 Unique{9, 10, 11, 12, 13, 14, 15, 16, 17}, 22 Unique{18, 19, 20, 21, 22, 23, 24, 25, 26}, 23 Unique{27, 28, 29, 30, 31, 32, 33, 34, 35}, 24 Unique{36, 37, 38, 39, 40, 41, 42, 43, 44}, 25 Unique{45, 46, 47, 48, 49, 50, 51, 52, 53}, 26 Unique{54, 55, 56, 57, 58, 59, 60, 61, 62}, 27 Unique{63, 64, 65, 66, 67, 68, 69, 70, 71}, 28 Unique{72, 73, 74, 75, 76, 77, 78, 79, 80}, 29 Unique{0, 9, 18, 27, 36, 45, 54, 63, 72}, 30 Unique{1, 10, 19, 28, 37, 46, 55, 64, 73}, 31 Unique{2, 11, 20, 29, 38, 47, 56, 65, 74}, 32 Unique{3, 12, 21, 30, 39, 48, 57, 66, 75}, 33 Unique{4, 13, 22, 31, 40, 49, 58, 67, 76}, 34 Unique{5, 14, 23, 32, 41, 50, 59, 68, 77}, 35 Unique{6, 15, 24, 33, 42, 51, 60, 69, 78}, 36 Unique{7, 16, 25, 34, 43, 52, 61, 70, 79}, 37 Unique{8, 17, 26, 35, 44, 53, 62, 71, 80}, 38 Unique{0, 1, 2, 9, 10, 11, 18, 19, 20}, 39 Unique{3, 4, 5, 12, 13, 14, 21, 22, 23}, 40 Unique{6, 7, 8, 15, 16, 17, 24, 25, 26}, 41 Unique{27, 28, 29, 36, 37, 38, 45, 46, 47}, 42 Unique{30, 31, 32, 39, 40, 41, 48, 49, 50}, 43 Unique{33, 34, 35, 42, 43, 44, 51, 52, 53}, 44 Unique{54, 55, 56, 63, 64, 65, 72, 73, 74}, 45 Unique{57, 58, 59, 66, 67, 68, 75, 76, 77}, 46 Unique{60, 61, 62, 69, 70, 71, 78, 79, 80}, 47 } 48 ) 49 50 // MakeBox is a helper function to make it easier to create the sections in standard rectangular puzzles 51 func MakeBox(gridWidth, gridHeight, boxWidth, boxHeight int) []Constraint { 52 toRet := make([]Constraint, 0, gridWidth/boxWidth*gridHeight/boxHeight) 53 for j := 0; j < gridHeight; j += boxHeight { 54 for i := 0; i < gridWidth; i += boxWidth { 55 thisGrid := make(Unique, 0, boxWidth*boxHeight) 56 for y := 0; y < boxHeight; y++ { 57 for x := 0; x < boxWidth; x++ { 58 thisGrid = append(thisGrid, i+x+(j+y)*gridWidth) 59 } 60 } 61 toRet = append(toRet, thisGrid) 62 } 63 } 64 return toRet 65 } 66 67 // Solve9 is a sudoku puzzle of the standard 9x9 format 68 func Solve9(data []int) bool { 69 if len(data) != 81 { 70 return false 71 } 72 s := Sudoku{ 73 data: data, 74 chars: 9, 75 constraints: s9, 76 } 77 return s.Solve() 78 } 79 80 // Solve4 is a sudoku puzzle of the 4x4 format 81 func Solve4(data []int) bool { 82 if len(data) != 16 { 83 return false 84 } 85 s := Sudoku{ 86 data: data, 87 chars: 4, 88 constraints: s4, 89 } 90 return s.Solve() 91 } 92 93 // Solve allows the creation of a non-standard Sudoku puzzle and solves it. 94 // 95 // data is the puzzle information, layed out left to right, then top to bottom 96 // 97 // chars is any valid 'character' the puzzle uses - 0 is used for an unfilled space 98 // 99 // structure is a slice of sections, each of which is a slice of positions, len(chars) 100 // in length, which describes the rows, columns, boxes or other shapes in which there 101 // can only be one of each character 102 // 103 // Will return true if puzzle is solveable and the solution will be stored in the data slice. 104 // Upon a failure, will return false and the data slice will be as original. 105 func Solve(data []int, chars int, constraints []Constraint) bool { 106 s := Sudoku{data, chars, constraints} 107 return s.Solve() 108 } 109 110 func slicePos(s []int, p int) int { 111 for n, sp := range s { 112 if sp == p { 113 return n 114 } 115 } 116 return -1 117 } 118 119 // Constraint defines the interface through which the character constraints are processed 120 type Constraint interface { 121 Constrain(*Sudoku, int, []bool) bool 122 } 123 124 // Sudoku puzzle information 125 type Sudoku struct { 126 data []int 127 chars int 128 constraints []Constraint 129 } 130 131 // Chars returns the number of different characters used in the puzzle 132 func (s *Sudoku) Chars() int { 133 return s.chars 134 } 135 136 // Pos return the character at the given position 137 func (s *Sudoku) Pos(i int) int { 138 return s.data[i] 139 } 140 141 func (s *Sudoku) possible(pos int) []int { 142 if pos < 0 || pos > len(s.data) || s.data[pos] != 0 { 143 return nil 144 } 145 marked := make([]bool, s.chars+1) 146 for _, c := range s.constraints { 147 any := c.Constrain(s, pos, marked) 148 if !any { 149 return []int{} 150 } 151 } 152 toRet := make([]int, 0, s.chars) 153 for p, m := range marked[1:] { 154 if !m { 155 toRet = append(toRet, p+1) 156 } 157 } 158 return toRet 159 } 160 161 // Solve will solve any solveable puzzle and return whether is was sucessful. 162 func (s *Sudoku) Solve() bool { 163 l := len(s.data) 164 possibilities := make([][]int, l) 165 var pos int 166 for ; pos < l; pos++ { 167 if p := s.possible(pos); p != nil { 168 possibilities[pos] = p 169 break 170 } 171 } 172 for pos < l { 173 if len(possibilities[pos]) == 0 { 174 s.data[pos] = 0 175 for pos--; pos >= 0 && len(possibilities[pos]) == 0; pos-- { 176 if possibilities[pos] != nil { 177 s.data[pos] = 0 178 } 179 } 180 if pos < 0 { 181 return false 182 } 183 continue 184 } 185 s.data[pos] = possibilities[pos][0] 186 possibilities[pos] = possibilities[pos][1:] 187 for pos++; pos < l; pos++ { 188 if p := s.possible(pos); p != nil { 189 possibilities[pos] = p 190 break 191 } 192 } 193 } 194 return true 195 }