Skip to content

Instantly share code, notes, and snippets.

Forked from p01/LICENSE.txt
Created September 28, 2011 10:53
What would you like to do?
Sudoku Solver in 140bytes

Sudoku Solver in 140 bytes

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

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
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'
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'
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}
Version 2, December 2004
Copyright (C) 2011 Mathieu 'p01' Henri <>
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.
"name": "sudokuSolver",
"description": "Brute force sudoku solver.",
"keywords": [
"brute force"
<!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>
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;
Copy link

atk commented Sep 28, 2011

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.

Copy link

p01 commented Sep 28, 2011

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.

Copy link

an74819 commented Oct 7, 2011

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

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.

Copy link

an74819 commented Oct 7, 2011

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

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.


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.

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