Java Sudoku Solver in 6 lines
After playing around with writing Sudoku Solvers in the past, I was interested to see this page which details a number of tiny sudoku solvers in a variety of languages such as Perl, Ruby, etc.
They have a few basic rules - no line over 80 bytes, etc, etc. And the examples take their input as a string of 81 digits, which represents the 9 rows of 9 digits, with “0″ being a blank square.
As I apparently have way too much time on my hands ;), I got up the motivation to convert one of these examples into Java. The results?
- The end program is around twice as many lines as the Perl original, and
- Yup - you can make Java programs as unreadable as anything else out there!
There may well be shorter possibilities out there - I didn’t put in a great deal of effort past converting the Perl original. But, for the record:
import java.util.*;public class S{static char[] A;static void R(){int i,j;for(i=
0;i<81;i++){if(A[i]!='0')continue;HashMap h=new HashMap();for(j=0;j<81;j++){h.
put(j/9==i/9||j%9==i%9||(j/27==i/27)&&((j%9/3)==(i%9/3))?""+A[j]:"0","1");}for(j
=1;j<=9;j++){if(h.get(""+j)==null){A[i]=(char)('0'+j);R();}}A[i]='0';return;}for
(i=0;i<81;i++){System.out.print(A[i]);}System.out.println();System.exit(0);}
public static void main(String[] a){A=a[0].toCharArray();R();}}
Assuming you have an appropriate classpath, you can run it with a line like:
java S 006070800000000000078601520030405010400000002090302060052103690000000000003020100
This code was converted from the excellent Perl example at:
http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html
July 24th, 2006 at 10:11 pm
And to think I managed to write solver in only 100 or so line of Perl. And it wasn’t even complete!
Bah.
July 25th, 2006 at 9:43 am
… you can save four more bytes by using ‘Map h=new HashMap()’
July 26th, 2006 at 8:04 pm
You can get smaller and faster by replacing the hash with a boolean array (’x’ is for eXcluded chars). You need to (ab)use the fact that booleans are false by default.
public class S{static char[] A;static void R(){int i,j;for(i=0;i
July 27th, 2006 at 1:42 am
import java.util.*;public class S{static char[]A;static void R(){int i=0,j;for(;i
August 1st, 2006 at 8:31 pm
Wow, still not sure how it does it. Need to get my head around it’s recursiveness (R() is called 1107(!) times for that example problem).
August 7th, 2006 at 2:47 am
Using Kofa’s idea of a boolean array I got it down to under 5 lines.
public class S{static char[] A;static void R(){int i=0,j;for(;i
October 29th, 2006 at 6:55 am
3 line groovy version:
def r(a){def m=a=~’0′; if(m.find()){def i=m.start();((49..57)-(0..80).collect{
j->j/9==i/9||j%9==i%9||j/27==i/27&&j%9/3==i%9/3?a[j]:0}).collect{
r(a[0..i-1]+(char)it+a[i+1..-1])}}else print a}