29
\$\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 sudokus 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
Improve this question
\$\endgroup\$
14
  • \$\begingroup\$ You should really add a time limit. \$\endgroup\$ Commented Feb 2, 2011 at 0:30
  • 1
    \$\begingroup\$ @JPvdMerwe: Good point, but a time limit would be hard to standardize. \$\endgroup\$ Commented Feb 2, 2011 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\$ Commented Feb 2, 2011 at 1:47
  • 3
    \$\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\$ Commented Feb 2, 2011 at 4:47
  • 9
    \$\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\$ Commented May 17, 2014 at 2:41

4 Answers 4

Reset to default
6
\$\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\$
3
  • \$\begingroup\$ You can omit the brackets in I=*(0..8), will save 2 chars. \$\endgroup\$ Commented Feb 8, 2011 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\$ Commented May 4, 2011 at 23:53
  • \$\begingroup\$ Looks like there is an extra ' on the last line. Not sure how that got there... \$\endgroup\$ Commented May 5, 2011 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\$
7
  • \$\begingroup\$ nice. there is the test case in the Prolog answer 000000000000003085001020000000507000004000100090000000500000073002010000000040009. Would you like to run your solution with this test case? \$\endgroup\$ Commented Jul 15, 2020 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\$ Commented Jul 15, 2020 at 14:05
  • \$\begingroup\$ Thanks. This is CodeGolf, so a performance does not matter \$\endgroup\$ Commented Jul 15, 2020 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\$ Commented Jul 15, 2020 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\$ Commented Jul 15, 2020 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\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.