[AdamSpeight2008]

Code Challenge: Sudoku Solver

Write a Sudoku Puzzle Solver.

Each row can only contain a distinct arrangement of the numbers 1 to 9.
Each column can only contain a distinct arrangement of the numbers 1 to 9.
Each house can only contain a distinct arrangement of the number 1 to 9.
An house being the nine squares contained in each section of the grid.
Example.

Valid Sudoku (Single Solution)

53 ¦ 7 ¦   
6  ¦195¦   
 98¦   ¦ 6 
---+---+---
8  ¦ 6 ¦  3
4  ¦8 3¦  1
7  ¦ 2 ¦  6
---+---+---
 6 ¦   ¦28 
   ¦419¦  5
   ¦ 8 ¦ 79

Invalid Sudoku (Multiple Solutions)

5 6¦ 2 ¦9 3
  8!   ¦5  
   !   ¦   
---+---+---
6  ¦285¦  9
   ¦9 3¦   
8  ¦761¦  4
---+---+---
   ¦   ¦   
  4¦   ¦3  
2 1¦ 5 ¦6 7

I'll award Reputations Points for interesting submissions.

• The shortest code
  
• The quickest solver. (Tested on the 2 above grids).
  
• Interesting way of solving.

This post has been edited by AdamSpeight2008: 11 June 2011 - 02:03 PM

[RetardedGenius]

Excellent challenge Adam! Is it OK if I give this a try with C#? (I just can't get on with VB... )
If I can write a solution - I doubt it - I'll do it in VB.NET.

This post has been edited by RetardedGenius: 12 June 2011 - 05:52 AM

[smohd]

What is the difference between the valid one and the invalid one? I want to try but I have never played it before:

[AdamSpeight2008]

Fixed the stupido mastike.

[codeprada]

Command line,GUI or it doesn't matter?

[v0rtex]

@ codeprada: I imagine its not too important but making it look pretty is always nice

[xclite]

This is a fun exercise, I actually just did one in Ruby. I'd recommend looking into constraint satisfaction problems as one avenue for solving these sorts of things.

One guy I knew wrote a genetic algorithm to solve sudoku problems - not really the best use of genetic algorithms, but also something fun to try.

[MathiasVP]

Indeed a great challenge. I made a C++ solution a few weeks ago. To my surprise it was quite hard to implement an algorithm that was able to "guess" on values for harder soduko puzzles.

[skorned]

I suspect anything other than brute forcing each possible value in each empty square would be non-trivial. Here's the approach I would take:

• Create a cell class, wherein every cell object would represent one number spot in the grid. This will have a member variable, which will be a list of all possible digits that can be entered there. It will start off with all the digits from 0 to 9, of which entries will be removed as the algorithm progresses.
  
• Then, create a 2D array holding 9x9 cells.
  
• Parse through each row. For each cell encountered, if there is a definite value in it, cross out that value from all the other cells in that row.
  
• Similarly, parse through every column.
  
• Then, parse through every 'house'.
  
• In each of these parsing loops, if a cell is encountered where only 1 number if possible, fill it in.

This code will already be quite complicated if it to follow DRY and not be too hand-coded. And it might still not be very efficient, or even successful, at solving the harder sudokus, because one can mentally follow a chain of thought which is hard to replicate in a hard and fast algorithm.

[xclite]

skorned, on 12 June 2011 - 01:03 PM, said:

I suspect anything other than brute forcing each possible value in each empty square would be non-trivial.

The idea is to be non-trivial - naive approaches can only get one so far.

Quote

[/list]
[*]Parse through each row. For each cell encountered, if there is a definite value in it, cross out that value from all the other cells in that row.
[*]Similarly, parse through every column.
[*]Then, parse through every 'house'.
[/list]

With a little intuition into how these are setup, you can do these 3 all at once.

Quote

In each of these parsing loops, if a cell is encountered where only 1 number if possible, fill it in.

And if more than one is possible...? This algorithm also doesn't deal with reducing possible choices each time you update the board.

Quote

This code will already be quite complicated if it to follow DRY and not be too hand-coded. And it might still not be very efficient, or even successful, at solving the harder sudokus, because one can mentally follow a chain of thought which is hard to replicate in a hard and fast algorithm.

It isn't overly complicated to replicate the optimal sudoku algorithm in code. I did it in fewer than 200 lines of code.

