Motivation After completing this excellent on , I wanted to get my hands dirty by solving something non-trivial. I also wanted to satiate the inner child artist in me by building something for myself for fun. hands-on course golang What started as a fun project soon became an obsession! I ended up building a mini sudoku-solver that uses and recursion to efficiently solve any valid sudoku fast. goroutines The project is hosted for folks who want to head to code directly. here Results Here's the result of a solver run executed on arguably . the world’s hardest sudoku ever Solution Approach The solver employs two different sub-approaches to solve a sudoku. The solver first maps the set of eligible numbers ( ) for each cell of sudoku. that can be filled It also the cells which have just a single eligible number. This is a step performed on each cell. fills map and reduce If each iteration of a sudoku scan keeps reducing the number of unfilled cells, the solver keeps repeating map and reduce until the sudoku is solved. Of course, the above technique solves only baby sudoku puzzles. When the number of cells stops reducing, the solver switches to a approach. unfilled trial and error This is where concurrency and goroutines come into play. This approach works as follows: The solver identifies the cell with . the least number of eligible numbers The solver then fires after creating a copy of sudoku with the eligible number filled at this cell. a goroutine as a recursive call to itself for each of these eligible numbers, In the next iteration, the solver picks up the next cell with least number of eligible numbers, and fires the next set of goroutines... and so on and so forth. This keeps repeating until either the sudoku is solved or a total of ten million (10, 000,000) iterations are exhausted. This approach results in a mega decision tree with each guess on a cell as a branch node. There is only one path which correctly solves the sudoku. When the solver hits this path, it returns the solved sudoku. Each thread of the solver works on a distinct copy of a sudoku to avoid data race. Key Learning Always use a channel (chan) or a struct with a chan to communicate with a go routine. Use wait groups to block execution until all the goroutines are completed. The below is a common pattern for firing multiple goroutines (as anonymous functions) and waiting for them to complete execution. { chanSudokuSolve := ( Channel)
	wg := (sync.WaitGroup) _, eligNum := cellToEvaluate.EligibleNumbers.GetList() {

		wg.Add( ) { wg.Done()

			_SudokuOut := sudokuIn.Copy()

			_SudokuOut.Fill(rowID, colID, fillVal)

			sudokuInter, _solved, _, _err := Solve(_SudokuOut)
			*c <- Channel{Intermediate: sudokuInter, Solved: _solved, Err: _err}
		}(SudokuOut, cellToEvaluate.RowID, cellToEvaluate.ColID, eligNum, wg, &chanSudokuSolve)
	} {
		wg.Wait() (c)
	}(wg, chanSudokuSolve) r := chanSudokuSolve {
		
	}
} func Solve (sudokuIn Sudoku) (Sudoku, , , error) bool int // Other parts of the code come here make chan new // fire a goroutine for each eligible nunber for range 1 // Call the solve function recursively, but as a go routine thread so that it executes asynchronously go func (sudokuIn Sudoku, rowID , colID , fillVal , wg *sync.WaitGroup, c * Channel) int int int chan defer // wait for the threads to be done & close channel once all threads are done go func (wg *sync.WaitGroup, c Channel) chan close // collect the results and look for the right guess for range Note that we do not have special wrapper function for Solve that deals with channels as a separate function parameter etc. All that complexity is handled in the anonymous block. This way of invoking goroutines keeps the function signature and code clean. Always run the code with race detector flag on to ensure that there is no data race. golang has a to detect data race conditions (i.e. scenarios when more than one goroutine in concurrently accessing the same memory address). powerful race detector I have modelled the sudoku as a slice of int slices. In the initial stages of coding, I was incorrectly copying the sudoku structure, which led to data race conditions and the solver was behaving super weird. _sudokuOut := (sudoku, (sudokuIn)) (_sudokuOut, sudokuIn) make len copy Once I detected the issue with race detector, I wrote a deep copy function for copying each element of a multi-dimensional slice, as follows: {
	mySudoku := (Sudoku, )
	done := ( {}) { _, _Row := s {
			myRow := (Row, ) _, _col := _Row {
				myRow = (myRow, _col)
			}
			mySudoku = (mySudoku, myRow)
		}
		done <- {}{}
	}()
	<-done mySudoku
} // Copy is a deep copy solution for Sudoku structure which is array of array of int func (s Sudoku) Copy () Sudoku make 0 make chan struct go func () for range make 0 for range append append struct return Of course, there are situations when a global variable must be accessed by multiple goroutines concurrently. A counter is a common example of this situation. In such situations, you can one of the following approaches: Use sync/atomic package and implement atomic counters. See . here For more complex management of state, use mutex. See . here I have used a simple atomic counter to count the number of iterations across all goroutines, as follows: globalCounter = ( ) {

	atomic.AddInt32(globalCounter, )
} var new int32 // Solve takes an unsolved sudoku and solves it. func Solve (sudokuIn Sudoku) (Sudoku, , , error) bool int 1 Use receiver functions on custom data types to model operations on the custom types. Here's an example of a receiver function that "receives" a Sudoku and validates whether it is solved or not. {
	myColumns := ( [ ]Row)
	myBoundedBoxes := ( [ ]Row) rowID, Row := s { !(Row.complete() && Row.nonRepeating()) { } colID, col := Row { myColumns[colID] = (myColumns[colID], col) bbID := _getBoundedBoxIndex(rowID, colID)
			myBoundedBoxes[bbID] = (myBoundedBoxes[bbID], col)
		}
	} (myColumns) > { _, Row := myColumns { !(Row.complete() && Row.nonRepeating()) { }
		}
	} (myBoundedBoxes) > { _, Row := myBoundedBoxes { !(Row.complete() && Row.nonRepeating()) { }
		}
	} } func (s Sudoku) Solved () bool make map int make map int // traverse the Sudoku once to collect Rows, columns and bounded boxes for range if return false for range // collect column values belonging to the same column id in a separate Row append // collect column values belonging to the same bounded box into a separate Row append if len 0 for range if return false if len 0 for range if return false return true At the risk of sounding pithy, receiver functions make golang "Classy". There are a number of excellent resources that explain receiver functions in depth. I especially liked and . this this Conclusion I was able to understand a number of intricate topics on golang through this tiny yet practical project. As a compiled, concurrent, garbage-collected, statically typed language, golang allows you to write efficient code fast and in the process have fun too! Thanks for reading!

Too Long; Didn't Read

Making security fun one episode at a time

Golang Sudoku Solver for Hard Sudoku Puzzles

Too Long; Didn't Read

Jeyabalaji Subramanian

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

Golang Sudoku Solver for Hard Sudoku Puzzles

Too Long; Didn't Read

Jeyabalaji Subramanian

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES