Sudoku Solver

.editorconfig

[*]
indent_style = tab
indent_size = 4

sudoku.ts

#!/usr/bin/env deno

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

/**
 * Determine if a given number is possible at a location
 */
function possible(y: number, x: number, n: number, grid: number[][]): boolean {
	for (let i = 0; i < 9; i++) {
		if (grid[y][i] === n) {
			return false
		}
	}
	for (let i = 0; i < 9; i++) {
		if (grid[i][x] === n) {
			return false
		}
	}
	const x0 = Math.floor(x / 3) * 3
	const y0 = Math.floor(y / 3) * 3
	for (let i = 0; i < 3; i++) {
		for (let j = 0; i < 3; i++) {
			if (grid[y0 + i][x0 + j] === n) {
				return false
			}
		}
	}
	return true
}

possible(4, 4, 5, grid) //?

let count = 0

/**
 * Solve a sudoko grid. Returns the first solution to a given sudoku puzzle.
 * @param grid The sudoku grid
 */
function solve(grid: number[][]) {
	/**
	 * A recursive function to solve for the global grid
	 */
	function solveImpl(): boolean {
		count += 1
		for (let y = 0; y < 9; y++) {
			for (let x = 0; x < 9; x++) {
				if (grid[y][x] === 0) {
					for (let n = 1; n < 10; n++) {
						if (possible(y, x, n, grid)) {
							grid[y][x] = n
							if (solveImpl()) {
								return true
							}
							grid[y][x] = 0 // We made a bad choice
						}
					}
					return false
				}
			}
		}
		return true
	}
	solveImpl()
	return grid
}

function test() {
	count = 0
	solve(grid)

	console.log(`Solved in ${count} tries`)
	console.log(grid)
}
test()

export {}