This post has been edited by xclite: 17 June 2011 - 11:54 AM

[Patrunjel]

Actually brute-forcing the combinations is kind of straight forward... You just need a way to separate the fixed numbers (the one in the input) from the ones that you need to check (like a struct with a bool that represents this), 3 functions for checking the row, column and square, and a simple understanding of how backtrackig works, and it's done.
(can't you make this challenge available for all the languages? ; )

[AdamSpeight2008]

Here's my 88 LoC Brute-force Solver.


Module Code

Spoiler

Option Strict On
Option Explicit On
Module Module1

  Sub Main()
    Console.WriteLine("Puzzle 1")
    Dim sc1 = 0
    Dim p1 = Sudoku.CreateFromArray({
 5, 3, 0, 0, 7, 0, 0, 0, 0,
 6, 0, 0, 1, 9, 5, 0, 0, 0,
 0, 9, 8, 0, 0, 0, 0, 6, 0,
 8, 0, 0, 0, 6, 0, 0, 0, 3,
 4, 0, 0, 8, 0, 3, 0, 0, 1,
 7, 0, 0, 0, 2, 0, 0, 0, 6,
 0, 6, 0, 0, 0, 0, 2, 8, 0,
 0, 0, 0, 4, 1, 9, 0, 0, 5,
 0, 0, 0, 0, 8, 0, 0, 7, 9})

    AddHandler p1.Found, Sub(SolArgs As SolutionArgs)
                           sc1 += 1
                           Console.WriteLine("Solution {0} Found in {1}ms", sc1, SolArgs.FoundIn.TotalMilliseconds)
                           Console.WriteLine(SolArgs.Solution)
                           SolArgs.IsCancelled = (sc1 = 2)
                         End Sub
    Console.WriteLine(p1)
    Console.WriteLine()
    p1.Solve()

    Console.WriteLine()
    Console.WriteLine("Puzzle 2")

    Dim sc2 = 0
    Dim p2 = Sudoku.CreateFromArray({
5, 0, 6, 0, 2, 0, 9, 0, 3,
0, 0, 8, 0, 0, 0, 5, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
6, 0, 0, 2, 8, 5, 0, 0, 9,
0, 0, 0, 9, 0, 3, 0, 0, 0,
8, 0, 0, 7, 6, 1, 0, 0, 4,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 4, 0, 0, 0, 3, 0, 0,
2, 0, 1, 0, 5, 0, 6, 0, 7})
    AddHandler p2.Found, Sub(SolArgs As SolutionArgs)
                           sc2 += 1
                           Console.WriteLine("Solution {0} Found in {1}ms", sc2, SolArgs.FoundIn.TotalMilliseconds)
                           Console.WriteLine(SolArgs.Solution)
                           SolArgs.IsCancelled = (sc2 = 2)
                         End Sub
    Console.WriteLine(p2)
    p2.Solve()
  End Sub


End Module

Cell
This class encapsulate a Sudoku Cell.

Spoiler

Public Class Cell
  Protected Zero2Eight As Integer() = {0, 1, 2, 3, 4, 6, 7, 8}
  Public Property Value() As Integer
  Private mSud As Sudoku
  Private x, y, h As Integer
  Public Sub New(ByVal id As Integer, ByVal value As Integer, Sud As Sudoku)
    mSud = Sud : _Value = value : y = id \ 9 : x = id Mod 9 : h = ((id \ 27) * 27) + ((x \ 3) * 3)
  End Sub
  Public Function Contains(ByVal value As Integer) As Boolean
    Return Zero2Eight.Any(Function(o) (mSud(9 * y + o).Value = value) OrElse (mSud(9 * o + x).Value = value)) OrElse
      {h + 0, h + 1, h + 2, h + 9, h + 10, h + 11, h + 18, h + 19, h + 20}.Any(Function(o) mSud(o).Value = value)
  End Function
  Public Overrides Function ToString() As String
    Return Me.Value.ToString
  End Function
End Class

SolutionArgs
This class encapsulates the solution arguments when a solution is found.

Spoiler

Public Class SolutionArgs
  Inherits EventArgs
  Protected _FoundIn As TimeSpan
  Protected _Solution As Sudoku
  Public IsCancelled As Boolean = False
  Public Sub New(FoundIn As TimeSpan, Solution As Sudoku)
    _FoundIn = FoundIn : _Solution = Solution
  End Sub
  Public Function FoundIn() As TimeSpan
    Return _FoundIn
  End Function
  Public Function Solution() As Sudoku
    Return _Solution
  End Function
End Class

Sudoku
This class encapsulates a Suduko grid. Also includes the Solver.

Spoiler

Public Class Sudoku
  Protected mCells(81) As Cell
  Protected mSW As New Diagnostics.Stopwatch
  Private mCanelled As Boolean = False
  Public Event Found(SolArgs As SolutionArgs)
  Public Sub New()
    For x As Integer = 0 To 80 : mCells(x) = New Cell(x, 0, Me) : Next
  End Sub
  Private Sub New(sa As Sudoku)
    For x As Integer = 0 To 80 : mCells(x) = New Cell(x, sa(x).Value, Me) : Next
  End Sub
  Public Shared Function CreateFromArray(ByVal sa As Integer()) As Sudoku
    If sa.Length <> 81 Then Throw New ArgumentException("Array.Length is not 81 ")
    Dim s As New Sudoku
    For i As Integer = 0 To 80
      If (sa(i) <> 0) AndAlso (s(i).Contains(sa(i))) Then Throw New ArgumentOutOfRangeException(String.Format("[{0}] has a {1}", i, sa(i)))
      s(i).Value = sa(i)
    Next
    Return s
  End Function
  Default Public Property Item(ByVal Index As Integer) As Cell
    Get
      Return mCells(Index)
    End Get
    Set(value As Cell)
      mCells(Index) = value
    End Set
  End Property
  Public Function Timing() As TimeSpan
    Return mSW.Elapsed
  End Function
  Public Sub Solve()
    mSW = Stopwatch.StartNew() : Solver(0) : mSW.Stop()
  End Sub
  Protected Sub Solver(ByVal Index As Integer)
    If mCanelled Then Exit Sub
    While (Index < 81) AndAlso (Me(Index).Value <> 0) : Index += 1 : End While
    If Index < 81 Then
      For Guess = 1 To 9
        If Me(Index).Contains(Guess) Then Continue For
        Me(Index).Value = Guess : Solver(Index) : Me(Index).Value = 0
      Next
    Else
      Dim SolArgs As New SolutionArgs(mSW.Elapsed, New Sudoku(Me))
      RaiseEvent Found(SolArgs) : mCanelled = SolArgs.IsCancelled
    End If
  End Sub
  Public Overrides Function ToString() As String
    Dim rs As New System.Text.StringBuilder(136)
    For i = 0 To 80
      Dim m = i Mod 9
      rs.Append(If(Me(i).Value=0," ", Me(i).Value)).Append(If({2, 5}.Contains(m), "¦", ""))
      If m = 8 Then rs.AppendLine()
      If ((i Mod 27) = 26) AndAlso (i <= 54) Then rs.AppendLine("---+---+---")
    Next
    Return rs.ToString
  End Function
End Class

This post has been edited by AdamSpeight2008: 13 June 2011 - 04:29 PM

[AdamSpeight2008]

Re-factored the previous. (Now 5 classes and 99 LoC)

The type use for conveying a solution is now no longer Sudoku but its own Solution class. (Notice how it inherits the base class Sudoku_Base

Suduko_Base

Public MustInherit Class Sudoku_Base
  Protected mCells(80) As Cell
  Public Overrides Function ToString() As String
    Dim rs As New System.Text.StringBuilder(256)
    For i = 0 To 72 Step 9
      rs.AppendFormat("{0}{1}{2}¦{3}{4}{5}¦{6}{7}{8}", mCells.Skip(i).Take(9).ToArray()).AppendLine(If({18, 45}.Contains(i), ControlChars.NewLine & "---+---+---", ""))
    Next
    Return rs.ToString
  End Function
  Protected Friend Sub New(Optional sa As Sudoku_Base = Nothing)
    For x As Integer = 0 To 80 : mCells(x) = New Cell(x, If(sa Is Nothing, 0, sa(x).Value), Me) : Next
  End Sub
  Default Public ReadOnly Property Item(ByVal Index As Integer) As Cell
    Get
      Return mCells(Index)
    End Get
  End Property
End Class

Sudoku

Public Class Sudoku
  Inherits Sudoku_Base
  Protected mSW As New Diagnostics.Stopwatch
  Private mCanelled As Boolean = False
  Public Event Found(SolArgs As SolutionArgs)
  Public Shared Function EmptyGrid() As Sudoku
    Return New Sudoku()
  End Function
  Public Shared Function CreateFromArray(ByVal sa As Integer()) As Sudoku
    If sa.Length <> 81 Then Throw New ArgumentException("Array.Length is not 81 ")
    Dim s As New Sudoku
    For i As Integer = 0 To 80
      If (sa(i) <> 0) AndAlso (s(i).Contains(sa(i))) Then Throw New ArgumentOutOfRangeException(String.Format("[{0}] has a {1}", i, sa(i)))
      s(i).Value = sa(i)
    Next
    Return s
  End Function
  Default Public Shadows Property Item(ByVal Index As Integer) As Cell
    Get
      Return mCells(Index)
    End Get
    Set(value As Cell)
      mCells(Index) = value
    End Set
  End Property
  Public Function Timing() As TimeSpan
    Return mSW.Elapsed
  End Function
  Public Sub Solve()
    mSW = Stopwatch.StartNew() : Solver(0) : mSW.Stop()
  End Sub
  Protected Sub Solver(ByVal Index As Integer)
    If mCanelled Then Exit Sub
    While (Index < 81) AndAlso (Me(Index).Value <> 0) : Index += 1 : End While
    If Index < 81 Then
      For Guess = 1 To 9
        If Me(Index).Contains(Guess) Then Continue For
        Me(Index).Value = Guess : Solver(Index) : Me(Index).Value = 0
      Next
    Else
      Dim SolArgs As New SolutionArgs(mSW.Elapsed, New Solution(Me))
      RaiseEvent Found(SolArgs) : mCanelled = SolArgs.IsCancelled
    End If
  End Sub
End Class

Solution

Public Class Solution
  Inherits Sudoku_Base
  Protected Friend Sub New(sa As Sudoku)
    MyBase.New(sa)
  End Sub
End Class

Cell

Public Class Cell
  Protected Zero2Eight As Integer() = {0, 1, 2, 3, 4, 6, 7, 8}
  Public Property Value() As Integer
  Private mSud As Sudoku_Base
  Private x, y, h As Integer
  Protected Friend Sub New(ByVal id As Integer, ByVal value As Integer, Sud As Sudoku_Base)
    mSud = Sud : _Value = value : y = id \ 9 : x = id Mod 9 : h = ((id \ 27) * 27) + ((x \ 3) * 3)
  End Sub
  Public Function Contains(ByVal value As Integer) As Boolean
    Return Zero2Eight.Any(Function(o) (mSud(9 * y + o).Value = value) OrElse (mSud(9 * o + x).Value = value)) OrElse
      {h + 0, h + 1, h + 2, h + 9, h + 10, h + 11, h + 18, h + 19, h + 20}.Any(Function(o) mSud(o).Value = value)
  End Function
  Public Overrides Function ToString() As String
    Return If(_Value = 0, " ", Me.Value)
  End Function
End Class

SolutionArgs

Public Class SolutionArgs
  Inherits EventArgs
  Protected _FoundIn As TimeSpan
  Protected _Solution As Solution
  Public IsCancelled As Boolean = False
  Public Sub New(FoundIn As TimeSpan, Solution As Solution)
    _FoundIn = FoundIn : _Solution = Solution
  End Sub
  Public Function FoundIn() As TimeSpan
    Return _FoundIn
  End Function
  Public Function Solution() As Solution
    Return _Solution
  End Function
End Class

[xclite]

Patrunjel, on 13 June 2011 - 04:10 PM, said:

Actually brute-forcing the combinations is kind of straight forward... You just need a way to separate the fixed numbers (the one in the input) from the ones that you need to check (like a struct with a bool that represents this), 3 functions for checking the row, column and square, and a simple understanding of how backtrackig works, and it's done.
(can't you make this challenge available for all the languages? ; )

I don't think anybody was arguing a brute force wasn't straight-forward, just inefficient =p

[RetardedGenius]

Not a solution but I thought that some of you may also be interested in seeing this lego robot that can solve Sodoku problems with a pen!