Danyel Koca Danyel Koca

How to Algorithmically Solve Sudoku Using Javascript

Published: May 27, 2024

How to Algorithmically Solve Sudoku Using Javascript

Background

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)

1
5
2
8
4
9
3
7
6
8
4
9
3
7
6
5
1
2
6
3
7
5
1
2
4
8
9
7
8
5
2
3
4
6
9
1
3
1
4
6
9
8
7
2
5
2
9
6
1
5
7
8
4
3
4
7
3
9
6
1
2
5
8
9
6
8
7
2
5
1
3
4
5
2
1
4
8
3
9
6
7

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.

Sudoku Data Generation

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 }]

Creating Sudoku Game by Removing Numbers

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.

1
2
8
4
9
3
7
8
4
3
7
6
5
1
2
6
7
5
2
4
9
5
3
4
6
3
1
4
6
9
8
7
2
5
2
6
1
5
8
4
3
4
7
3
9
6
1
2
5
6
8
7
2
5
1
4
1
4
3
6
7

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);

Solving the Sudoku Game

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:

1
2
8
4
9
3
7
8
4
3
7
6
5
1
2
6
7
5
2
4
9
5
3
4
6
3
1
4
6
9
8
7
2
5
2
6
1
5
8
4
3
4
7
3
9
6
1
2
5
6
8
7
2
5
1
4
1
4
3
6
7

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.

Conclusion

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

Create A Simple and Dynamic Tooltip With Svelte and JavaScript

2024/06/19

Create A Simple and Dynamic Tooltip With Svelte and JavaScript

JavaScriptSvelteSimpleDynamicTooltipFront-end
Create an Interactive Map of Tokyo with JavaScript

2024/06/17

Create an Interactive Map of Tokyo with JavaScript

SvelteSVGJavaScriptTailwindInteractive MapTokyoJapanTokyo Metropolitan Area23 Wards
How to Easily Fix Japanese Character Issue in Matplotlib

2024/06/14

How to Easily Fix Japanese Character Issue in Matplotlib

MatplotlibGraphChartPythonJapanese charactersIssueBug
Book Review | Talking to Strangers: What We Should Know about the People We Don't Know by Malcolm Gladwell

2024/06/13

Book Review | Talking to Strangers: What We Should Know about the People We Don't Know by Malcolm Gladwell

Book ReviewTalking to StrangersWhat We Should Know about the People We Don't KnowMalcolm Gladwell
Most Commonly Used 3,000 Kanjis in Japanese

2024/06/07

Most Commonly Used 3,000 Kanjis in Japanese

Most CommonKanji3000ListUsage FrequencyJapaneseJLPTLanguageStudyingWordsKanji ImportanceWord Prevalence
Replace With Regex Using VSCode

2024/06/07

Replace With Regex Using VSCode

VSCodeRegexFindReplaceConditional Replace
Do Not Use Readable Store in Svelte

2024/06/06

Do Not Use Readable Store in Svelte

SvelteReadableWritableState ManagementStoreSpeedMemoryFile Size
Increase Website Load Speed by Compressing Data with Gzip and Pako

2024/06/05

Increase Website Load Speed by Compressing Data with Gzip and Pako

GzipCompressionPakoWebsite Load SpeedSvelteKit
Find the Word the Mouse is Pointing to on a Webpage with JavaScript

2024/05/31

Find the Word the Mouse is Pointing to on a Webpage with JavaScript

JavascriptMousePointerHoverWeb Development
Create an Interactive Map with Svelte using SVG

2024/05/29

Create an Interactive Map with Svelte using SVG

SvelteSVGInteractive MapFront-end
Book Review | Originals: How Non-Conformists Move the World by Adam Grant & Sheryl Sandberg

2024/05/28

Book Review | Originals: How Non-Conformists Move the World by Adam Grant & Sheryl Sandberg

Book ReviewOriginalsAdam Grant & Sheryl SandbergHow Non-Conformists Move the World
How I Increased Traffic to my Website by 10x in a Month

2024/05/26

How I Increased Traffic to my Website by 10x in a Month

Increase Website TrafficClicksImpressionsGoogle Search Console
Life is Like Cycling

2024/05/24

Life is Like Cycling

CyclingLifePhilosophySuccess
Generate a Complete Sudoku Grid with Backtracking Algorithm in JavaScript

2024/05/19

