Generating & Solving Sudoku in JS & Ruby with Backtracking

Update:

Thank you to edh_developer for helping me to identify an issue with multiple possible boards being generated. The gist code has been updated.

Sudoku

Puzzle games like Sudoku have always fascinated me, and Sudoku in particular has helped me get through many long waits. It is a quite popular game, but for those unfamiliar with the rules here is a quick synopsis, or you can see the Wikipedia entry here.

---

A Sudoku game begins with a 9x9 grid partially filled with values from 1 to 9. The goal for the player, is to fill all of the remaining boxes with values from 1–9. However, each number that a player inserts must pass three strict rules:

1. Each value 1–9 can only be present once in a row. So in the example board above, 5, 3, and 7 cannot be written into any of the empty cells in the first row.

2. Each value 1–9 can only be present once in a column. So in the example board above, 5, 6, 8, 4, and 7 cannot be written into any of the empty cells in the first column.

3. Each value 1–9 can only be present once within a grid region. A grid region is a smaller 3x3 grid within the larger Sudoku board. These regions can be seen in the board above by their bolded borders. For example, the top-left region contains the values 5,3,6,8, and 9, and so these values cannot be placed again into any of the empty cells remaining in this region.

Solving these puzzles by hand involves meticulously comparing values against these rules and inserting them if they pass. Using similar logic in a backtracking algorithm, we can write a small script that can both generate and solve these boards as well. Let’s break it down here, or skip to the bottom for the full code.

---

Backtracking

Backtracking is an algorithmic approach to solving problems under specific constraints (sounds like Sudoku to me!) in which a value is entered if it meets the conditions and then the algorithm proceeds to the next value. However, if the algorithm is unable to place these subsequent values, it will backtrack to the last successfully placed value and change it to the next possible successful value and continue again.

---

Implementation

I implemented the backtracking solution in both Javascript and Ruby. I have outlined the process and components in Javascript below, but the full code for both Ruby and Javascript can be found at the bottom of this article.

Placement Criteria

To begin implementing this algorithm, we must first define what our successful criteria are: rowSafe checks the uniqueness of the values in the row, colSafe checks it in the column and boxSafe in the 3x3 grid. Then, we need to evaluate whether the coordinates of the emptyCell (which is a JS object or Ruby hash containing both coordinates)

• To check the row, we can pick the row of puzzleArray that is specified in the emptyCell coordinates and see if it contains the num value we are trying to insert by looking for the index of that value.

	// puzzleArray is the game board being solved. A 9x9 matrix
	// emptyCell = {rowIndex: INT , colIndex: INT } INT = coordinates of currently empty cell
	// num = integer value 1-9 being tested
	const rowSafe = (puzzleArray, emptyCell, num) => {
	// -1 is return value of .find() if value not found
	return puzzleArray[ emptyCell.rowIndex ].indexOf(num) == -1
	}

view raw sudoku-row-condition.js hosted with ❤ by GitHub

• To check the column, we can examine the column index of emptyCell for each row and see if any of them contain that value. In Javascript .some() will return true if at least one of the values of array meet the condition.

	// puzzleArray is the game board being solved. A 9x9 matrix
	// emptyCell = {rowIndex: INT , colIndex: INT } INT = coordinates of currently empty cell
	// num = integer value 1-9 being tested
	const colSafe = (puzzleArray, emptyCell, num) => {
	return !puzzleArray.some(row => row[ emptyCell.colIndex ] == num )
	}

view raw sudoku-col-condition.js hosted with ❤ by GitHub

• The region condition is trickier, because we must first determine which region the cell belongs to. Each region begins on rows 0, 3, and 6 and columns 0, 3, and 6. Using a combination of subtraction and modulus with the coordinates of the empty cell, we can determine the top-left most cell of the region which the cell belongs to. Then, we scan through the region and look for a match

	// puzzleArray is the game board being solved. A 9x9 matrix
	// emptyCell = {rowIndex: INT , colIndex: INT } INT = coordinates of currently empty cell
	// num = integer value 1-9 being tested
	const boxSafe = (puzzleArray, emptyCell, num) => {
	// Define top left corner of box region for empty cell
	boxStartRow = emptyCell.rowIndex - (emptyCell.rowIndex % 3)
	boxStartCol = emptyCell.colIndex - (emptyCell.colIndex % 3)
	let safe = true
	for ( boxRow of [0,1,2] ) { // Each box region has 3 rows
	for ( boxCol of [0,1,2] ) { // Each box region has 3 columns
	// Is num is present in box region?
	if ( puzzleArray[boxStartRow + boxRow][boxStartCol + boxCol] == num ) {
	safe = false // If number is found, it is not safe to place
	}
	}
	}
	return safe
	}

view raw sudoku-box-condition.js hosted with ❤ by GitHub

• Since all three criteria must be met to pass, we can check that all conditions are met with a helper function.

	const safeToPlace = ( puzzleArray, emptyCell, num ) => {
	return rowSafe(puzzleArray, emptyCell, num) &&
	colSafe(puzzleArray, emptyCell, num) &&
	boxSafe(puzzleArray, emptyCell, num)
	}

view raw sudoku-safe-helper.js hosted with ❤ by GitHub

Generating a Game Board

To generate a game board, we first start by making a completely filled, and correctly solved board out of a completely blank board. The range of values 1 to 9 is shuffled at the start of each iteration, ensuring the that probability of each new game being similar is low. Since each successful placement of a number will be followed by another attempt to place a number, this fillPuzzle function will recursively call itself. Since this can get a bit tricky, let’s outline the steps before we see the code:

• Obtain an empty 9x9 matrix filled with zeros.
• Scan the matrix for the next cell with a current value of zero.

	const nextEmptyCell = puzzleArray => {
	const emptyCell = {rowIndex: "", colIndex: ""}
	puzzleArray.forEach( (row, rowIndex) => {
	// If this key has already been assigned, skip iteration
	if (emptyCell.colIndex !== "" ) return
	// find first zero-element
	let firstZero = row.find( col => col === 0)
	// if no zero present, skip to next row
	if (firstZero === undefined) return;
	emptyCell.rowIndex = rowIndex
	emptyCell.colIndex = row.indexOf(firstZero)
	})
	if (emptyCell.colIndex !== "") return emptyCell
	// If emptyCell was never assigned, there are no more zeros
	return false
	}

view raw sudoku-next-empty.js hosted with ❤ by GitHub

• Randomize the array [0,1,2,3,4,5,6,7,8,9] and attempt to place the first value of that shuffled array into the empty cell found above.

• Insert a conditional to abort the script if board fails to generate within a certain number of iterations. Most boards will generate in < 500ms, but random generation can lead to long wait times on occasion. I will discuss this more in the initialize section.

• If the value from the shuffled array passes all of the safety checks, insert it and go back to step 2.

• If the value from the shuffled array fails the safety check, return the cell to zero, and go back to the previously placed number and try to change it to the next possible value from the shuffled array and repeat.

	// startingBoard is a 9x9 matrix of zeros
	const numArray = [1, 2, 3, 4, 5, 6, 7, 8, 9]
	const shuffle = array => {
	let newArray = [...array]
	for ( let i = newArray.length - 1; i > 0; i-- ) {
	const j = Math.floor( Math.random() * ( i + 1 ) );
	[ newArray[ i ], newArray[ j ] ] = [ newArray[ j ], newArray[ i ] ];
	}
	return newArray;
	}
	const fillPuzzle = startingBoard => {
	const emptyCell = nextEmptyCell(startingBoard)
	// If there are no more zeros, the board is finished, return it
	return startingBoard if (!emptyCell)
	for (num of shuffle(numArray) ) {
	// counter is a global variable tracking the number of iterations performed in generating a puzzle
	// Most puzzles generate in < 500ms, but occassionally random generation could run in to
	// heavy backtracking and result in a long wait. Best to abort this attempt and restart.
	// See initializer function for more
	counter++
	if ( counter > 20_000_000 ) throw new Error ("Recursion Timeout")
	if ( safeToPlace( startingBoard, emptyCell, num) ) {
	// If safe to place number, place it
	startingBoard[ emptyCell.rowIndex ][ emptyCell.colIndex ] = num
	// Recursively call the fill function to place num in next empty cell
	return startingBoard if ( fillPuzzle(startingBoard) )
	// If we were unable to place the future num, that num was wrong.
	// Reset it and try next
	startingBoard[ emptyCell.rowIndex ][ emptyCell.colIndex ] = 0
	}
	}
	// If unable to place any number, return false,
	// causing previous round to go to next num
	return false
	}

