Last active
February 24, 2021 17:04
Punch holes in filled sudoku board
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment