puzzle-solvers - operateboard.go

  1package solver
  2
  3//go:generate go run ../cmd/generate_neighbors
  4
  5import (
  6	"math/bits"
  7	"strings"
  8)
  9
 10// anything is a cell value that has bits for all possible numbers set.
 11const anything uint16 = 1<<1 | 1<<2 | 1<<3 | 1<<4 | 1<<5 | 1<<6 | 1<<7 | 1<<8 | 1<<9
 12
 13// operateBoard represents a board that is being solved.
 14//
 15// It contains cells that store all possible values for that cell.  The only
 16// serious non-algorithmic optimization is to use uint16s as bit sets, which
 17// makes read/update extremely fast.
 18type operateBoard struct {
 19	cells [9 * 9]uint16
 20}
 21
 22// clone returns a duplicate of b.
 23func (b *operateBoard) clone() *operateBoard {
 24	newBoard := &operateBoard{
 25		cells: [9 * 9]uint16{},
 26	}
 27
 28	copy(newBoard.cells[:], b.cells[:])
 29
 30	return newBoard
 31}
 32
 33// String returns a string representation of the board, where each cell has its
 34// options listed.
 35func (b *operateBoard) String() string {
 36	var s strings.Builder
 37
 38	for i, n := range b.cells {
 39		if i%9 == 0 && i > 0 {
 40			s.WriteRune('\n')
 41		}
 42		if i%27 == 0 && i > 0 {
 43			s.WriteRune('\n')
 44		}
 45		if i%3 == 0 && i%9 != 0 {
 46			s.WriteString(" | ")
 47		}
 48
 49		spaces := 10
 50		for j := 1; j <= 9; j++ {
 51			if n&(1<<j) != 0 {
 52				s.WriteRune(rune(j) + '0')
 53				spaces--
 54			}
 55		}
 56		for ; spaces > 0; spaces-- {
 57			s.WriteRune(' ')
 58		}
 59	}
 60
 61	return s.String()
 62}
 63
 64// clear removes val from the list of options for the cell at idx and also
 65// updates the possibilities for all other cells.
 66//
 67// Returns whether the board is still valid.
 68func (b *operateBoard) clear(idx, val int) bool {
 69	old := b.cells[idx]
 70
 71	// Actually clear the cell
 72	n := b.cells[idx] & ^(1 << val)
 73	b.cells[idx] = n
 74
 75	// If nothing changed, short-curcuit, since this update must have already
 76	// fully propagated at some point in the past.
 77	if old == n {
 78		return true
 79	}
 80
 81	// The board is invalid, since there are no options.
 82	if n == 0 {
 83		return false
 84	}
 85
 86	// If we just reached a single possible number in this cell, immediately
 87	// set it and propagate.
 88	if bits.OnesCount16(n) == 1 {
 89		if !b.set(idx, 15-bits.LeadingZeros16(n)) {
 90			return false
 91		}
 92	}
 93
 94	// Check if val is only valid in a single cell in one of the units for the
 95	// current cell.  This will quickly cascade solutions through the board
 96	for _, unit := range affectedUnits[idx] {
 97		cell := -1
 98		for _, index := range units[unit] {
 99			if b.cells[index]&(1<<val) != 0 {
100				if cell != -1 {
101					// We found two cells in the same unit that can have the
102					// same value.  It's solve()'s job to handle this.
103					//
104					// We know the board is valid because we were passed in a
105					// valid board, and checked all of our operations to ensure
106					// the board stays valid.
107					return true
108				} else {
109					cell = index
110				}
111			}
112		}
113
114		// We didn't find any cells that could be set to val, which means the
115		// board is not valid.
116		if cell == -1 {
117			return false
118		}
119
120		// If cell is the only cell that can be set to val, and wasn't already, then set it!
121		if b.cells[cell] != (1<<val) && !b.set(cell, val) {
122			return false
123		}
124	}
125
126	// We're done propagating.  All of the operations we've performed have
127	// either kept the board valid, or returned early, so we can return true
128	// here without checking again.
129	return true
130}
131
132// set puts val as the only option for idx and propagates.
133//
134// Returns whether the board is still valid
135func (b *operateBoard) set(idx, val int) bool {
136	// Clear all but val instead of just setting it, because Clear has some
137	// special logic.
138	//
139	// Split the for loop to avoid branching inside.
140	for i := 1; i < val; i++ {
141		if !b.clear(idx, i) {
142			return false
143		}
144	}
145
146	for i := val+1; i <=9; i++ {
147		if !b.clear(idx, i) {
148			return false
149		}
150	}
151
152	// Propagate setting of val on this cell to all of the neighbors.
153	for _, neighbor := range neighbors[idx] {
154		if !b.clear(neighbor, val) {
155			return false
156		}
157	}
158
159	return true
160}
161
162func (b *operateBoard) solve() *operateBoard {
163	type option struct {
164		idx int
165		n   int
166	}
167
168	// Iterate over all cells and pick the one that has the smallest number of
169	// choices.
170	var choice *option
171	for i, val := range b.cells {
172		n := bits.OnesCount16(val)
173		if n == 0 {
174			// This board is not valid
175			return nil
176		} else if n == 1 {
177			// We've already determined the value for this cell
178			continue
179		}
180
181		if choice == nil || n < choice.n {
182			choice = &option{i, n}
183		}
184	}
185
186	// We've solved it!
187	if choice == nil {
188		return b
189	}
190
191	newBoard := operateBoard{}
192	// Actually try to set the value.  At the end of this loop, we will either
193	// have a solved puzzle, or know that it's impossible.
194	for i := 1; i <= 9; i++ {
195		// Skip if the cell can't take this number.
196		if b.cells[choice.idx]&(1<<i) == 0 {
197			continue
198		}
199
200		// Propagate the choice of value.
201		copy(newBoard.cells[:], b.cells[:])
202		if !newBoard.set(choice.idx, i) {
203			continue
204		}
205
206		// Solve it!
207		solved := newBoard.solve()
208		if solved != nil {
209			return solved
210		}
211	}
212
213	return nil
214}
215
216// Convert a solved board to a regular board.
217func (b *operateBoard) toBoard() *Board {
218	out := &Board{}
219	for i, v := range b.cells {
220		out[i] = int8(15 - bits.LeadingZeros16(v))
221	}
222
223	return out
224}
225
226func newOperateBoard() *operateBoard {
227	b := &operateBoard{}
228	for i := range b.cells {
229		b.cells[i] = anything
230	}
231
232	return b
233}