-
-
Save dsasse07/3ff7ae0eff2a7b3efd276e3f10f59f91 to your computer and use it in GitHub Desktop.
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 | |
} |
function newStartingBoard(holes){…}
is used to initialize a new board and retrieve the solution map. You could pass the starting board in to function fillPuzzle(startingBoard){…}
to solve directly if the solution map is not available
holes
Is the number of empty spaces you would like for the board starting board to have. As a note, the more empty spaces you desire the longer it will take to generate a board as it needs to ensure that there is only one valid solution to the board as it removes additional values. The max I have tried this with was 57
Very fast code. But initialization of the pokeCounter variable is missing!
@SirPhemmiey Im not sure why the base case isn’t being hit for you to stop the stack overflow. It’s been a while since I wrote this. When I have some free time I’ll debug a bit and comment back
First puzzle I got is not solvable. It has multiple solutions.
847 | 9 | 1 5
39 | | 27
| 8 | 4
---------------
62 | 3 |
5 | 62 |
9 | 184 | 56
---------------
45 | 9 7 | 618
768 | 2 | 3
1 9 | 6 | 47
Hey Dan, helpful script right here.
But how to run it? What's the
init
function to run?