-
Notifications
You must be signed in to change notification settings - Fork 0
/
zebra_puzzle.go
103 lines (97 loc) · 2.47 KB
/
zebra_puzzle.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package zebra
// CSP is a structure that models a
// simple constraint satisfaction problem
type CSP struct {
v, d []uint8
c []constrainter
}
// SolvePuzzle function solves the zebra puzzle
func SolvePuzzle() Solution {
csp := CSP{
v: make([]uint8, 30),
d: []uint8{1, 2, 3, 4, 5},
c: []constrainter{
constraint(partialSolution),
togetherWithConstraint{a: englishman, b: red},
togetherWithConstraint{a: green, b: coffee},
togetherWithConstraint{a: spaniard, b: dog},
togetherWithConstraint{a: ukrainian, b: tea},
toTheRightOfConstraint{a: green, b: ivory},
togetherWithConstraint{a: oldGold, b: snails},
togetherWithConstraint{a: kools, b: yellow},
togetherWithConstraint{a: milk, b: house3},
togetherWithConstraint{a: norwegian, b: house1},
nextToConstraint{a: chesterfields, b: fox},
nextToConstraint{a: kools, b: horse},
togetherWithConstraint{a: luckyStrike, b: orangeJuice},
togetherWithConstraint{a: japanese, b: parliaments},
nextToConstraint{a: norwegian, b: blue},
},
}
recursiveBacktracking(&csp.v, &csp)
return Solution{OwnsZebra: ownerOf(zebra, csp.v...), DrinksWater: ownerOf(water, csp.v...)}
}
func recursiveBacktracking(assignment *[]uint8, csp *CSP) bool {
if complete(csp.v) {
return true
}
idx := selectUnassigned(&csp.v, assignment, *csp)
domainValueLoop:
for _, d := range csp.d {
csp.v[idx] = d
for _, c := range csp.c {
switch {
case !c.forApplicability()(csp.v...):
continue
case !c.forSatisfaction()(csp.v...):
csp.v[idx] = 0
continue domainValueLoop
default:
}
}
outcome := recursiveBacktracking(assignment, csp)
if !outcome {
csp.v[idx] = 0
continue domainValueLoop
}
return true
}
return false
}
func selectUnassigned(variables, assignment *[]uint8, csp CSP) uint8 {
for _, c := range csp.c {
indexer := func([]uint8) (uint8, bool) { return 0, false }
switch constr := c.(type) {
case togetherWithConstraint:
indexer = constr.forMissingIndex
case nextToConstraint:
indexer = constr.forMissingIndex
}
idx, ok := indexer(*variables)
if !ok || (*variables)[idx] != 0 {
continue
}
return uint8(idx)
}
for i, v := range *assignment {
if v != 0 {
continue
}
return uint8(i)
}
return 0
}
func complete(assignment []uint8) bool {
for _, v := range assignment {
if v != 0 {
continue
}
return false
}
return true
}
// Solution type describes the solution of the zebra puzzle
type Solution struct {
DrinksWater string
OwnsZebra string
}