Sudoku solver

sudoku.js

// Based on: https://dfns.dyalog.com/n_sudoku.htm
// x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~*x

const solveSudoku = (board) => {
	const grid = Array.isArray(board[0])
		? board
		: Array.from({ length: 9 }, (_, i) => board.slice(i * 9, (i + 1) * 9));

	if (solve(grid)) {
		return grid;
	}
	return null; // No solution exists
};

const solve = (grid) => {
	let row = 0,
		col = 0,
		isEmpty = false;

	// Find an empty cell
	for (let i = 0; i < 9; i++) {
		for (let j = 0; j < 9; j++) {
			if (grid[i][j] === 0) {
				row = i;
				col = j;
				isEmpty = true;
				break;
			}
		}
		if (isEmpty) break;
	}

	// If no empty cell found, puzzle is solved
	if (!isEmpty) return true;

	// Try digits 1 to 9
	for (let num = 1; num <= 9; num++) {
		if (isSafe(grid, row, col, num)) {
			grid[row][col] = num;

			if (solve(grid)) return true;

			grid[row][col] = 0;
		}
	}
	return false;
};

const isSafe = (grid, row, col, num) => {
	// Check row
	for (let x = 0; x < 9; x++) {
		if (grid[row][x] === num) return false;
	}

	// Check column
	for (let x = 0; x < 9; x++) {
		if (grid[x][col] === num) return false;
	}

	// Check 3x3 box
	let startRow = row - (row % 3),
		startCol = col - (col % 3);
	for (let i = 0; i < 3; i++) {
		for (let j = 0; j < 3; j++) {
			if (grid[i + startRow][j + startCol] === num) return false;
		}
	}

	return true;
};

// const grid = [
// 	[3, 0, 1, 6, 7, 2, 0, 8, 4],
// 	[0, 0, 0, 8, 0, 1, 2, 0, 7],
// 	[0, 8, 7, 0, 0, 0, 6, 1, 0],
// 	[0, 9, 2, 0, 0, 5, 3, 7, 8],
// 	[8, 0, 0, 7, 0, 0, 0, 0, 0],
// 	[0, 0, 4, 9, 2, 0, 5, 0, 0],
// 	[1, 0, 0, 0, 0, 6, 0, 0, 5],
// 	[0, 0, 6, 0, 5, 0, 8, 0, 0],
// 	[5, 7, 3, 2, 0, 4, 0, 0, 0],
// ];
const grid = [
	[0, 0, 0, 4, 7, 6, 0, 0, 0],
	[0, 0, 0, 0, 0, 5, 8, 0, 0],
	[0, 0, 0, 0, 0, 1, 5, 0, 9],
	[0, 0, 0, 0, 0, 0, 0, 0, 4],
	[4, 6, 0, 0, 0, 0, 0, 5, 0],
	[0, 7, 0, 0, 1, 0, 0, 0, 6],
	[5, 0, 0, 0, 3, 0, 0, 0, 0],
	[0, 0, 9, 0, 0, 0, 2, 3, 0],
	[0, 0, 1, 7, 0, 0, 0, 0, 0],
];

const solution = solveSudoku(grid);
if (solution) {
	console.log("Solved puzzle");
	solution.forEach((row) => console.log(row.join(" ")));
} else {
	console.log("No solution");
}