Published: May 27, 2024
In a previous blogpost, I had written about how to create a complete sudoku grid like below. (Note that this sudoku grid is created in real time, so whenever you are visiting this page, the grid will change)
This is a follow-up post, where we will create a sudoku game out of this grid by removing some of the numbers and develop an algorithm to solve it.
The most difficult part of creating and solving a Sudoku game is creating the complete grid, which we already solved. There are 81 numbers in the grid, and we store those numbers in an array of size 81. This is how the generated data looks like:
let grid = [{ "row": 0, "col": 0, "block": "0-0", "value": 1 },
{ "row": 0, "col": 1, "block": "0-0", "value": 5 },
{ "row": 0, "col": 2, "block": "0-0", "value": 2 },
{ "row": 0, "col": 3, "block": "0-1", "value": 8 },
{ "row": 0, "col": 4, "block": "0-1", "value": 4 },
{ "row": 0, "col": 5, "block": "0-1", "value": 9 },
{ "row": 0, "col": 6, "block": "0-2", "value": 3 },
{ "row": 0, "col": 7, "block": "0-2", "value": 7 },
{ "row": 0, "col": 8, "block": "0-2", "value": 6 },
{ "row": 1, "col": 0, "block": "0-0", "value": 8 },
{ "row": 1, "col": 1, "block": "0-0", "value": 4 },
{ "row": 1, "col": 2, "block": "0-0", "value": 9 },
{ "row": 1, "col": 3, "block": "0-1", "value": 3 },
{ "row": 1, "col": 4, "block": "0-1", "value": 7 },
{ "row": 1, "col": 5, "block": "0-1", "value": 6 },
{ "row": 1, "col": 6, "block": "0-2", "value": 5 },
{ "row": 1, "col": 7, "block": "0-2", "value": 1 },
{ "row": 1, "col": 8, "block": "0-2", "value": 2 },
{ "row": 2, "col": 0, "block": "0-0", "value": 6 },
{ "row": 2, "col": 1, "block": "0-0", "value": 3 },
{ "row": 2, "col": 2, "block": "0-0", "value": 7 },
{ "row": 2, "col": 3, "block": "0-1", "value": 5 },
{ "row": 2, "col": 4, "block": "0-1", "value": 1 },
{ "row": 2, "col": 5, "block": "0-1", "value": 2 },
{ "row": 2, "col": 6, "block": "0-2", "value": 4 },
{ "row": 2, "col": 7, "block": "0-2", "value": 8 },
{ "row": 2, "col": 8, "block": "0-2", "value": 9 },
{ "row": 3, "col": 0, "block": "1-0", "value": 7 },
{ "row": 3, "col": 1, "block": "1-0", "value": 8 },
{ "row": 3, "col": 2, "block": "1-0", "value": 5 },
{ "row": 3, "col": 3, "block": "1-1", "value": 2 },
{ "row": 3, "col": 4, "block": "1-1", "value": 3 },
{ "row": 3, "col": 5, "block": "1-1", "value": 4 },
{ "row": 3, "col": 6, "block": "1-2", "value": 6 },
{ "row": 3, "col": 7, "block": "1-2", "value": 9 },
{ "row": 3, "col": 8, "block": "1-2", "value": 1 },
{ "row": 4, "col": 0, "block": "1-0", "value": 3 },
{ "row": 4, "col": 1, "block": "1-0", "value": 1 },
{ "row": 4, "col": 2, "block": "1-0", "value": 4 },
{ "row": 4, "col": 3, "block": "1-1", "value": 6 },
{ "row": 4, "col": 4, "block": "1-1", "value": 9 },
{ "row": 4, "col": 5, "block": "1-1", "value": 8 },
{ "row": 4, "col": 6, "block": "1-2", "value": 7 },
{ "row": 4, "col": 7, "block": "1-2", "value": 2 },
{ "row": 4, "col": 8, "block": "1-2", "value": 5 },
{ "row": 5, "col": 0, "block": "1-0", "value": 2 },
{ "row": 5, "col": 1, "block": "1-0", "value": 9 },
{ "row": 5, "col": 2, "block": "1-0", "value": 6 },
{ "row": 5, "col": 3, "block": "1-1", "value": 1 },
{ "row": 5, "col": 4, "block": "1-1", "value": 5 },
{ "row": 5, "col": 5, "block": "1-1", "value": 7 },
{ "row": 5, "col": 6, "block": "1-2", "value": 8 },
{ "row": 5, "col": 7, "block": "1-2", "value": 4 },
{ "row": 5, "col": 8, "block": "1-2", "value": 3 },
{ "row": 6, "col": 0, "block": "2-0", "value": 4 },
{ "row": 6, "col": 1, "block": "2-0", "value": 7 },
{ "row": 6, "col": 2, "block": "2-0", "value": 3 },
{ "row": 6, "col": 3, "block": "2-1", "value": 9 },
{ "row": 6, "col": 4, "block": "2-1", "value": 6 },
{ "row": 6, "col": 5, "block": "2-1", "value": 1 },
{ "row": 6, "col": 6, "block": "2-2", "value": 2 },
{ "row": 6, "col": 7, "block": "2-2", "value": 5 },
{ "row": 6, "col": 8, "block": "2-2", "value": 8 },
{ "row": 7, "col": 0, "block": "2-0", "value": 9 },
{ "row": 7, "col": 1, "block": "2-0", "value": 6 },
{ "row": 7, "col": 2, "block": "2-0", "value": 8 },
{ "row": 7, "col": 3, "block": "2-1", "value": 7 },
{ "row": 7, "col": 4, "block": "2-1", "value": 2 },
{ "row": 7, "col": 5, "block": "2-1", "value": 5 },
{ "row": 7, "col": 6, "block": "2-2", "value": 1 },
{ "row": 7, "col": 7, "block": "2-2", "value": 3 },
{ "row": 7, "col": 8, "block": "2-2", "value": 4 },
{ "row": 8, "col": 0, "block": "2-0", "value": 5 },
{ "row": 8, "col": 1, "block": "2-0", "value": 2 },
{ "row": 8, "col": 2, "block": "2-0", "value": 1 },
{ "row": 8, "col": 3, "block": "2-1", "value": 4 },
{ "row": 8, "col": 4, "block": "2-1", "value": 8 },
{ "row": 8, "col": 5, "block": "2-1", "value": 3 },
{ "row": 8, "col": 6, "block": "2-2", "value": 9 },
{ "row": 8, "col": 7, "block": "2-2", "value": 6 },
{ "row": 8, "col": 8, "block": "2-2", "value": 7 }]
Now let's randomly remove some numbers and create a newGrid. This will be our sudoku board.
You can choose the number of cells to be dropped below. You can drop between 10-50 cells.
The code for dropping cells can be found below:
let dropCount = 20;
function drop(dC) {
let indicesToBeDropped = Array.from({ length: grid.length }, (_, index) => index)
.map((value) => ({ value, sort: Math.random() }))
.sort((a, b) => a.sort - b.sort)
.map(({ value }) => value)
.slice(0, dC);
let nG = grid.map((number, index) => {
let newNumber = { ...number };
if (indicesToBeDropped.includes(index)) {
newNumber.value = '';
newNumber.empty = true;
}
return newNumber;
});
return nG;
}
let newGrid = drop(dropCount);
Here comes the interesting part as we'll solve the board and bring it back to its complete state, if we can.
But we don't know for sure whether the game is actually solvable so let's go ahead and solve it. Our data structure makes it super easy to solve this game as each number has an associated row, column and block number. We just need to filter the data that share the same row/ column/ block and see what number would fit in an empty cell.
Below is the code that solve the grid. The logic is explained in the code, but let me know in the comments if you have any question.
// Copy the earlier grid so that we don't modify it
// $ sign makes the new grid reactive based on earlier grid in svelte
$: gameGrid = newGrid.map((n) => {
return { ...n };
});
// For sleeping when each number is filled
// so that the user can see the algorithm working step by step
let timeout;
function sleep(time) {
return new Promise((resolve) => {
timeout = setTimeout(resolve, time);
return timeout;
});
}
// We keep a count so that if we exceed 1000 trials, we stop trying
let count = 0;
// Keep track of solving situation so that we can show a message
let solved = false;
// Solver function
async function solve() {
solved = false;
// Continue iterating until there is no cell where value === "" (ie empty cell)
while (gameGrid.filter((n) => n.value === '').length !== 0 && count < 1000) {
count++;
// Loop through all cells
for (let cellIndex = 0; cellIndex < gameGrid.length; cellIndex++) {
let cell = gameGrid[cellIndex];
// For an empty cell
if (cell.value === '') {
// Find numbers on the same row, column, and block as this cell
let rowNumbers = gameGrid.filter((i) => i.row === cell.row).map((i) => i.value);
let colNumbers = gameGrid.filter((i) => i.col === cell.col).map((i) => i.value);
let blockNumbers = gameGrid.filter((i) => i.block === cell.block).map((i) => i.value);
// Find numbers that can be put in this cell that are not present in row, column, and block
let rowPossibleNumbers = numbers.filter((i) => !rowNumbers.includes(i));
let colPossibleNumbers = numbers.filter((i) => !colNumbers.includes(i));
let blockPossibleNumbers = numbers.filter((i) => !blockNumbers.includes(i));
// Find the intersection of all possible numbers for this cell
let possibleNumbers = [rowPossibleNumbers, colPossibleNumbers, blockPossibleNumbers];
possibleNumbers = possibleNumbers.reduce((a, b) => a.filter((c) => b.includes(c)));
// If there is only 1 possible number, we found the correct number!
// Fill it in and sleep
if (possibleNumbers.length === 1) {
cell.value = possibleNumbers[0];
// update gameGrid so that it is visible in HTML DOM
gameGrid = [...gameGrid];
await sleep(100);
break;
}
}
}
}
clearTimeout(timeout);
solved = true;
}
Now, click below button to see if the algorithm is working as expected:
Tried 0 times
Try playing with the input field that was introduced above where you could control # number cells to be dropped. You'll see that as you approach dropping 50 cells, it becomes super difficult to solve the board within 1,000 tries.
In this blogpost we have devised a way to create a sudoku game out of complere board. The complete board creation topic was covered in an earlier blog.
After removing certain number of cells based on user input, we then use a brute-force approach to fill in the cells by looking at conditions such as whether the number is feasible w.r.t row, column, and block conditions.
If you have any questions, feel free to let me know by dropping a comment below.
Until further notice, happy hacking :)
Leave comment
Comments
Check out other blog posts
2024/06/19
Create A Simple and Dynamic Tooltip With Svelte and JavaScript
2024/06/17
Create an Interactive Map of Tokyo with JavaScript
2024/06/14
How to Easily Fix Japanese Character Issue in Matplotlib
2024/06/13
Book Review | Talking to Strangers: What We Should Know about the People We Don't Know by Malcolm Gladwell
2024/06/07
Most Commonly Used 3,000 Kanjis in Japanese
2024/06/07
Replace With Regex Using VSCode
2024/06/06
Do Not Use Readable Store in Svelte
2024/06/05
Increase Website Load Speed by Compressing Data with Gzip and Pako
2024/05/31
Find the Word the Mouse is Pointing to on a Webpage with JavaScript
2024/05/29
Create an Interactive Map with Svelte using SVG
2024/05/28
Book Review | Originals: How Non-Conformists Move the World by Adam Grant & Sheryl Sandberg
2024/05/26
How I Increased Traffic to my Website by 10x in a Month
2024/05/24
Life is Like Cycling
2024/05/19
Generate a Complete Sudoku Grid with Backtracking Algorithm in JavaScript
2024/05/16
Why Tailwind is Amazing and How It Makes Web Dev a Breeze
2024/05/15
Generate Sitemap Automatically with Git Hooks Using Python
2024/05/14
Book Review | Range: Why Generalists Triumph in a Specialized World by David Epstein
2024/05/13
What is Svelte and SvelteKit?
2024/05/12
Internationalization with SvelteKit (Multiple Language Support)
2024/05/11
Reduce Svelte Deploy Time With Caching
2024/05/10
Lazy Load Content With Svelte and Intersection Oberver
2024/05/10
Find the Optimal Stock Portfolio with a Genetic Algorithm
2024/05/09
Convert ShapeFile To SVG With Python
2024/05/08
Reactivity In Svelte: Variables, Binding, and Key Function
2024/05/07
Book Review | The Art Of War by Sun Tzu
2024/05/06
Specialists Are Dead. Long Live Generalists!
2024/05/03
Analyze Voter Behavior in Turkish Elections with Python
2024/05/01
Create Turkish Voter Profile Database With Web Scraping
2024/04/30
Make Infinite Scroll With Svelte and Tailwind
2024/04/29
How I Reached Japanese Proficiency In Under A Year
2024/04/25
Use-ready Website Template With Svelte and Tailwind
2024/01/29
Lazy Engineers Make Lousy Products
2024/01/28
On Greatness
2024/01/28
Converting PDF to PNG on a MacBook
2023/12/31
Recapping 2023: Compilation of 24 books read
2023/12/30
Create a Photo Collage with Python PIL
2024/01/09
Detect Device & Browser of Visitors to Your Website
2024/01/19
Anatomy of a ChatGPT Response