sudoku.js

const rotate = ar => ar[0].map((col, i) => ar.map(row => row[i]))

const check = board => {
	const board2 = rotate(board)
	const row_ok = board.every(row => new Set(row).size === row.length)
	const col_ok = board2.every(row => new Set(row).size === row.length)
	const block_ok = (() => {
		for (let i = 0; i < 3; i++) {
			for (let j = 0; j < 3; j++) {
				const s = new Set()
				for (let k = 3 * i; k < 3 * (i + 1); k++) {
					for (let l = 3 * j; l < 3 * (j + 1); l++) {
						s.add(board[k][l])
					}
				}
				if (s.size !== 9) {
					return false
				}
			}
		}
		return true
	})()
	return row_ok && col_ok && block_ok
}

const shouldFill = (board, a, b) => {
	const s = new Set([1, 2, 3, 4, 5, 6, 7, 8, 9])
	for (let i = 0; i < 9; i++) {
		s.delete(board[a][i])
		s.delete(board[i][b])
	}
	a = parseInt(a / 3)
	b = parseInt(b / 3)
	for (let k = 3 * a; k < 3 * (a + 1); k++) {
		for (let l = 3 * b; l < 3 * (b + 1); l++) {
			s.delete(board[k][l])
		}
	}
	return s
}

const solve = (board, solveall) => {
	const ans = []
	const _solve = board => {
		let full = true
		for (let i = 0; i < 9; i++) {
			for (let j = 0; j < 9; j++) {
				if (board[i][j] !== 0) continue
				full = false
				const ls = shouldFill(board, i, j)
				let cnt = 0
				for (let k of ls) {
					board[i][j] = k
					if (!_solve(board)) cnt++
				}
				if (solveall || cnt === ls.size) {
					board[i][j] = 0
					return false
				}
			}
		}
		if (full && check(board)) ans.push(copy2d(board))
		return true
	}
	_solve(copy2d(board))
	return ans
}

const rand = (min, max) => parseInt(Math.random() * (max - min + 1) + min)

const shuffle = a => {
	for (let i = a.length - 1; i > 0; i--) {
		const j = Math.floor(Math.random() * (i + 1))
		;[a[i], a[j]] = [a[j], a[i]]
	}
	return a
}

const copy2d = arr => arr.map(x => x.slice())

const genRandomBoardFromSeed = seed => {
	const arr = copy2d(seed)
	const rnd = shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9])
	for (let i = 0; i < 9; i++) {
		for (let j = 0; j < 9; j++) {
			for (let k = 0; k < 9; k++) {
				if (arr[i][j] == rnd[k]) {
					arr[i][j] = rnd[(k + 1) % 9]
					break
				}
			}
		}
	}
	return arr
}

const dig = (board, max = 15, oneans = false) => {
	const arr = copy2d(board)
	for (let i = 1; i <= max; i++) {
		const [a, b] = [rand(0, 8), rand(0, 8)]
		if (arr[a][b] === 0) {
			i--
			continue
		}
		const tmp = arr[a][b]
		arr[a][b] = 0
		if (oneans && solve(arr).length !== 1) {
			arr[a][b] = tmp
			i--
		}
	}
	return arr
}

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

const board = genRandomBoardFromSeed(seed)
const play = dig(board, 30) // a little bit slow
console.log(board)
console.log(play)
const results = solve(play, true)
console.log(results)
console.log(results.every(check))