philronan/sudoku-cheat.html

## sudoku-cheat.html
<!DOCTYPE html>
<html lang="en">

<head>
    <title>Sudoku cheat</title>
    <link rel="preconnect" href="https://fonts.googleapis.com">
    <link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
    <link href="https://fonts.googleapis.com/css2?family=DM+Mono&display=swap" rel="stylesheet">
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <style>
        body {
            background-color: #222;
            color: #4c4;
            font-family: sans-serif;
        }

        .content {
            text-align: center;
        }

        .grid {
            background-color: #000;
            color: #4c4;
            font-family: 'DM Mono', monospace;;
            font-size: 20px;
            width: 16em;
            height: 16em;
            letter-spacing: 1.15em;
            line-height: 1.75em;
            padding-left: 1em;
            resize: none;
            overflow: hidden;
            margin: 0.5em;
            display: inline-block;
        }

        .grid:focus {
            outline: none;
        }

        .output {
            background-color: #444;
            color: #aaa;
        }
    </style>
</head>

<body>
    <div class="content">
        <h1>Sudoku cheat</h1>
        <p>Enter the digits on the left (use "." for unknowns).</p>
        <textarea class="grid"
            onkeyup="s = this.value; s = s.replaceAll(/[^1-9\.]/g, '').substring(0,81); this.value = s; document.getElementById('out').value = (s.length == 81) ? sudoku(s) : ''"></textarea>
        <textarea class="grid output" disabled id="out"></textarea>
        <script>
            function sudoku(s) {
                if (s.length != 81) return "invalid input"
                let arr = []
                for (let i = 0; i < 81; i++) {
                    let ch = s.charAt(i)
                    if (ch < '1' || ch > '9') arr.push(0b111111111)
                    else arr.push(1 << (parseInt(ch) - 1))
                }
                arr = solve(arr)
                if (typeof (arr) == 'object') {
                    //print_sudoku(arr)
                    return sudoku2str(arr)
                }
                else {
                    //console.log(arr)
                    return arr
                }
            }

            function sudoku2str(arr) {
                let output = ''
                for (let i = 0; i < 81; i++) {
                    let n = arr[i]
                    if (n > 0 && (n & (n - 1)) == 0) {
                        let v = Math.log(n) / Math.log(2) + 1
                        output += v.toString()
                    }
                    else {
                        output += '.'
                    }
                }
                return output
            }

            function print_sudoku(arr) {
                for (let row = 0; row < 9; row++) {
                    r = (row + 1).toString() + ': '
                    for (let col = 0; col < 9; col++) {
                        let t = row * 9 + col
                        let n = arr[t]
                        if (n > 0 && (n & (n - 1)) == 0) {
                            let v = Math.log(n) / Math.log(2) + 1
                            r += '  ' + v.toString()
                        }
                        else {
                            r += '  .'
                        }
                    }
                    console.log(r)
                }
            }

            function nbits(n) {
                let nb = 0
                while (n) {
                    n &= n - 1
                    nb++
                }
                return nb
            }

            function solve(arr) {
                let saveArr = arr.toString()
                while (true) {
                    arr = propagate(arr)
                    arr = constrain(arr)
                    let sv = arr.toString()
                    if (sv == saveArr) break
                    saveArr = sv
                }
                if (arr.includes(0)) return '.........this.....has......no.......solutions.........try......again.............'
                let solved = true
                let leastbits = 9
                let leastbitsloc = 0
                for (let i = 0; i < 81; i++) {
                    let n = nbits(arr[i])
                    if (n != 1) {
                        solved = false
                        if (n < leastbits) {
                            leastbits = n
                            leastbitsloc = i
                        }
                    }
                }
                if (solved) return arr
                let v = arr[leastbitsloc]
                for (let i = 0; i < 9; i++) {
                    if ((1 << i) & v) {
                        let newarr = [...arr]
                        newarr[leastbitsloc] = 1 << i
                        result = solve(newarr)
                        if (typeof (result) == 'object') return result
                    }
                }
                return '.........this.....has......no.......solutions.........try......again.............'
            }

            function propagate(arr) {
                for (let i = 0; i < 81; i++) {
                    let n = arr[i]
                    if (n > 0 && (n & (n - 1)) == 0) {
                        let rowStart = Math.floor(i / 9) * 9
                        let colStart = i % 9
                        let boxStart = Math.floor(i / 27) * 27 + Math.floor((i % 9) / 3) * 3
                        let t
                        for (t = rowStart; t < rowStart + 9; t++) {
                            if (t == i) continue
                            arr[t] &= ~n
                        }
                        for (t = colStart; t < 81; t += 9) {
                            if (t == i) continue
                            arr[t] &= ~n
                        }
                        for (let dy = 0; dy < 27; dy += 9) {
                            for (let dx = 0; dx < 3; dx++) {
                                t = boxStart + dy + dx
                                if (t == i) continue
                                arr[t] &= ~n
                            }
                        }
                    }
                }
                return arr
            }

            function constrain(arr) {
                for (let i = 0; i < 81; i++) {
                    let rowStart = Math.floor(i / 9) * 9
                    let colStart = i % 9
                    let boxStart = Math.floor(i / 27) * 27 + Math.floor((i % 9) / 3) * 3
                    let t, j, k, buckets
                    buckets = [0, 0, 0, 0, 0, 0, 0, 0, 0]
                    for (t = rowStart; t < rowStart + 9; t++) {
                        for (j = 0; j < 9; j++) if ((1 << j) & arr[t]) buckets[j]++
                    }
                    for (j = 0; j < 9; j++) {
                        if (buckets[j] == 1) {
                            for (t = rowStart; t < rowStart + 9; t++) {
                                if (arr[t] & (1 << j)) arr[t] = 1 << j
                            }
                        }
                    }
                    buckets = [0, 0, 0, 0, 0, 0, 0, 0, 0]
                    for (t = colStart; t < 81; t += 9) {
                        for (j = 0; j < 9; j++) if ((1 << j) & arr[t]) buckets[j]++
                    }
                    for (j = 0; j < 9; j++) {
                        if (buckets[j] == 1) {
                            for (t = colStart; t < 81; t += 9) {
                                if (arr[t] & (1 << j)) arr[t] = 1 << j
                            }
                        }
                    }
                    buckets = [0, 0, 0, 0, 0, 0, 0, 0, 0]
                    for (let dy = 0; dy < 27; dy += 9) {
                        for (let dx = 0; dx < 3; dx++) {
                            t = boxStart + dy + dx
                            for (j = 0; j < 9; j++) if ((1 << j) & arr[t]) buckets[j]++
                        }
                    }
                    for (j = 0; j < 9; j++) {
                        if (buckets[j] == 1) {
                            for (let dy = 0; dy < 27; dy += 9) {
                                for (let dx = 0; dx < 3; dx++) {
                                    t = boxStart + dy + dx
                                    if (arr[t] & (1 << j)) arr[t] = 1 << j
                                }
                            }
                        }
                    }
                }
                return arr
            }

    //sudoku('8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..')
        </script>
    </div>
</body>

</html>
	<!DOCTYPE html>
	<html lang="en">

	<head>
	<title>Sudoku cheat</title>
	<link rel="preconnect" href="https://fonts.googleapis.com">
	<link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
	<link href="https://fonts.googleapis.com/css2?family=DM+Mono&display=swap" rel="stylesheet">
	<meta charset="utf-8">
	<meta name="viewport" content="width=device-width, initial-scale=1">
	<style>
	body {
	background-color: #222;
	color: #4c4;
	font-family: sans-serif;
	}

	.content {
	text-align: center;
	}

	.grid {
	background-color: #000;
	color: #4c4;
	font-family: 'DM Mono', monospace;;
	font-size: 20px;
	width: 16em;
	height: 16em;
	letter-spacing: 1.15em;
	line-height: 1.75em;
	padding-left: 1em;
	resize: none;
	overflow: hidden;
	margin: 0.5em;
	display: inline-block;
	}

	.grid:focus {
	outline: none;
	}

	.output {
	background-color: #444;
	color: #aaa;
	}
	</style>
	</head>

	<body>
	<div class="content">
	<h1>Sudoku cheat</h1>
	<p>Enter the digits on the left (use "." for unknowns).</p>
	<textarea class="grid"
	onkeyup="s = this.value; s = s.replaceAll(/[^1-9\.]/g, '').substring(0,81); this.value = s; document.getElementById('out').value = (s.length == 81) ? sudoku(s) : ''"></textarea>
	<textarea class="grid output" disabled id="out"></textarea>
	<script>
	function sudoku(s) {
	if (s.length != 81) return "invalid input"
	let arr = []
	for (let i = 0; i < 81; i++) {
	let ch = s.charAt(i)
	if (ch < '1' \|\| ch > '9') arr.push(0b111111111)
	else arr.push(1 << (parseInt(ch) - 1))
	}
	arr = solve(arr)
	if (typeof (arr) == 'object') {
	//print_sudoku(arr)
	return sudoku2str(arr)
	}
	else {
	//console.log(arr)
	return arr
	}
	}

	function sudoku2str(arr) {
	let output = ''
	for (let i = 0; i < 81; i++) {
	let n = arr[i]
	if (n > 0 && (n & (n - 1)) == 0) {
	let v = Math.log(n) / Math.log(2) + 1
	output += v.toString()
	}
	else {
	output += '.'
	}
	}
	return output
	}

	function print_sudoku(arr) {
	for (let row = 0; row < 9; row++) {
	r = (row + 1).toString() + ': '
	for (let col = 0; col < 9; col++) {
	let t = row * 9 + col
	let n = arr[t]
	if (n > 0 && (n & (n - 1)) == 0) {
	let v = Math.log(n) / Math.log(2) + 1
	r += ' ' + v.toString()
	}
	else {
	r += ' .'
	}
	}
	console.log(r)
	}
	}

	function nbits(n) {
	let nb = 0
	while (n) {
	n &= n - 1
	nb++
	}
	return nb
	}

	function solve(arr) {
	let saveArr = arr.toString()
	while (true) {
	arr = propagate(arr)
	arr = constrain(arr)
	let sv = arr.toString()
	if (sv == saveArr) break
	saveArr = sv
	}
	if (arr.includes(0)) return '.........this.....has......no.......solutions.........try......again.............'
	let solved = true
	let leastbits = 9
	let leastbitsloc = 0
	for (let i = 0; i < 81; i++) {
	let n = nbits(arr[i])
	if (n != 1) {
	solved = false
	if (n < leastbits) {
	leastbits = n
	leastbitsloc = i
	}
	}
	}
	if (solved) return arr
	let v = arr[leastbitsloc]
	for (let i = 0; i < 9; i++) {
	if ((1 << i) & v) {
	let newarr = [...arr]
	newarr[leastbitsloc] = 1 << i
	result = solve(newarr)
	if (typeof (result) == 'object') return result
	}
	}
	return '.........this.....has......no.......solutions.........try......again.............'
	}

	function propagate(arr) {
	for (let i = 0; i < 81; i++) {
	let n = arr[i]
	if (n > 0 && (n & (n - 1)) == 0) {
	let rowStart = Math.floor(i / 9) * 9
	let colStart = i % 9
	let boxStart = Math.floor(i / 27) * 27 + Math.floor((i % 9) / 3) * 3
	let t
	for (t = rowStart; t < rowStart + 9; t++) {
	if (t == i) continue
	arr[t] &= ~n
	}
	for (t = colStart; t < 81; t += 9) {
	if (t == i) continue
	arr[t] &= ~n
	}
	for (let dy = 0; dy < 27; dy += 9) {
	for (let dx = 0; dx < 3; dx++) {
	t = boxStart + dy + dx
	if (t == i) continue
	arr[t] &= ~n
	}
	}
	}
	}
	return arr
	}

	function constrain(arr) {
	for (let i = 0; i < 81; i++) {
	let rowStart = Math.floor(i / 9) * 9
	let colStart = i % 9
	let boxStart = Math.floor(i / 27) * 27 + Math.floor((i % 9) / 3) * 3
	let t, j, k, buckets
	buckets = [0, 0, 0, 0, 0, 0, 0, 0, 0]
	for (t = rowStart; t < rowStart + 9; t++) {
	for (j = 0; j < 9; j++) if ((1 << j) & arr[t]) buckets[j]++
	}
	for (j = 0; j < 9; j++) {
	if (buckets[j] == 1) {
	for (t = rowStart; t < rowStart + 9; t++) {
	if (arr[t] & (1 << j)) arr[t] = 1 << j
	}
	}
	}
	buckets = [0, 0, 0, 0, 0, 0, 0, 0, 0]
	for (t = colStart; t < 81; t += 9) {
	for (j = 0; j < 9; j++) if ((1 << j) & arr[t]) buckets[j]++
	}
	for (j = 0; j < 9; j++) {
	if (buckets[j] == 1) {
	for (t = colStart; t < 81; t += 9) {
	if (arr[t] & (1 << j)) arr[t] = 1 << j
	}
	}
	}
	buckets = [0, 0, 0, 0, 0, 0, 0, 0, 0]
	for (let dy = 0; dy < 27; dy += 9) {
	for (let dx = 0; dx < 3; dx++) {
	t = boxStart + dy + dx
	for (j = 0; j < 9; j++) if ((1 << j) & arr[t]) buckets[j]++
	}
	}
	for (j = 0; j < 9; j++) {
	if (buckets[j] == 1) {
	for (let dy = 0; dy < 27; dy += 9) {
	for (let dx = 0; dx < 3; dx++) {
	t = boxStart + dy + dx
	if (arr[t] & (1 << j)) arr[t] = 1 << j
	}
	}
	}
	}
	}
	return arr
	}

	//sudoku('8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..')
	</script>
	</div>
	</body>

	</html>