view raw sudoku-fill-puzzle.js hosted with ❤ by GitHub

Generating a Playable Board

Hooray! We have a completely filled Sudoku board that meets all of the criteria for the game! However, if you actually wanted to play the game, you need to “poke some holes” in it to make it playable. We can remove these cells at random; however, we must ensure that the removal of a value creates a board that can still be solved AND that it leads to a unique solution - as in there is only one way to place the numbers and win.

If the board can no longer be solved, or a second possible solution is found, we will put the value back and pick a different random cell to remove. As a bonus to this method, we can create an ordered list of the coordinates and value of each removed item if we ever need a hint. To this function we must pass in an integer number of holes to punch into the board. The more holes there are, the more difficult the board will be.

	const pokeHoles = (startingBoard, holes) => {
	const removedVals = []
	const val = shuffle( range(0,80) )
	while (removedVals.length < holes) {
	const nextVal = val.pop()
	if (nextVal === undefined) throw new Error ("Impossible Game")
	const randomRowIndex = Math.floor(nextVal / 9) // Integer 0-8 for row index
	const randomColIndex = nextVal % 9
	if (!startingBoard[ randomRowIndex ]) continue // guard against cloning error
	if ( startingBoard[ randomRowIndex ][ randomColIndex ] == 0 ) continue // If cell already empty, restart loop
	removedVals.push({ // Store the current value at the coordinates
	rowIndex: randomRowIndex,
	colIndex: randomColIndex,
	val: startingBoard[ randomRowIndex ][ randomColIndex ]
	})
	startingBoard[ randomRowIndex ][ randomColIndex ] = 0 // "poke a hole" in the board at the coords
	const proposedBoard = startingBoard.map ( row => row.slice() ) // Clone this changed board
	// Attempt to solve the board after removing value. If it cannot be solved, restore the old value.
	// and remove that option from the list
	if ( multiplePossibleSolutions( startingBoard.map ( row => row.slice() ) ) ) {
	startingBoard[ randomRowIndex ][ randomColIndex ] = removedVals.pop().val
	}
	}
	return [removedVals, startingBoard]
	}
	// The board will be completely solved once for each item in the empty cell list.
	// The empty cell array is rotated on each iteration, so that the order of the empty cells
	// And thus the order of solving the game, is different each time.
	// The solution for each attempt is pushed to a possibleSolutions array as a string
	// Multiple solutions are identified by taking a unique Set from the possible solutions
	// and measuring its length. If multiple possible solutions are found at any point
	// If will return true, prompting the pokeHoles function to select a new value for removal.
	function multiplePossibleSolutions (boardToCheck) {
	const possibleSolutions = []
	const emptyCellArray = emptyCellCoords(boardToCheck)
	for (let index = 0; index < emptyCellArray.length; index++) {
	// Rotate a clone of the emptyCellArray by one for each iteration
	emptyCellClone = [...emptyCellArray]
	const startingPoint = emptyCellClone.splice(index, 1);
	emptyCellClone.unshift( startingPoint[0] )
	thisSolution = fillFromArray( boardToCheck.map( row => row.slice() ) , emptyCellClone)
	possibleSolutions.push( thisSolution.join() )
	if (Array.from(new Set(possibleSolutions)).length > 1 ) return true
	}
	return false
	}

view raw sudoku-hole-puncher.js hosted with ❤ by GitHub

Results

All that is left is to run the script and receive the startingBoard , solvedBoard , and list of removedVals in an instant! Notice that in the initializing function newStartingBoard we will try to create a game. Most games will be created in <500 ms, but to prevent the occasional long wait, the iteration counter in fillPuzzle will throw an error and abort the script after a specified time. We will catch this error and use it to re-trigger the initialize function. It is faster to abandon puzzles with abnormally long generation times and start over than it is to wait them out.

	const newSolvedBoard = _ => {
	startTime = new Date
	// Create an unaffiliated clone of a fresh board
	const newBoard = BLANK_BOARD.map(row => row.slice() )
	// Populate the board using backtracking algorithm
	fillPuzzle(newBoard)
	return newBoard
	}
	function newStartingBoard (holes) {
	// Reset global iteration counter to 0 and Try to generate a new game.
	// If counter reaches its maximum limit in the fillPuzzle function, current attemp will abort
	// To prevent the abort from crashing the script, the error is caught and used to re-run
	// this function
	try {
	counter = 0
	let solvedBoard = newSolvedBoard()
	// Clone the populated board and poke holes in it.
	// Stored the removed values for clues
	let [removedVals, startingBoard] = pokeHoles( solvedBoard.map ( row => row.slice() ), holes)
	return [removedVals, startingBoard, solvedBoard]
	} catch (error)
	return newStartingBoard(holes)
	}
	}

view raw sudoku-initialize-functions.js hosted with ❤ by GitHub

And now join me in forever feeling incredibly slow when trying to solve these puzzles by hand.

Resources

• Use Backtracking to Solve Sudoku by:

  

  ChristinaFollow

  Junior Developer at Interplay Learning - Feel free to contact me via LinkedIn or connect on Github, I am always happy to chat with folks from this community!

• Sudoku Generator Algorithm by: 101Computing

Full Code

• Javascript
• Ruby

Javascript - Full Code

• JS Gist External Link

	const BLANK_BOARD = [
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0]
	]
	let counter
	const numArray = [1, 2, 3, 4, 5, 6, 7, 8, 9]
	function shuffle( array ) {
	let newArray = [...array]
	for ( let i = newArray.length - 1; i > 0; i-- ) {
	const j = Math.floor( Math.random() * ( i + 1 ) );
	[ newArray[ i ], newArray[ j ] ] = [ newArray[ j ], newArray[ i ] ];
	}
	return newArray;
	}
	/*--------------------------------------------------------------------------------------------
	--------------------------------- Check if Location Safe -------------------------------------
	--------------------------------------------------------------------------------------------*/
	const rowSafe = (puzzleArray, emptyCell, num) => {
	// -1 is return value of .find() if value not found
	return puzzleArray[ emptyCell.rowIndex ].indexOf(num) == -1
	}
	const colSafe = (puzzleArray, emptyCell, num) => {
	return !puzzleArray.some(row => row[ emptyCell.colIndex ] == num )
	}
	const boxSafe = (puzzleArray, emptyCell, num) => {
	boxStartRow = emptyCell.rowIndex - (emptyCell.rowIndex % 3) // Define top left corner of box region for empty cell
	boxStartCol = emptyCell.colIndex - (emptyCell.colIndex % 3)
	let safe = true
	for ( boxRow of [0,1,2] ) { // Each box region has 3 rows
	for ( boxCol of [0,1,2] ) { // Each box region has 3 columns
	if ( puzzleArray[boxStartRow + boxRow][boxStartCol + boxCol] == num ) { // Num is present in box region?
	safe = false // If number is found, it is not safe to place
	}
	}
	}
	return safe
	}
	const safeToPlace = ( puzzleArray, emptyCell, num ) => {
	return rowSafe(puzzleArray, emptyCell, num) &&
	colSafe(puzzleArray, emptyCell, num) &&
	boxSafe(puzzleArray, emptyCell, num)
	}
	/*--------------------------------------------------------------------------------------------
	--------------------------------- Obtain Next Empty Cell -------------------------------------
	--------------------------------------------------------------------------------------------*/
	const nextEmptyCell = puzzleArray => {
	const emptyCell = {rowIndex: "", colIndex: ""}
	puzzleArray.forEach( (row, rowIndex) => {
	if (emptyCell.colIndex !== "" ) return // If this key has already been assigned, skip iteration
	let firstZero = row.find( col => col === 0) // find first zero-element
	if (firstZero === undefined) return; // if no zero present, skip to next row
	emptyCell.rowIndex = rowIndex
	emptyCell.colIndex = row.indexOf(firstZero)
	})
	if (emptyCell.colIndex !== "" ) return emptyCell
	// If emptyCell was never assigned, there are no more zeros
	return false
	}
	/*--------------------------------------------------------------------------------------------
	--------------------------------- Generate Filled Board -------------------------------------
	--------------------------------------------------------------------------------------------*/
	const fillPuzzle = startingBoard => {
	const emptyCell = nextEmptyCell(startingBoard)
	// If there are no more zeros, the board is finished, return it
	if (!emptyCell) return startingBoard
	// Shuffled [0 - 9 ] array fills board randomly each pass
	for (num of shuffle(numArray) ) {
	// counter is a global variable tracking the number of iterations performed in generating a puzzle
	// Most puzzles generate in < 500ms, but occassionally random generation could run in to
	// heavy backtracking and result in a long wait. Best to abort this attempt and restart.
	// 20_000_000 iteration maximum is approximately 1.3 sec runtime.
	// See initializer function for more
	counter++
	if ( counter > 20_000_000 ) throw new Error ("Recursion Timeout")
	if ( safeToPlace( startingBoard, emptyCell, num) ) {
	startingBoard[ emptyCell.rowIndex ][ emptyCell.colIndex ] = num // If safe to place number, place it
	// Recursively call the fill function to place num in next empty cell
	if ( fillPuzzle(startingBoard) ) return startingBoard
	// If we were unable to place the future num, that num was wrong. Reset it and try next value
	startingBoard[ emptyCell.rowIndex ][ emptyCell.colIndex ] = 0
	}
	}
	return false // If unable to place any number, return false, which triggers previous round to go to next num
	}
	const newSolvedBoard = _ => {
	const newBoard = BLANK_BOARD.map(row => row.slice() ) // Create an unaffiliated clone of a fresh board
	fillPuzzle(newBoard) // Populate the board using backtracking algorithm
	return newBoard
	}
	/*--------------------------------------------------------------------------------------------
	--------------------------------- Generate Playable Board ------------------------------------
	--------------------------------------------------------------------------------------------*/
	const pokeHoles = (startingBoard, holes) => {
	const removedVals = []
	while (removedVals.length < holes) {
	const val = Math.floor(Math.random() * 81) // Value between 0-81
	const randomRowIndex = Math.floor(val / 9) // Integer 0-8 for row index
	const randomColIndex = val % 9
	if (!startingBoard[ randomRowIndex ]) continue // guard against cloning error
	if ( startingBoard[ randomRowIndex ][ randomColIndex ] == 0 ) continue // If cell already empty, restart loop
	removedVals.push({ // Store the current value at the coordinates
	rowIndex: randomRowIndex,
	colIndex: randomColIndex,
	val: startingBoard[ randomRowIndex ][ randomColIndex ]
	})
	startingBoard[ randomRowIndex ][ randomColIndex ] = 0 // "poke a hole" in the board at the coords
	const proposedBoard = startingBoard.map ( row => row.slice() ) // Clone this changed board
	// Attempt to solve the board after removing value. If it cannot be solved, restore the old value.
	// and remove that option from the list
	if ( !fillPuzzle( proposedBoard ) ) {
	startingBoard[ randomRowIndex ][ randomColIndex ] = removedVals.pop().val
	}
	}
	return [removedVals, startingBoard]
	}
	/*--------------------------------------------------------------------------------------------
	--------------------------------- Initialize -------------------------------------
	--------------------------------------------------------------------------------------------*/
	function newStartingBoard (holes) {
	// Reset global iteration counter to 0 and Try to generate a new game.
	// If counter reaches its maximum limit in the fillPuzzle function, current attemp will abort
	// To prevent the abort from crashing the script, the error is caught and used to re-run
	// this function
	try {
	counter = 0
	let solvedBoard = newSolvedBoard()
	// Clone the populated board and poke holes in it.
	// Stored the removed values for clues
	let [removedVals, startingBoard] = pokeHoles( solvedBoard.map ( row => row.slice() ), holes)
	return [removedVals, startingBoard, solvedBoard]
	} catch (error)
	return newStartingBoard(holes)
	}
	}
	// The board will be completely solved once for each item in the empty cell list.
	// The empty cell array is rotated on each iteration, so that the order of the empty cells
	// And thus the order of solving the game, is different each time.
	// The solution for each attempt is pushed to a possibleSolutions array as a string
	// Multiple solutions are identified by taking a unique Set from the possible solutions
	// and measuring its length. If multiple possible solutions are found at any point
	// If will return true, prompting the pokeHoles function to select a new value for removal.
	function multiplePossibleSolutions (boardToCheck) {
	const possibleSolutions = []
	const emptyCellArray = emptyCellCoords(boardToCheck)
	for (let index = 0; index < emptyCellArray.length; index++) {
	// Rotate a clone of the emptyCellArray by one for each iteration
	emptyCellClone = [...emptyCellArray]
	const startingPoint = emptyCellClone.splice(index, 1);
	emptyCellClone.unshift( startingPoint[0] )
	thisSolution = fillFromArray( boardToCheck.map( row => row.slice() ) , emptyCellClone)
	possibleSolutions.push( thisSolution.join() )
	if (Array.from(new Set(possibleSolutions)).length > 1 ) return true
	}
	return false
	}
	// This will attempt to solve the puzzle by placing values into the board in the order that
	// the empty cells list presents
	function fillFromArray(startingBoard, emptyCellArray) {
	const emptyCell = nextStillEmptyCell(startingBoard, emptyCellArray)
	if (!emptyCell) return startingBoard
	for (num of shuffle(numArray) ) {
	pokeCounter++
	if ( pokeCounter > 60_000_000 ) throw new Error ("Poke Timeout")
	if ( safeToPlace( startingBoard, emptyCell, num) ) {
	startingBoard[ emptyCell.rowIndex ][ emptyCell.colIndex ] = num
	if ( fillFromArray(startingBoard, emptyCellArray) ) return startingBoard
	startingBoard[ emptyCell.rowIndex ][ emptyCell.colIndex ] = 0
	}
	}
	return false
	}
	// As numbers get placed, not all of the initial cells are still empty.
	// This will find the next still empty cell in the list
	function nextStillEmptyCell (startingBoard, emptyCellArray) {
	for (coords of emptyCellArray) {
	if (startingBoard[ coords.row ][ coords.col ] === 0) return {rowIndex: coords.row, colIndex: coords.col}
	}
	return false
	}
	// Generate array from range, inclusive of start & endbounds.
	const range = (start, end) => {
	const length = end - start + 1
	return Array.from( {length} , ( _ , i) => start + i)
	}
	// Get a list of all empty cells in the board from top-left to bottom-right
	function emptyCellCoords (startingBoard) {
	const listOfEmptyCells = []
	for (const row of range(0,8)) {
	for (const col of range(0,8) ) {
	if (startingBoard[row][col] === 0 ) listOfEmptyCells.push( {row, col } )
	}
	}
	return listOfEmptyCells
	}

