/
queensboard.go
248 lines (230 loc) · 6 KB
/
queensboard.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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
// Package queensboard provides a data structure and method similar to a chess
// board. Queens can be placed on the board, but not within the attack range of
// another queen. The purpose of this package is to provide the underlying tools
// for demonstrating simple backtracking algorithms.
package queensboard
import (
"bytes"
"fmt"
"io"
"sync"
)
var (
// ErrorOperationNotPermitted indicates that an operation is not permitted
// on a particular field. E.g. placing a queen on an attacked field or
// removing a queen from a field that holds no queen
ErrorOperationNotPermitted = fmt.Errorf("operation not permitted")
// ErrorOutOfBounds is returned when coordinates point to a field outside
// of the board
ErrorOutOfBounds = fmt.Errorf("out of bounds coordinates")
// ErrorInvalidBoardDimensions is returned in case of invalid width or
// height values for creating a new board
ErrorInvalidBoardDimensions = fmt.Errorf("invalid board dimensions")
)
// Coordinates holds the x and y values for addressing a field on the board
type Coordinates struct {
X, Y int
}
type field struct {
queen bool // true if a queen is placed on this field
attacks int // number of times the field is under attack by a queen
}
// Board holds a concurrency-safe Queens Board
type Board struct {
lock sync.RWMutex
fields [][]field
queens int
width int
height int
}
// New returns an empty standard-sized (8x8) fields board
func New() *Board {
b, _ := NewCustom(8, 8)
return b
}
// NewCustom returns a board with custom width and height
func NewCustom(width, height int) (*Board, error) {
if width < 1 || height < 1 {
return nil, ErrorInvalidBoardDimensions
}
b := &Board{
width: width,
height: height,
}
b.fields = make([][]field, b.height, b.height)
for i := range b.fields {
b.fields[i] = make([]field, b.width, b.width)
}
return b, nil
}
func (b *Board) withinBounds(x, y int) bool {
if x >= 0 && y >= 0 && x < b.width && y < b.height {
return true
}
return false
}
// PlaceQueen places a queen on the board and updates the attack counters of all
// affected fields.
func (b *Board) PlaceQueen(c Coordinates) error {
if !b.withinBounds(c.X, c.Y) {
return ErrorOutOfBounds
}
b.lock.Lock()
defer b.lock.Unlock()
if b.fields[c.Y][c.X].queen || b.fields[c.Y][c.X].attacks > 0 {
return ErrorOperationNotPermitted
}
// increment fields attack counter: horizontally
for j := 0; b.withinBounds(j, c.Y); j++ {
b.fields[c.Y][j].attacks++
}
// increment fields attack counter: vertically
for i := 0; b.withinBounds(c.X, i); i++ {
b.fields[i][c.X].attacks++
}
// increment fields attack counter: up-left
for j, i := c.X-1, c.Y-1; b.withinBounds(j, i); {
b.fields[i][j].attacks++
j--
i--
}
// increment fields attack counter: up-right
for j, i := c.X+1, c.Y-1; b.withinBounds(j, i); {
b.fields[i][j].attacks++
j++
i--
}
// increment fields attack counter: down-left
for j, i := c.X-1, c.Y+1; b.withinBounds(j, i); {
b.fields[i][j].attacks++
j--
i++
}
// increment fields attack counter: down-right
for j, i := c.X+1, c.Y+1; b.withinBounds(j, i); {
b.fields[i][j].attacks++
j++
i++
}
// place queen
b.fields[c.Y][c.X].attacks = 0
b.fields[c.Y][c.X].queen = true
b.queens++
return nil
}
// RemoveQueen removes a queen from the board and updates the attack counters of
// all affected fields.
func (b *Board) RemoveQueen(c Coordinates) error {
if !b.withinBounds(c.X, c.Y) {
return ErrorOutOfBounds
}
b.lock.Lock()
defer b.lock.Unlock()
if !b.fields[c.Y][c.X].queen {
return ErrorOperationNotPermitted
}
// decrement fields attack counter: horizontally
for j := 0; b.withinBounds(j, c.Y); j++ {
b.fields[c.Y][j].attacks--
}
// decrement fields attack counter: vertically
for i := 0; b.withinBounds(c.X, i); i++ {
b.fields[i][c.X].attacks--
}
// decrement fields attack counter: up-left
for j, i := c.X-1, c.Y-1; b.withinBounds(j, i); {
b.fields[i][j].attacks--
j--
i--
}
// decrement fields attack counter: up-right
for j, i := c.X+1, c.Y-1; b.withinBounds(j, i); {
b.fields[i][j].attacks--
j++
i--
}
// decrement fields attack counter: down-left
for j, i := c.X-1, c.Y+1; b.withinBounds(j, i); {
b.fields[i][j].attacks--
j--
i++
}
// decrement fields attack counter: down-right
for j, i := c.X+1, c.Y+1; b.withinBounds(j, i); {
b.fields[i][j].attacks--
j++
i++
}
// remove queen
b.fields[c.Y][c.X].attacks = 0
b.fields[c.Y][c.X].queen = false
b.queens--
return nil
}
// Queens returns the number of queens on the board
func (b *Board) Queens() int {
b.lock.RLock()
defer b.lock.RUnlock()
return b.queens
}
// AvailableFields returns a list of fields available for queen placement
func (b *Board) AvailableFields() []Coordinates {
var cs []Coordinates
b.lock.RLock()
defer b.lock.RUnlock()
for i := range b.fields {
for j := range b.fields[i] {
if b.fields[i][j].attacks > 0 {
continue
}
if b.fields[i][j].queen {
continue
}
cs = append(cs, Coordinates{X: j, Y: i})
}
}
return cs
}
// Print writes a human readable representation of the current board state to
// the given writer
func (b *Board) Print(w io.Writer) error {
// board framing
var top, middle, bottom bytes.Buffer
top.WriteRune('┏')
middle.WriteRune('┠')
bottom.WriteRune('┗')
for j := 1; j < b.width; j++ {
top.Write([]byte("━┯"))
middle.Write([]byte("─┼"))
bottom.Write([]byte("━┷"))
}
top.Write([]byte("━┓\n"))
middle.Write([]byte("─┨\n"))
bottom.Write([]byte("━┛\n"))
// compile the field
out := bytes.NewBuffer(top.Bytes())
b.lock.RLock()
for i := 0; i < b.height; i++ {
out.WriteRune('┃')
for j := 0; j < b.width; j++ {
if b.fields[i][j].queen {
out.WriteRune('♛')
} else if b.fields[i][j].attacks > 0 {
out.WriteRune('•')
} else {
out.WriteRune(' ')
}
if j < (b.width - 1) {
out.WriteRune('│')
}
}
out.Write([]byte("┃\n"))
if i < (b.height - 1) {
out.Write(middle.Bytes())
}
}
b.lock.RUnlock()
out.Write(bottom.Bytes())
_, err := w.Write(out.Bytes())
return err
}