Generate a Complete Sudoku Grid with Backtracking Algorithm in JavaScript

SudokuComplete GridBacktracking AlgorithmJavaScript
Why Tailwind is Amazing and How It Makes Web Dev a Breeze

2024/05/16

Why Tailwind is Amazing and How It Makes Web Dev a Breeze

TailwindAmazingFront-endWeb Development
Generate Sitemap Automatically with Git Hooks Using Python

2024/05/15

Generate Sitemap Automatically with Git Hooks Using Python

Git HooksPythonSitemapSvelteKit
Book Review | Range: Why Generalists Triumph in a Specialized World by David Epstein

2024/05/14

Book Review | Range: Why Generalists Triumph in a Specialized World by David Epstein

Book ReviewRangeDavid EpsteinWhy Generalists Triumph in a Specialized World
What is Svelte and SvelteKit?

2024/05/13

What is Svelte and SvelteKit?

SvelteSvelteKitFront-endVite
Internationalization with SvelteKit (Multiple Language Support)

2024/05/12

Internationalization with SvelteKit (Multiple Language Support)

InternationalizationI18NSvelteKitLanguage Support
Reduce Svelte Deploy Time With Caching

2024/05/11

Reduce Svelte Deploy Time With Caching

SvelteEnhanced ImageCachingDeploy Time
Lazy Load Content With Svelte and Intersection Oberver

2024/05/10

Lazy Load Content With Svelte and Intersection Oberver

Lazy LoadingWebsite Speed OptimizationSvelteIntersection Observer
Find the Optimal Stock Portfolio with a Genetic Algorithm

2024/05/10

Find the Optimal Stock Portfolio with a Genetic Algorithm

Stock marketPortfolio OptimizationGenetic AlgorithmPython
Convert ShapeFile To SVG With Python

2024/05/09

Convert ShapeFile To SVG With Python

ShapeFileSVGPythonGeoJSON
Reactivity In Svelte: Variables, Binding, and Key Function

2024/05/08

Reactivity In Svelte: Variables, Binding, and Key Function

SvelteReactivityBindingKey Function
Book Review | The Art Of War by Sun Tzu

2024/05/07

Book Review | The Art Of War by Sun Tzu

Book ReviewThe Art Of WarSun TzuThomas Cleary
Specialists Are Dead. Long Live Generalists!

2024/05/06

Specialists Are Dead. Long Live Generalists!

SpecialistGeneralistParadigm ShiftSoftware Engineering
Analyze Voter Behavior in Turkish Elections with Python

2024/05/03

Analyze Voter Behavior in Turkish Elections with Python

TurkeyAge Analysis2018 ElectionsVoter Behavior
Create Turkish Voter Profile Database With Web Scraping

2024/05/01

Create Turkish Voter Profile Database With Web Scraping

PythonSeleniumWeb ScrapingTurkish Elections
Make Infinite Scroll With Svelte and Tailwind

2024/04/30

Make Infinite Scroll With Svelte and Tailwind

SvelteTailwindInfinite ScrollFront-end
How I Reached Japanese Proficiency In Under A Year

2024/04/29

How I Reached Japanese Proficiency In Under A Year

JapaneseProficiencyJLPTBusiness
Use-ready Website Template With Svelte and Tailwind

2024/04/25

Use-ready Website Template With Svelte and Tailwind

Website TemplateFront-endSvelteTailwind
Lazy Engineers Make Lousy Products

2024/01/29

Lazy Engineers Make Lousy Products

Lazy engineerLousy productStarbucksSBI
On Greatness

2024/01/28

On Greatness

GreatnessMeaning of lifeSatisfactory lifePurpose
Converting PDF to PNG on a MacBook

2024/01/28

Converting PDF to PNG on a MacBook

PDFPNGMacBookAutomator
Recapping 2023: Compilation of 24 books read

2023/12/31

Recapping 2023: Compilation of 24 books read

BooksReading2023Reflections
Create a Photo Collage with Python PIL

2023/12/30

Create a Photo Collage with Python PIL

PythonPILImage ProcessingCollage
Detect Device & Browser of Visitors to Your Website

2024/01/09

Detect Device & Browser of Visitors to Your Website

JavascriptDevice DetectionBrowser DetectionWebsite Analytics
Anatomy of a ChatGPT Response

2024/01/19

Anatomy of a ChatGPT Response

ChatGPTLarge Language ModelMachine LearningGenerative AI