Instantly share code, notes, and snippets.

Created September 28, 2011 10:53
Sudoku Solver in 140bytes

# Sudoku Solver in 140 bytes

Solve a Sudoku grid only using magic, recursion, and 140bytes of 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
 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 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
 Sudoku Solver in 140bytes
Expected value: 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
Actual value:

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

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

### 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

### 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 commented Oct 7, 2011

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

### newproject commented Mar 28, 2012

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 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 commented Apr 5, 2012

Thankyou for the quick response!!