-
Notifications
You must be signed in to change notification settings - Fork 27
/
solver.go
145 lines (130 loc) · 2.78 KB
/
solver.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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
package rush
type Solution struct {
Solvable bool
Moves []Move
NumMoves int
NumSteps int
Depth int
MemoSize int
MemoHits uint64
}
type Solver struct {
board *Board
target int
memo *Memo
sa *StaticAnalyzer
path []Move
moves [][]Move
}
func NewSolverWithStaticAnalyzer(board *Board, sa *StaticAnalyzer) *Solver {
solver := Solver{}
solver.board = board
solver.target = board.Target()
solver.memo = NewMemo()
solver.sa = sa
return &solver
}
func NewSolver(board *Board) *Solver {
return NewSolverWithStaticAnalyzer(board, theStaticAnalyzer)
}
func (solver *Solver) isSolved() bool {
return solver.board.Pieces[0].Position == solver.target
}
func (solver *Solver) search(depth, maxDepth, previousPiece int) bool {
height := maxDepth - depth
if height == 0 {
return solver.isSolved()
}
board := solver.board
if !solver.memo.Add(board.MemoKey(), height) {
return false
}
// count occupied squares between primary piece and target
primary := board.Pieces[0]
i0 := primary.Position + primary.Size
i1 := solver.target + primary.Size - 1
minMoves := 0
for i := i0; i <= i1; i++ {
if board.occupied[i] {
minMoves++
}
}
if minMoves >= height {
return false
}
buf := &solver.moves[depth]
*buf = board.Moves(*buf)
for _, move := range *buf {
if move.Piece == previousPiece {
continue
}
board.DoMove(move)
solved := solver.search(depth+1, maxDepth, move.Piece)
board.UndoMove(move)
if solved {
solver.memo.Set(board.MemoKey(), height-1)
solver.path[depth] = move
return true
}
}
return false
}
func (solver *Solver) solve(skipChecks bool) Solution {
board := solver.board
memo := solver.memo
if !skipChecks {
if err := board.Validate(); err != nil {
return Solution{}
}
if solver.sa.Impossible(board) {
return Solution{}
}
}
if solver.isSolved() {
return Solution{Solvable: true}
}
previousMemoSize := 0
noChange := 0
cutoff := board.Width - board.Pieces[0].Size
for i := 1; ; i++ {
solver.path = make([]Move, i)
solver.moves = make([][]Move, i)
if solver.search(0, i, -1) {
moves := solver.path
steps := 0
for _, move := range moves {
steps += move.AbsSteps()
}
result := Solution{
Solvable: true,
Moves: moves,
NumMoves: len(moves),
NumSteps: steps,
Depth: i,
MemoSize: memo.Size(),
MemoHits: memo.Hits(),
}
return result
}
memoSize := memo.Size()
if memoSize == previousMemoSize {
noChange++
} else {
noChange = 0
}
if !skipChecks && noChange > cutoff {
return Solution{
Depth: i,
MemoSize: memo.Size(),
MemoHits: memo.Hits(),
}
}
previousMemoSize = memoSize
}
}
func (solver *Solver) Solve() Solution {
return solver.solve(false)
}
func (solver *Solver) UnsafeSolve() Solution {
return solver.solve(true)
}