|
1 package takuzu |
|
2 |
|
3 import ( |
|
4 "fmt" |
|
5 "log" |
|
6 "runtime" |
|
7 "sync" |
|
8 "time" |
|
9 |
|
10 "github.com/pkg/errors" |
|
11 ) |
|
12 |
|
13 var verbosity int |
|
14 var schrodLvl uint |
|
15 |
|
16 // SetVerbosityLevel initializes the verbosity level of the resolution |
|
17 // routines. |
|
18 func SetVerbosityLevel(level int) { |
|
19 verbosity = level |
|
20 } |
|
21 |
|
22 // SetSchrodingerLevel initializes the "Schrödinger" level (0 means disabled) |
|
23 // It must be called before any board generation or reduction. |
|
24 func SetSchrodingerLevel(level uint) { |
|
25 schrodLvl = level |
|
26 } |
|
27 |
|
28 func (b Takuzu) guessPos(l, c int) int { |
|
29 if b.Board[l][c].Defined { |
|
30 return b.Board[l][c].Value |
|
31 } |
|
32 |
|
33 bx := b.Clone() |
|
34 bx.Set(l, c, 0) |
|
35 bx.FillLineColumn(l, c) |
|
36 if bx.CheckLine(l) != nil || bx.CheckColumn(c) != nil { |
|
37 return 1 |
|
38 } |
|
39 Copy(&b, &bx) |
|
40 bx.Set(l, c, 1) |
|
41 bx.FillLineColumn(l, c) |
|
42 if bx.CheckLine(l) != nil || bx.CheckColumn(c) != nil { |
|
43 return 0 |
|
44 } |
|
45 |
|
46 return -1 // dunno |
|
47 } |
|
48 |
|
49 // TrivialHint returns the coordinates and the value of the first cell that |
|
50 // can be guessed using trivial methods. |
|
51 // It returns {-1, -1, -1} if none can be found. |
|
52 func (b Takuzu) TrivialHint() (line, col, value int) { |
|
53 for line = 0; line < b.Size; line++ { |
|
54 for col = 0; col < b.Size; col++ { |
|
55 if b.Board[line][col].Defined { |
|
56 continue |
|
57 } |
|
58 if value = b.guessPos(line, col); value != -1 { |
|
59 return |
|
60 } |
|
61 } |
|
62 } |
|
63 value, line, col = -1, -1, -1 |
|
64 return |
|
65 } |
|
66 |
|
67 // trySolveTrivialPass does 1 pass over the takuzu board and tries to find |
|
68 // values using simple guesses. |
|
69 func (b Takuzu) trySolveTrivialPass() (changed bool) { |
|
70 for line := 0; line < b.Size; line++ { |
|
71 for col := 0; col < b.Size; col++ { |
|
72 if b.Board[line][col].Defined { |
|
73 continue |
|
74 } |
|
75 if guess := b.guessPos(line, col); guess != -1 { |
|
76 b.Set(line, col, guess) |
|
77 if verbosity > 3 { |
|
78 log.Printf("Trivial: Setting [%d,%d] to %d", line, col, guess) |
|
79 } |
|
80 changed = true // Ideally remember l,c |
|
81 } |
|
82 } |
|
83 } |
|
84 return changed |
|
85 } |
|
86 |
|
87 // TrySolveTrivial tries to solve the takuzu using a loop over simple methods |
|
88 // It returns true if all cells are defined, and an error if the grid breaks the rules. |
|
89 func (b Takuzu) TrySolveTrivial() (bool, error) { |
|
90 for { |
|
91 changed := b.trySolveTrivialPass() |
|
92 if verbosity > 3 { |
|
93 var status string |
|
94 if changed { |
|
95 status = "ongoing" |
|
96 } else { |
|
97 status = "stuck" |
|
98 } |
|
99 log.Println("Trivial resolution -", status) |
|
100 } |
|
101 if !changed { |
|
102 break |
|
103 } |
|
104 |
|
105 if verbosity > 3 { |
|
106 b.DumpBoard() |
|
107 fmt.Println() |
|
108 } |
|
109 } |
|
110 full, err := b.Validate() |
|
111 if err != nil { |
|
112 return full, errors.Wrap(err, "the takuzu looks wrong") |
|
113 } |
|
114 return full, nil |
|
115 } |
|
116 |
|
117 // TrySolveRecurse tries to solve the takuzu recursively, using trivial |
|
118 // method first and using guesses if it fails. |
|
119 func (b Takuzu) TrySolveRecurse(allSolutions *[]Takuzu, timeout time.Duration) (*Takuzu, error) { |
|
120 |
|
121 var solutionsMux sync.Mutex |
|
122 var singleSolution *Takuzu |
|
123 var solutionMap map[string]*Takuzu |
|
124 |
|
125 var globalSearch bool |
|
126 // globalSearch doesn't need to use a mutex and is more convenient |
|
127 // to use than allSolutions. |
|
128 if allSolutions != nil { |
|
129 globalSearch = true |
|
130 solutionMap = make(map[string]*Takuzu) |
|
131 } |
|
132 |
|
133 startTime := time.Now() |
|
134 |
|
135 var recurseSolve func(level int, t Takuzu, errStatus chan<- error) error |
|
136 |
|
137 recurseSolve = func(level int, t Takuzu, errStatus chan<- error) error { |
|
138 |
|
139 reportStatus := func(failure error) { |
|
140 // Report status to the caller's channel |
|
141 if errStatus != nil { |
|
142 errStatus <- failure |
|
143 } |
|
144 } |
|
145 |
|
146 // In Schröndinger mode we check concurrently both values for a cell |
|
147 var schrodinger bool |
|
148 concurrentRoutines := 1 |
|
149 if level < int(schrodLvl) { |
|
150 schrodinger = true |
|
151 concurrentRoutines = 2 |
|
152 } |
|
153 |
|
154 var status [2]chan error |
|
155 status[0] = make(chan error) |
|
156 status[1] = make(chan error) |
|
157 |
|
158 for { |
|
159 // Try simple resolution first |
|
160 full, err := t.TrySolveTrivial() |
|
161 if err != nil { |
|
162 reportStatus(err) |
|
163 return err |
|
164 } |
|
165 |
|
166 if full { // We're done |
|
167 if verbosity > 1 { |
|
168 log.Printf("{%d} The takuzu is correct and complete.", level) |
|
169 } |
|
170 solutionsMux.Lock() |
|
171 singleSolution = &t |
|
172 if globalSearch { |
|
173 solutionMap[t.ToString()] = &t |
|
174 } |
|
175 solutionsMux.Unlock() |
|
176 |
|
177 reportStatus(nil) |
|
178 return nil |
|
179 } |
|
180 |
|
181 if verbosity > 2 { |
|
182 log.Printf("{%d} Trivial resolution did not complete.", level) |
|
183 } |
|
184 |
|
185 // Trivial method is stuck, let's use recursion |
|
186 |
|
187 changed := false |
|
188 |
|
189 // Looking for first empty cell |
|
190 var line, col int |
|
191 firstClear: |
|
192 for line = 0; line < t.Size; line++ { |
|
193 for col = 0; col < t.Size; col++ { |
|
194 if !t.Board[line][col].Defined { |
|
195 break firstClear |
|
196 } |
|
197 } |
|
198 } |
|
199 |
|
200 if line == t.Size || col == t.Size { |
|
201 break |
|
202 } |
|
203 |
|
204 if verbosity > 2 { |
|
205 log.Printf("{%d} GUESS - Trying values for [%d,%d]", level, line, col) |
|
206 } |
|
207 |
|
208 var val int |
|
209 err = nil |
|
210 errCount := 0 |
|
211 |
|
212 for testval := 0; testval < 2; testval++ { |
|
213 if !globalSearch && t.Board[line][col].Defined { |
|
214 // No need to "guess" here anymore |
|
215 break |
|
216 } |
|
217 |
|
218 // Launch goroutines for cell values of 0 and/or 1 |
|
219 for testCase := 0; testCase < 2; testCase++ { |
|
220 if schrodinger || testval == testCase { |
|
221 tx := t.Clone() |
|
222 tx.Set(line, col, testCase) |
|
223 go recurseSolve(level+1, tx, status[testCase]) |
|
224 } |
|
225 } |
|
226 |
|
227 // Let's collect the goroutines' results |
|
228 for i := 0; i < concurrentRoutines; i++ { |
|
229 if schrodinger && verbosity > 1 { // XXX |
|
230 log.Printf("{%d} Schrodinger waiting for result #%d for cell [%d,%d]", level, i, line, col) |
|
231 } |
|
232 select { |
|
233 case e := <-status[0]: |
|
234 err = e |
|
235 val = 0 |
|
236 case e := <-status[1]: |
|
237 err = e |
|
238 val = 1 |
|
239 } |
|
240 |
|
241 if schrodinger && verbosity > 1 { // XXX |
|
242 log.Printf("{%d} Schrodinger result #%d/2 for cell [%d,%d]=%d - err=%v", level, i+1, line, col, val, err) |
|
243 } |
|
244 |
|
245 if err == nil { |
|
246 if !globalSearch { |
|
247 reportStatus(nil) |
|
248 if i+1 < concurrentRoutines { |
|
249 // Schröndinger mode and we still have one status to fetch |
|
250 <-status[1-val] |
|
251 } |
|
252 return nil |
|
253 } |
|
254 continue |
|
255 } |
|
256 if timeout > 0 && level > 2 && time.Since(startTime) > timeout { |
|
257 if errors.Cause(err).Error() != "timeout" { |
|
258 if verbosity > 0 { |
|
259 log.Printf("{%d} Timeout, giving up", level) |
|
260 } |
|
261 err := errors.New("timeout") |
|
262 reportStatus(err) |
|
263 if i+1 < concurrentRoutines { |
|
264 // Schröndinger mode and we still have one status to fetch |
|
265 <-status[1-val] |
|
266 } |
|
267 // XXX actually can't close the channel and leave, can I? |
|
268 return err |
|
269 } |
|
270 } |
|
271 |
|
272 // err != nil: we can set a value -- unless this was a timeout |
|
273 if errors.Cause(err).Error() == "timeout" { |
|
274 if verbosity > 1 { |
|
275 log.Printf("{%d} Timeout propagation", level) |
|
276 } |
|
277 reportStatus(err) |
|
278 if i+1 < concurrentRoutines { |
|
279 // Schröndinger mode and we still have one status to fetch |
|
280 <-status[1-val] |
|
281 } |
|
282 // XXX actually can't close the channel and leave, can I? |
|
283 return err |
|
284 } |
|
285 |
|
286 errCount++ |
|
287 if verbosity > 2 { |
|
288 log.Printf("{%d} Bad outcome (%v)", level, err) |
|
289 log.Printf("{%d} GUESS was wrong - Setting [%d,%d] to %d", |
|
290 level, line, col, 1-val) |
|
291 } |
|
292 |
|
293 t.Set(line, col, 1-val) |
|
294 changed = true |
|
295 |
|
296 } // concurrentRoutines |
|
297 |
|
298 if (changed && !globalSearch) || schrodinger { |
|
299 // Let's loop again with the new board |
|
300 break |
|
301 } |
|
302 } |
|
303 |
|
304 if verbosity > 2 { |
|
305 log.Printf("{%d} End of cycle.\n\n", level) |
|
306 } |
|
307 |
|
308 if errCount == 2 { |
|
309 // Both values failed |
|
310 err := errors.New("dead end") |
|
311 reportStatus(err) |
|
312 return err |
|
313 } |
|
314 |
|
315 // If we cannot fill more cells (!changed) or if we've made a global search with |
|
316 // both values, the search is complete. |
|
317 if schrodinger || globalSearch || !changed { |
|
318 break |
|
319 } |
|
320 |
|
321 if verbosity > 2 { |
|
322 t.DumpBoard() |
|
323 fmt.Println() |
|
324 } |
|
325 } |
|
326 |
|
327 // Try to force garbage collection |
|
328 runtime.GC() |
|
329 |
|
330 full, err := t.Validate() |
|
331 if err != nil { |
|
332 if verbosity > 1 { |
|
333 log.Println("The takuzu looks wrong - ", err) |
|
334 } |
|
335 err := errors.Wrap(err, "the takuzu looks wrong") |
|
336 reportStatus(err) |
|
337 return err |
|
338 } |
|
339 if full { |
|
340 if verbosity > 1 { |
|
341 log.Println("The takuzu is correct and complete") |
|
342 } |
|
343 solutionsMux.Lock() |
|
344 singleSolution = &t |
|
345 if globalSearch { |
|
346 solutionMap[t.ToString()] = &t |
|
347 } |
|
348 solutionsMux.Unlock() |
|
349 } |
|
350 |
|
351 reportStatus(nil) |
|
352 return nil |
|
353 } |
|
354 |
|
355 status := make(chan error) |
|
356 go recurseSolve(0, b, status) |
|
357 |
|
358 err := <-status // Wait for it... |
|
359 |
|
360 firstSol := singleSolution |
|
361 if globalSearch { |
|
362 for _, tp := range solutionMap { |
|
363 *allSolutions = append(*allSolutions, *tp) |
|
364 } |
|
365 } |
|
366 |
|
367 if err != nil { |
|
368 return firstSol, err |
|
369 } |
|
370 |
|
371 if globalSearch && len(*allSolutions) > 0 { |
|
372 firstSol = &(*allSolutions)[0] |
|
373 } |
|
374 return firstSol, nil |
|
375 } |