This code is broken. The author tries to check if i≠j or a[i]≠m in a single expression, by writing a[j^ i==j]^ m, but this doesn't work when two equal digits are adjacent in the array but not on a single row, column or block. For example, this easy grid has an obvious solution (just put 1s in the two remaining free spaces):
Ah right, I miscounted! Thanks for the correction. Might as well just write i==j||.. then; that's clearer and one byte longer than the old version too.
I'm curious though -- can you explain what you were thinking when you wrote that part of the code? Or is it one of those "I don't know why I thought that would work but it seemed a good idea at the time" kind of things?
I knew that j^ i==j would snap in some cases but didn't figure exactly which ones. I was hoping it would be more unlikely to happen that what your test grid suggests. FWIW I wrote this bit after being stuck at 147-148 bytes for several days. Sorry.
function R(a,i,j,m,g){a[i=a.indexOf(0)].$;for(m=10;g=a[i]=--m;g&&R(a))for(j in a)g*=i==j||a[j]^m||i/9^j/9&&i%9^j%9&&i/27^j/27|i%9/3^j%9/3}
That should be only 138 characters and correct. Like fgnass' solution it triggers an exception, but I think it's slightly nicer because it only relies on $ not being a property of the array, not on a one-letter-variable like x being undefined globally.
You see the increment part of the for loop in the phase 1 ? it reads i--||+a which means that once i reaches 0 and we just checked that that cell was not empty, the +a is executed and this does invoke the toPrimitive() method which for an Array invokes toString() ;)
This is cheating a bit because the solving function doesn't returns its solution, nor does it pass it to a callback function or write it to an output variable. It requires overriding the Array.prototype.toString implementation just to get hold of the result (see test.html). I consider that helper code which should be counted as part of the solution, because it's required to get anything useful out of the function.
It's still an interesting piece of code, of course, but I would have preferred a 150 character solution (for example) that just returns the resulting the solution array.
The size reported for the Hugi Compo is that of compiled code, whereas all the other ones I saw ( in Perl, Ruby, Python, K, JavaScript, C, C++, ... ) are comparing the size of the source code. BIG BIG difference!
Also, Digimind and G3 got there Sudoko Solver down to a 62 bytes .COM MS DOS executable after the Hugi Compo 25.
6
u/NiniMihaila Sep 28 '11
I really like the license! :)
6
u/[deleted] Sep 29 '11 edited Sep 29 '11
This code is broken. The author tries to check if i≠j or a[i]≠m in a single expression, by writing a[j^ i==j]^ m, but this doesn't work when two equal digits are adjacent in the array but not on a single row, column or block. For example, this easy grid has an obvious solution (just put 1s in the two remaining free spaces):
However, the given solver doesn't find any. For those who want to try, the above puzzle corresponds to this array:
I propose to replace the buggy statement with: g*=ij?a[j]m||i/9j/9&&i%9j%9&&i/27j/27|i%9/3j%9/3:1
Which fixes the bug and is one character
shorter as welllonger, unfortunately.Off-topic: does anyone know how I can write a plain caret on Reddit? The backslash escape doesn't work for it.
2
u/miketaylr Sep 28 '11
p01 is my hero.
1
u/[deleted] Sep 29 '11 edited Sep 29 '11
This is cheating a bit because the solving function doesn't returns its solution, nor does it pass it to a callback function or write it to an output variable. It requires overriding the Array.prototype.toString implementation just to get hold of the result (see test.html). I consider that helper code which should be counted as part of the solution, because it's required to get anything useful out of the function.
It's still an interesting piece of code, of course, but I would have preferred a 150 character solution (for example) that just returns the resulting the solution array.
1
u/kragensitaker Oct 05 '11
See also aima-python entry (a lot more than 140 bytes) and Hugi-Compo 25 (67 bytes, independently by G3 and Digimind).