Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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
share|improve this question
    
You should really add a time limit. –  JPvdMerwe Feb 2 '11 at 0:30
    
Pretty sure this has been done before. There are some very short solvers out there, but some puzzles will take a long long time to solve using a naive algorithm –  gnibbler Feb 2 '11 at 0:40
1  
@JPvdMerwe: Good point, but a time limit would be hard to standardize. –  snmcdonald Feb 2 '11 at 1:19
1  
@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
1  
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
show 8 more comments

2 Answers

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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