Solve a Sudoku grid only using magic, recursion, and 140bytes of brute force.
-
-
Save fgnass/1247640 to your computer and use it in GitHub Desktop.
Sudoku Solver in 140bytes
This file contains 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
| function R | |
| ( | |
| a, // the array representing the sudoko grid | |
| // placeholder arguments | |
| i, // index of the last empty cell | |
| j, // index to check the candidates for the cell 'i' | |
| m, // candidate number for the the cell 'i' | |
| g // flag whether 'm' is a already used in the same row|col|node as 'i' | |
| ){ | |
| // phase 1: look for an empty cell | |
| for | |
| ( | |
| i=80; | |
| a[i]; // keep going if the cell isn't empty | |
| i--||x // decrease the index and cause a ReferenceError if we went through the whole grid | |
| ); | |
| // phase 2: check all candidate numbers for the cell 'i' | |
| for | |
| ( | |
| m=10; | |
| g=a[i]=--m; // put the candidate in the cell 'i' already and set 'g' to something truthy | |
| // at the end of phase 2, the cell 'i' is reset to 0 for "higher" branches of the recursion | |
| g&&R(a) // recurse if 'm' isn't already used in the same row|col|node as 'i' | |
| ) | |
| // phase 3: check if the candidate number is used already | |
| for(j in a) // loop through the whole grid again | |
| g*= // turn 'g' falsy if | |
| a[j^i==j] // we are not on the cell 'i' | |
| ^m // and the cell 'j' is set to 'm' | |
| || // and we are in the same row|col|node as 'i' | |
| i/9^j/9&&i%9^j%9&&i/27^j/27|i%9/3^j%9/3 | |
| } |
This file contains 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
| function R(a,i,j,m,g){for(i=80;a[i];i--||x);for(m=10;g=a[i]=--m;g&&R(a))for(j in a)g*=a[j^i==j]^m||i/9^j/9&&i%9^j%9&&i/27^j/27|i%9/3^j%9/3} |
This file contains 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
| DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE | |
| Version 2, December 2004 | |
| Copyright (C) 2011 Mathieu 'p01' Henri <http://www.p01.org/releases/> | |
| Everyone is permitted to copy and distribute verbatim or modified | |
| copies of this license document, and changing it is allowed as long | |
| as the name is changed. | |
| DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE | |
| TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION | |
| 0. You just DO WHAT THE FUCK YOU WANT TO. |
This file contains 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
| { | |
| "name": "sudokuSolver", | |
| "description": "Brute force sudoku solver.", | |
| "keywords": [ | |
| "sudoku", | |
| "solver", | |
| "recursive", | |
| "brute force" | |
| ] | |
| } |
This file contains 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> | |
| <title>Sudoku Solver in 140bytes</title> | |
| <div>Expected value: <b>4,2,8,1,5,9,6,7,3,1,9,6,3,7,4,8,2,5,3,7,5,8,6,2,9,4,1,9,8,1,4,2,3,5,6,7,5,6,4,7,1,8,3,9,2,7,3,2,5,9,6,1,8,4,2,4,3,6,8,1,7,5,9,6,1,7,9,4,5,2,3,8,8,5,9,2,3,7,4,1,6</b></div> | |
| <div>Actual value: <b id="ret"></b></div> | |
| <script> | |
| var testGrid = [0,0,0,1,5,0,0,7,0,1,0,6,0,0,0,8,2,0,3,0,0,8,6,0,0,4,0,9,0,0,4,0,0,5,6,7,0,0,4,7,0,8,3,0,0,7,3,2,0,0,6,0,0,4,0,4,0,0,8,1,0,0,9,0,1,7,0,0,0,2,0,8,0,5,0,0,3,7,0,0,0]; | |
| var myFunction = function R(a,i,j,m,g){for(i=80;a[i];i--||x);for(m=10;g=a[i]=--m;g&&R(a))for(j in a)g*=a[j^i==j]^m||i/9^j/9&&i%9^j%9&&i/27^j/27|i%9/3^j%9/3}; | |
| try { | |
| myFunction( testGrid ); | |
| } | |
| catch (e) { | |
| document.getElementById( "ret" ).textContent=testGrid; | |
| } | |
| </script> |
Silly me, in an earlier implementation I had a throw a, and just didn't think of throwing a "real" error. Well done sir!
I know this is 140bytes, aka the Sparta of JavaScript, but I wonder if people are OK with having to try catch the call.
Hello, I'm in school studying java and this is very interesting but I don't get a few things. Granted I don't know much about javascript and you guys are obviously experienced, but how do those first two for loops work?
In the condition spot you have statements and in the increment spot you have what looks like logical operators? Do mind briefly explaining how that works?
Thanks, Ryan
Hi, Ryan. The first loop just pushes the counter "i" to the most right occurrence of zero, until it is pushed down to -1 (returning 0, which coerces to false, thus using the undefined "x", which leads to the error that we are about to catch). The second loop tries every number between 1 and 9 recursively. Actually we don't use the for statement as originally intended, but just figured we can use it like this:
for(initialisation;true/false-y statement;will be executed after the body)loop body
All statements can use "," to do multiple things; logical and/or or even the if-then-else-shorthand x ? y : z will work, but not additional command bodies. Please read the Wikipage for byte-saving tips.
Oh ok, I get it now. Thanks for the quick response!
Hello, I am new to JavaScript and am willing to learn new things.This code looks interesting but phase 3 code is not very clear to me.Would be great if you explain the same in detail.
Thanks,
Sana
// j will once take the value of every single position in a, while g will be a true-ish value
for(j in a) // loop through the whole grid again
g*= // turn 'g' falsy by multiplication with zero if
a[j^i==j] // we are not on the cell 'i' --> j xor [1|0], 1 only if i == j, therefore skewing the position to the left/right, depending on if j is odd/even
^m // and the cell 'j' is set to 'm' --> a[j]^m=0 only if a[j] == m
// until here, g would be 0 if j != i and a[j] == m, but we still want to check if the same number is not in the same row/col/node
|| // and we are in the same row|col|node as 'i'
i/9^j/9 && // xor floors the divided number, but the division has operator precedence, so this will be zero only if i and j are in the same row
i%9^j%9 && // same here, only that we take the modulo (rest of division), for example 14 % 9 == 23 % 9 == 5, so this will be zero for the same column
i/27^j/27 | i%9/3^j%9/3 // this one is a bit more difficult to explain; in essence, it will use each a third of the row and a third of the column detection
// now g should be one if there are empty/double values and the recursion moves on.
If you have further questions, feel free to ask.
Thankyou for the quick response!!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
It's 139bytes - not a bad idea at all, though I'd like the comment that one needs to ensure that x is not defined in any scope around the function.