view raw sudoku-full.js hosted with ❤ by GitHub

Ruby - Full Code

• Ruby Gist External Link

	class Sudoku
	attr_accessor :starting_board, :solution, :removed_values, :difficulty
	BLANK_BOARD = [
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0]
	]
	def initialize(holes = 30)
	holes > 64 ? 64 : holes
	generate_game(holes)
	end
	def generate_game(holes)
	begin
	@iteration_counter = 0
	self.solution = new_solved_board
	self.removed_values, self.starting_board = poke_holes(self.solution.map(&:clone), holes)
	self.difficulty = holes
	rescue
	generate_game(holes)
	end
	end
	def new_solved_board
	new_board = BLANK_BOARD.map(&:clone)
	solve(new_board)
	new_board
	end
	def solve (puzzle_matrix)
	empty_cell = find_next_empty_cell(puzzle_matrix)
	return puzzle_matrix if !empty_cell #If no empty cells, we are done. Return the completed puzzle
	# Fill in the empty cell
	for num in (1..9).to_a.shuffle do
	raise if (@iteration_counter > 1_000_000) #Abandon current attempt and start over if recursion attempt takes too long
	if safe(puzzle_matrix, empty_cell, num) # For a number, check if it safe to place that number in the empty cell
	puzzle_matrix[empty_cell[:row_i]][empty_cell[:col_i]] = num # if safe, place number
	return puzzle_matrix if solve(puzzle_matrix) # Recursively call solve method again.
	puzzle_matrix[empty_cell[:row_i]][empty_cell[:col_i]] = 0
	end
	end
	return false #If unable to place a number, return false, trigerring previous iteration to move to next number
	end
	def find_next_empty_cell(puzzle_matrix)
	# Find the coordinates of the next unsolved cell
	empty_cell = {row_i:"",col_i:""}
	for row in puzzle_matrix do
	next_zero_index = row.find_index(0)
	empty_cell[:row_i] = puzzle_matrix.find_index(row)
	empty_cell[:col_i] = next_zero_index
	return empty_cell if empty_cell[:col_i]
	end
	return false
	end
	def safe(puzzle_matrix, empty_cell, num)
	row_safe(puzzle_matrix, empty_cell, num) &&
	col_safe(puzzle_matrix, empty_cell, num) &&
	box_safe(puzzle_matrix, empty_cell, num)
	end
	def row_safe (puzzle_matrix, empty_cell, num)
	!puzzle_matrix[ empty_cell[:row_i] ].find_index(num)
	end
	def col_safe (puzzle_matrix, empty_cell, num)
	!puzzle_matrix.any?{|row| row[ empty_cell[:col_i] ] == num}
	end
	def box_safe (puzzle_matrix, empty_cell, num)
	box_start_row = (empty_cell[:row_i] - (empty_cell[:row_i] % 3))
	box_start_col = (empty_cell[:col_i] - (empty_cell[:col_i] % 3))
	(0..2).to_a.each do |box_row|
	(0..2).to_a.each do |box_col|
	return false if puzzle_matrix[box_start_row + box_row][box_start_col + box_col] == num
	end
	end
	return true
	end
	def poke_holes(puzzle_matrix, holes)
	removed_values = []
	while removed_values.length < holes
	row_i = (0..8).to_a.sample
	col_i = (0..8).to_a.sample
	next if (puzzle_matrix[row_i][col_i] == 0)
	removed_values.push({row_i: row_i, col_i: col_i, val: puzzle_matrix[row_i][col_i] })
	puzzle_matrix[row_i][col_i] = 0
	proposed_board = puzzle_matrix.map(&:clone)
	puzzle_matrix[row_i][col_i] = removed_values.pop[:val] if !solve( proposed_board )
	end
	[removed_values, puzzle_matrix]
	end
	end

view raw sudoku-full.rb hosted with ❤ by GitHub

Comments

[edh_developer]

In the puzzle generating code, I think it can generate and return puzzles with multiple solutions. Am I missing something that prevents that from happening?

[Daniel Sasse]

Hi edh_developer, from what I have understood from looking into this, the process of generating the board, and then running the solve function to test the removal of each value to create a starting board should account for this. I haven't come across an edge case where this has not worked yet, so it is quite possible I could have missed something, or that my understanding is a bit off. If you have any specific advice I would be happy to chat with you about it and make any necessary revisions. Thank you!

[edh_developer]

Here's an example of a puzzle with two solutions:

sandwalk.blogspot.com/2007/06/i-kn...

It's possible for your code to randomly generate this puzzle, or one like it. The solver would then find one of the two solutions and return it, without checking for alternate solutions. It wouldn't catch the given example, and it may even return a different solution than the one you started with.

[edh_developer]

I tried it. I added this to the end of your source and ran it:

def printboard(board)
  i = 1
  for row in board
    puts "#{row[0]} #{row[1]} #{row[2]} | #{row[3]} #{row[4]} #{row[5]} | #{row[6]} #{row[7]} #{row[8]}"
    if i == 3 || i == 6 then puts "---------------------" end
    i += 1
  end
