Skip to content

Instantly share code, notes, and snippets.

@dsasse07
Last active February 24, 2021 17:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save dsasse07/ee1ff3e1595c0d016db22c8605fcf3ee to your computer and use it in GitHub Desktop.
Save dsasse07/ee1ff3e1595c0d016db22c8605fcf3ee to your computer and use it in GitHub Desktop.
Punch holes in filled sudoku board
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