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