Last active
July 5, 2023 06:57
-
-
Save philronan/6796b9e3023aac722755a2bee663bc0d to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!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> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment