26
\$\begingroup\$

Implement the shortest Sudoku solver.

Sudoku Puzzle:

 | 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A|   3   |     1 |
B|     6 |       |   5
C| 5     |       | 9 8 3
-+-----------------------
D|   8   |     6 | 3   2
E|       |   5   |
F| 9   3 | 8     |   6
-+-----------------------
G| 7 1 4 |       |     9
H|   2   |       | 8
I|       | 4     |   3

Answer:

 | 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 8 3 2 | 5 9 1 | 6 7 4
B| 4 9 6 | 3 8 7 | 2 5 1
C| 5 7 1 | 2 6 4 | 9 8 3
-+-----------------------
D| 1 8 5 | 7 4 6 | 3 9 2
E| 2 6 7 | 9 5 3 | 4 1 8
F| 9 4 3 | 8 1 2 | 7 6 5
-+-----------------------
G| 7 1 4 | 6 3 8 | 5 2 9
H| 3 2 9 | 1 7 5 | 8 4 6
I| 6 5 8 | 4 2 9 | 1 3 7

Rules:

  1. Assume all mazes are solvable by logic only.
  2. All input will be 81 characters long. Missing characters will be 0.
  3. Output the solution as a single string.
  4. The "grid" may be stored internally however you wish.
  5. The solution must use a non-guessing solution. (see Sudoku Solver)

Example I/O:

>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137
\$\endgroup\$
  • \$\begingroup\$ You should really add a time limit. \$\endgroup\$ – JPvdMerwe Feb 2 '11 at 0:30
  • 1
    \$\begingroup\$ @JPvdMerwe: Good point, but a time limit would be hard to standardize. \$\endgroup\$ – snmcdonald Feb 2 '11 at 1:19
  • 1
    \$\begingroup\$ @gnibbler: It might have been done before (but not on codegolf.se). I think it will still be fun to solve as well as add some value to the community, especially if one goes about it honestly. \$\endgroup\$ – snmcdonald Feb 2 '11 at 1:47
  • 2
    \$\begingroup\$ I like this one. I've been hesitant to try an actual golf solution, and I've been thinking about writing a Sudoku solver (it seems like a fun exercise). I think it's something people like me, who've never golfed before, could use as a jumping-off point. And once I come up with one, I might then golf it. \$\endgroup\$ – Andy Feb 2 '11 at 4:47
  • 8
    \$\begingroup\$ Problems "solvable by logic only" is very vague. Do you mean, perhaps, using only the basic steps of a) Writing a value in a cell for which it's value not in its row, column, and block b) Identifying a number that can only go in one place in its row, column, or block, and writing it there? \$\endgroup\$ – xnor May 17 '14 at 2:41
5
\$\begingroup\$

RUBY (449 436 chars)

I=*(0..8)
b=$*[0].split('').map{|v|v<'1'?I.map{|d|d+1}:[v.to_i]};f=b.map{|c|!c[1]}
[[z=I.map{|v|v%3+v/3*9},z.map{|v|v*3}],[x=I.map{|v|v*9},I],[I,x]
].map{|s,t|t.map{|i|d=[a=0]*10;s.map{|j|c=b[i+j];c.map{|v|d[v]+=1if !f[i+j]}
v,r=*c;s.map{|k|b[i+k].delete(v)if j!=k}if !r 
s[(a+=1)..8].map{|k|s.map{|l|b[i+l]-=c if l!=k&&l!=j}if c.size==2&&c==b[i+k]}}
v=d.index 1;f[i+k=s.find{|j|b[i+j].index v}]=b[i+k]=[v]if v}}while f.index(!1)
p b*''

Example:

C:\golf>soduku2.rb 030001000006000050500000983080006302000050000903800060714000009020000800000400030
"832591674496387251571264983185746392267953418943812765714638529329175846658429137"

quick explanation:
Board b is an array of 81 arrays holding all the possible values for each cell. The array on line three holds [offset,start_index] for each group (boxes,rows,columns). Three tasks are performed while iterating through the groups.

  1. The value of any cell of size 1 is removed from the rest of the group.
  2. If any pair of cells contain the same 2 values, these values are removed from the rest of the group.
  3. The count of each value is stored in d - if there is only 1 instance of a value, we set the containing cell to that value, and mark the cell fixed in f

Repeat until all cells are fixed.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can omit the brackets in I=*(0..8), will save 2 chars. \$\endgroup\$ – Dogbert Feb 8 '11 at 17:02
  • \$\begingroup\$ I get sudokusolver.rb:8: unterminated string meets end of file if I start it with ruby1.8 sudokusolver.rb 030.... What am I doing wrong? \$\endgroup\$ – user unknown May 4 '11 at 23:53
  • \$\begingroup\$ Looks like there is an extra ' on the last line. Not sure how that got there... \$\endgroup\$ – AShelly May 5 '11 at 2:27
3
\$\begingroup\$

Prolog - 493 Characters

:-use_module(library(clpfd)).
a(X):-all_distinct(X).
b([],[],[]).
b([A,B,C|X],[D,E,F|Y],[G,H,I|Z]):-a([A,B,C,D,E,F,G,H,I]),b(X,Y,Z).
c([A,B,C,D,E,F,G,H,I|X])-->[[A,B,C,D,E,F,G,H,I]],c(X).
c([])-->[].
l(X,Y):-length(X,Y).
m(X,Y):-maplist(X,Y).
n(L,M):-l(M,L).
o(48,_).
o(I,O):-O is I-48.
:-l(L,81),see(user),m(get,L),seen,maplist(o,L,M),phrase(c(M),R),l(R,9),m(n(9),R),append(R,V),V ins 1..9,m(a,R),transpose(R,X),m(a,X),R=[A,B,C,D,E,F,G,H,I],b(A,B,C),b(D,E,F),b(G,H,I),flatten(R,O),m(write,O).

Output:

Inputting: 000000000000003085001020000000507000004000100090000000500000073002010000000040009 Outputs: 987654321246173985351928746128537694634892157795461832519286473472319568863745219

Inputting: 030001000006000050500000983080006302000050000903800060714000009020000800000400030 Outputs: 832591674496387251571264983185746392267953418943812765714638529329175846658429137

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Perl 5, 295 bytes

sub P{$r=$p/9;$c=$p%9;$q=3*~~($r/3)+$c/3}sub N{($i,$u)=@_;P;$G[$p]=$u*$i;$R[$r]{$i}=$C[$c]{$i}=$Q[$q]{$i}=$u}sub S{if($p>80){print@G;exit}if($G[$p]){S(++$p);$p--}else{N($_,1),S(++$p),$p--,N($_)for grep{P;$R[$r]{$_}+$C[$c]{$_}+$Q[$q]{$_}<1}1..9}}@G=split'',$ARGV[0];N($G[$p=$_],1)for 0..80;$p=0;S

Try it online!

Shortened from 339 to 317 to 315 to 314 to 310 to 309 to 298 to 295

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ nice. there is the test case in the Prolog answer 000000000000003085001020000000507000004000100090000000500000073002010000000040009. Would you like to run your solution with this test case? \$\endgroup\$ – mazzy Jul 15 at 10:47
  • 1
    \$\begingroup\$ Nice example :-) . It is kind of worst case, with a solution having 987654321 in the first line. It runs into the time limit on TIO, but run locally on my PC it still outputs the correct solution -- after around 10 minutes. There is, of course, room for performance optimization, but it would make the code longer. \$\endgroup\$ – Donat Jul 15 at 14:05
  • \$\begingroup\$ Thanks. This is CodeGolf, so a performance does not matter \$\endgroup\$ – mazzy Jul 15 at 15:35
  • \$\begingroup\$ I'm afraid the grep uses guesswork and your solution uses a brute force. I'm guessing :) your answer would be better suited for Implement a Brute Force Sudoku Solver. See rule 5 in this question. \$\endgroup\$ – mazzy Jul 15 at 16:22
  • 1
    \$\begingroup\$ If backtracking were not allowed, a solution in Prolog should not be valid either because Prolog does backtracking inherently. It is just hidden under the surface. \$\endgroup\$ – Donat Jul 15 at 16:41
3
\$\begingroup\$

PowerShell, 491 490 488 465 463 bytes

$w=,0*81;$c=,(1..9)*81
$a=(24,24,6)*3|%{,(0..8|%{($r++)});,(0..8|%{$v%81;$v+=9});$v++;,((1,1,7)*3|%{+$q;$q+=$_});$q-=$_}
filter g($v,$i){if($v){$a|?{$i-in$_}|%{$_|%{$c[$_]=$c[$_]-ne$v}};$w[$i]=$v;$c[$i]=@()}}
$args|% t*y|%{g($_-48)($i++)}
for(;$a|%{($b=$_)|?{($v=$c[$_])}|?{(($c[$b]|%{"$_"})-eq$v).Count-eq$v.Count
$c[$b]|%{$_}|group|? C* -eq 1|? N* -in $v|%{$v=+$_.Name;1}}|%{$b|?{"$v"-ne$c[$_]}|%{$c[$_]=@($c[$_]|?{$_-notin$v})}
g($v[0]*!$v[1])$_
1}}){}
-join$w

Try it online!

Implemented Solving methods: Single, Naked Pair, Naked Trio, Naked Quad and Hidden Single.

See Terms related to solving

See also the code with debug output.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.