Skip to content

Instantly share code, notes, and snippets.

@fgnass

fgnass/LICENSE.txt

Forked from p01/LICENSE.txt
Created September 28, 2011 10:53
Show Gist options
  • Save fgnass/1247640 to your computer and use it in GitHub Desktop.
Save fgnass/1247640 to your computer and use it in GitHub Desktop.
Download ZIP
Sudoku Solver in 140bytes
Raw
README.md

Sudoku Solver in 140 bytes

Solve a Sudoku grid only using magic, recursion, and 140bytes of brute force.

Raw
annotated.js
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
}
Raw
index.js
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}
Raw
LICENSE.txt
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.
Raw
package.json
{
"name": "sudokuSolver",
"description": "Brute force sudoku solver.",
"keywords": [
"sudoku",
"solver",
"recursive",
"brute force"
]
}
Raw
test.html
<!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>
@atk
Copy link

atk commented Oct 7, 2011

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.

@an74819
Copy link

an74819 commented Oct 7, 2011

Oh ok, I get it now. Thanks for the quick response!

@newproject
Copy link

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

@atk
Copy link

atk commented Mar 29, 2012 

      // 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.

@newproject
Copy link

Thankyou for the quick response!!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment