author | Mikael Berthe <mikael@lilotux.net> |
Sun, 16 Oct 2016 09:48:36 +0200 | |
changeset 7 | e284e3ad2800 |
parent 6 | 110d38ae22cd |
child 10 | 8dc05ff5dbe2 |
permissions | -rw-r--r-- |
0 | 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 |
||
6
110d38ae22cd
Refactor code; split takuzu.go and create solve.go
Mikael Berthe <mikael@lilotux.net>
parents:
4
diff
changeset
|
16 |
// 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
|
17 |
// routines. |
110d38ae22cd
Refactor code; split takuzu.go and create solve.go
Mikael Berthe <mikael@lilotux.net>
parents:
4
diff
changeset
|
18 |
func SetVerbosityLevel(level int) { |
110d38ae22cd
Refactor code; split takuzu.go and create solve.go
Mikael Berthe <mikael@lilotux.net>
parents:
4
diff
changeset
|
19 |
verbosity = level |
0 | 20 |
} |
21 |
||
6
110d38ae22cd
Refactor code; split takuzu.go and create solve.go
Mikael Berthe <mikael@lilotux.net>
parents:
4
diff
changeset
|
22 |
// 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
|
23 |
// 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
|
24 |
func SetSchrodingerLevel(level uint) { |
110d38ae22cd
Refactor code; split takuzu.go and create solve.go
Mikael Berthe <mikael@lilotux.net>
parents:
4
diff
changeset
|
25 |
schrodLvl = level |
0 | 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 |
||
4 | 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 |
||
0 | 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 |
} |