Generate a Complete Sudoku Grid with Backtracking Algorithm in JavaScript

In this blogpost, we will see how to generate a complete sudoku grid like below using a backtracking algorithm in JavaScript. Click on Restart Grid to see the algorithm in action!

Background

It may sound easy to create a sudoku grid complete with numbers. It may also sound foolish to do this, because eventually what matters is solving an incomplete sudoku grid, not creating a complete one from scratch. Even if we were interested in creating one, we would like to create one with missing numbers, which can be used to play an actual game of sudoku.

However, these arguments would be wrong because:

1. It is not easy to create a complete sudoku grid.

As an exercise, try creating a 9x9 sudoku grid that satisfies the rules of the game (i.e., all numbers between 1-9 should be used across each row, column and block with no repetition) You will soon realize that it is not as easy as it looks, because while it is easy to satisfy these conditions for the first ~20 numbers, it becomes harder as you get closer to the end of the grid.

This is because the numbers you fill in earlier may/will cause problems in later cells by eliminiating all potential numbers for a cell. You then need to backtrack couple cells, change number in that earlier cell so that the later cell can be filled with a number.

2. It is not irrelevant to create a complete sudoku grid.

Complete grid creation is actually first step of creating a sudoku game board. We start with a complete grid, and remove numbers from that grid, so that the player can fill in those numbers. More numbers we delete, the harder the game becomes.

So, we can see that completed grid creation is an essential part of crafting this game. Before we dive into the game, let's look at the rules of grid creation:

Basics of Sudoku

The basic rule of of 9x9 sudoku is that, each row, column, and block in the grid should have numbers between 1-9. There are 9 cells in a row, column, or a block, so it fits numbers between 1-9 perfectly, hence no repetition is allowed.

1. Rows

Below you can see each row highlighted with row name in each cell.

2. Columns

Below you can see each column highlighted with column name in each cell.

3. Blocks

Blocks are 3x3 squares that make up the grid. Similar to rows and columns, each block should have numbers between 1-9 and no repetition is allowed.

Below you can see each block highlighted with block name in each cell.

Method

As I touched upon briefly in the above section, creating a complete grid is devilishly difficult to do by hand, because to be able to do this, you'd need to foresee all possible issues that might arise from using a certain number for a cell.

You eventually run into a cell where no number can be used, because the row, column, and block conditions rule out all possible numbers. When this happens, we backtrack.

Backtracking Algorithm

Below shows how this algorithm runs in principle:

1. Check if there is a number between 1-9 that satisfy row, column, block constraints and that are not already tried for the cell you are on.
2. If there is such number, set the value of your cell to that number. Add that number to the list of tried numbers for this cell. Move forward 1 cell, go to step 1.
3. Else, clean the list of tried numbers for this cell. Move back 1 cell. Clean the value of that cell (previous cell) and go to step 1.

Below is the code version:

// Initialize variables
let grid = []; // To keep grid data
let numbers = []; // Numbers from 1-9
let cellIndex = 0; // Cell number

// initialize grid and numbers
for (let i = 0; i < 9; i++) {
	// Add to numbers
	numbers.push(i + 1);

	// For each cell, record its row, column, block, initial value, and tried values
	// Initial value and tried values are initialized as '' and [] respectively
	for (let j = 0; j < 9; j++) {
		let cell = {};
		cell.row = i;
		cell.col = j;
		cell.block = `${Math.floor(i / 3)}-${Math.floor(j / 3)}`;
		cell.value = '';
		cell.tried = [];
		grid.push(cell);
	}
}

// Function that fills the grid with backtracking algorithm
function fillGrid() {
	// Continue only if there are still cells remaining to be filled
	while (cellIndex < grid.length) {
		// Get the relevant cell
		let cell = grid[cellIndex];

		// If we tried all numbers for a cell, set the tried to []
		// Otherwise the algorithm gets blocked
		if (cell.tried.length == 9) {
			cell.tried = [];
		}

		// For this cell, get cells that belong to the same row, column and block
		let row = grid.filter((d) => d.row === cell.row).map((d) => d.value);
		let col = grid.filter((d) => d.col === cell.col).map((d) => d.value);
		let block = grid.filter((d) => d.block === cell.block).map((d) => d.value);

		// Shuffle numbers because we want to have a different grid at each time
		// Otherwise your grid will always produce the same output
		numbers = numbers
			.map((value) => ({ value, sort: Math.random() }))
			.sort((a, b) => a.sort - b.sort)
			.map(({ value }) => value);

		// Variable that keeps whether a feasible number found for a cell
		let found = false;

		// Loop through random numbers
		for (let n = 0; n < 9; n++) {
			// Get a random number
			let number = numbers[n];

			// Check if this number satisfies the conditions
			// Ie 1. it is not tried yet
			// 2. it doesnt appear in the same row as the cell
			// 3. it doesnt appear in the same column as the cell
			// 4. it doesnt appear in the same block as the cell
			if (
				!cell.tried.includes(number) &&
				!row.includes(number) &&
				!col.includes(number) &&
				!block.includes(number)
			) {
				// If the number satisfies set cell value to that number
				cell.value = number;

				// Add the number to tried numbers for this cell
				cell.tried.push(number);

				// Move to next cell
				cellIndex++;

				// Set found to true, because a number solution is found
				found = true;
				break;
			}
		}

		// If no number is found for the cell
		// Ie there is no number that satisfies above 4 conditions
		if (!found) {
			// Set tried numbers array to [] for this cell
			grid[cellIndex].tried = [];

			// Move back 1 cell
			cellIndex--;

			// Set previous cell's value to "" in order to try other numbers
			grid[cellIndex].value = '';
		}
	}
}

fillGrid();

Result

Now let's see whether above code works with below grid using the Fill Grid button:

It does, doesn't it? And backtracking algorithm is very efficient as it finds an answer to this problem within 1 second most of the time.

Conclusion

In this blogpost, we have seen that the task of complete sudoku grid is not trivial, because it can't be done by hand and it is an essential part of sudoku game-making.

For this task, we have developed a simple yet efficient algorithm called backtracking algorithm to create a complete sudoku grid. I could usually generate a complete sudoku grid of 81 cells within 200 steps, in less than a second.

I will follow-up this blogpost with 2 more posts:

1. Algorithmically create sudoku games with varying difficulty by removing numbers from the complete grid
2. Solve sudoku game algorithmically

In the meantime, happy hacking!