end

SOLUTION = [
    [9, 2, 6, 5, 7, 1, 4, 8, 3],
    [3, 5, 1, 4, 8, 6, 2, 7, 9],
    [8, 7, 4, 9, 2, 3, 5, 1, 6],
    [5, 8, 2, 3, 6, 7, 1, 9, 4],
    [1, 4, 9, 2, 5, 8, 3, 6, 7],
    [7, 6, 3, 1, 4, 9, 8, 2, 5],
    [2, 3, 8, 7, 9, 4, 6, 5, 1],
    [6, 1, 7, 8, 3, 5, 9, 4, 2],
    [4, 9, 5, 6, 1, 2, 7, 3, 8]
]
# Could have been randomly generated by
# poke_holes(SOLUTION,52)
PUZZLE = [
    [9, 0, 6, 0, 7, 0, 4, 0, 3],
    [0, 0, 0, 4, 0, 0, 2, 0, 0],
    [0, 7, 0, 0, 2, 3, 0, 1, 0],
    [5, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 4, 0, 2, 0, 8, 0, 6, 0],
    [0, 0, 3, 0, 0, 0, 0, 0, 5],
    [0, 3, 0, 7, 0, 0, 0, 5, 0],
    [0, 0, 7, 0, 0, 5, 0, 0, 0],
    [4, 0, 5, 0, 1, 0, 7, 0, 8]
]

puts "\nOriginal Puzzle:\n\n"
printboard(SOLUTION)

puts "\n\nGenerated Solution:\n\n"
printboard(Sudoku.new.solve(PUZZLE))

The resulting output:

$ ruby sudoku-full.rb

Original Puzzle:

9 2 6 | 5 7 1 | 4 8 3
3 5 1 | 4 8 6 | 2 7 9
8 7 4 | 9 2 3 | 5 1 6
---------------------
5 8 2 | 3 6 7 | 1 9 4
1 4 9 | 2 5 8 | 3 6 7
7 6 3 | 1 4 9 | 8 2 5
---------------------
2 3 8 | 7 9 4 | 6 5 1
6 1 7 | 8 3 5 | 9 4 2
4 9 5 | 6 1 2 | 7 3 8

Generated Solution:

9 2 6 | 5 7 1 | 4 8 3
3 5 1 | 4 8 6 | 2 7 9
8 7 4 | 9 2 3 | 5 1 6
---------------------
5 8 2 | 3 6 7 | 1 9 4
1 4 9 | 2 5 8 | 3 6 7
7 6 3 | 1 9 4 | 8 2 5
---------------------
2 3 8 | 7 4 9 | 6 5 1
6 1 7 | 8 3 5 | 9 4 2
4 9 5 | 6 1 2 | 7 3 8

[Daniel Sasse]

Thank you! I was able to replicate this using a few different boards after your tip. I wrote a multipleSolutions check that now attempts to solve the puzzle from each of the currently empty positions and if more than one unique solution is found it will replace the removed value and attempt to remove a different one. I believe there is a more efficient solution, but this fix is working in the meantime for our app (fludoku.netlify.app). I coded the fix in JS first for the app, and will be working to update the ruby gist and gem to match. Thank you again!

[alpsinan]

The code works excellent down to 30 clues puzzles. It finds puzzles with 29 clues very slowly. Puzzles with 28 clues and less takes ages. (1-2 hours?) But Puzzles with 26 clues are very common. It is nearly impossible to find a puzzle with 26 clues.

[Sylwia Vargas]

This is a terrific blog post! Great piece of writing. I love how you guide a code newbie through this process. I’m so happy that you’re documenting your dev process along the way!