Last active
April 2, 2024 20:49
-
-
Save dsasse07/3ff7ae0eff2a7b3efd276e3f10f59f91 to your computer and use it in GitHub Desktop.
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 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 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
First puzzle I got is not solvable. It has multiple solutions.