# Implement a Non-Guessing Sudoku Solver

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

`````` | 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
``````
-
You should really add a time limit. – JPvdMerwe Feb 2 '11 at 0:30
@JPvdMerwe: Good point, but a time limit would be hard to standardize. – snmcdonald Feb 2 '11 at 1:19
@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. – snmcdonald Feb 2 '11 at 1:47
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. – Andy Feb 2 '11 at 4:47
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? – xnor May 17 '14 at 2:41

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.

-
You can omit the brackets in `I=*(0..8)`, will save 2 chars. – Dogbert Feb 8 '11 at 17:02
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? – user unknown May 4 '11 at 23:53
Looks like there is an extra ' on the last line. Not sure how that got there... – AShelly May 5 '11 at 2:27

Microsoft Small Basic (http://smallbasic.com/)

Not classically golfed, but this was my entry for the Small Basic 25 line challenge.

``````' Sudoku Solver (25 line challenge), by Jason T. Jacques <jtjacques@gmail.com>

'sudoku = "  873 6 5  5  6 91 2   5  31   9 57  9 2 1 4  62 4   87  9   6 23 1  8  6 4 721  "
'sudoku = "78 9   5    48 1       78  4   92 8 1 5   2 7 7 13   4  73       6 54    4   6 29"
'sudoku = "   15  7 1 6   82 3  86  4 9  4  567  47 83  732  6  4 4  81  9 17   2 8 5  37   "
sudoku = Program.GetArgument(Program.ArgumentCount)

crlf[9] = "                                                              "
For i = 1 To 81 ' generate grid
grid[Math.Ceiling(i / 9)][Math.Remainder(i - 1, 9) + 1] = Text.GetSubText(sudoku, 1, 1)
sudoku = Text.GetSubTextToEnd(sudoku, 2)
EndFor

For n = 1 To 6561 + 1 ' 81 x 81 (worst case, fill only one square on each check of the grid)
If (grid[Math.Ceiling((Math.Remainder(n - 1, 81) + 1) / 9)][Math.Remainder((Math.Remainder(n - 1, 81) + 1) - 1, 9) + 1] * 1 = 0) Or (n = 6562) Then ' or n - cheat to display final grid
position = Text.Append(Math.Ceiling((Math.Remainder(n - 1, 81) + 1) / 9), Math.Remainder((Math.Remainder(n - 1, 81) + 1) - 1, 9) + 1)
FillPosition()
EndIf
EndFor

Sub FillPosition
possible = "123456789" ' default 'pencil marks'
For i = 1 To 81 ' remove values present in row, column and grid
If (((grid[(Math.Remainder(i - 1, 9) + 1)][Text.GetSubText(position, 2, 1)] = Math.Ceiling(i/9)) Or (grid[Text.GetSubText(position, 1, 1)][(Math.Remainder(i - 1, 9) + 1)] = Math.Ceiling(i/9)) Or (grid[Math.Ceiling((Math.Remainder(i - 1, 9) + 1)/3) + (Math.Ceiling(Text.GetSubText(position, 1, 1) / 3) - 1) * 3][Math.Remainder((Math.Remainder(i - 1, 9) + 1) - 1, 3) + 1 + (Math.Ceiling(Text.GetSubText(position, 2, 1) / 3) - 1) * 3] = Math.Ceiling(i/9))) And (Text.IsSubText(possible, Math.Ceiling(i/9)))) Then
possible = Text.Append(Text.GetSubText(possible, 1, Text.GetIndexOf(possible, Math.Ceiling(i/9)) - 1), Text.GetSubTextToEnd(possible, Text.GetIndexOf(possible, Math.Ceiling(i/9)) + 1))
EndIf
TextWindow.Write(grid[Math.Ceiling(i / 9)][Math.Remainder(i - 1, 9) + 1] + " " + crlf[Math.Remainder(i - 1, 9) + 1])
EndFor
TextWindow.WriteLine("")
If Text.GetLength(possible) = 1 Then ' if only one possible result, use
grid[Text.GetSubText(position, 1, 1)][Text.GetSubText(position, 2, 1)] = possible
EndIf
EndSub
``````

Edit: updated to use command line arguments.

-
This does accept 0's instead of spaces for unknown values, but isn't smart enough to solve your example - what can I say, I suck at Sudoku! – jtjacques Feb 3 '11 at 0:01

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

-