14 Replies - 18462 Views - Last Post: 14 June 2011 - 03:18 PM

#1 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2263
  • View blog
  • Posts: 9,468
  • Joined: 29-May 08

Code Challenge: Sudoku Solver (Intermediate - Hard)

Post icon  Posted 11 June 2011 - 08:01 AM

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


Is This A Good Question/Topic? 1
  • +

Replies To: Code Challenge: Sudoku Solver (Intermediate - Hard)

#2 RetardedGenius  Icon User is offline

  • >>──(Knee)──►
  • member icon

Reputation: 126
  • View blog
  • Posts: 555
  • Joined: 30-October 10

Re: Code Challenge: Sudoku Solver (Intermediate - Hard)

Posted 11 June 2011 - 12:33 PM

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

Was This Post Helpful? 0
  • +
  • -

#3 smohd  Icon User is offline

  • Critical Section
  • member icon


Reputation: 1819
  • View blog
  • Posts: 4,627
  • Joined: 14-March 10

Re: Code Challenge: Sudoku Solver (Intermediate - Hard)

Posted 11 June 2011 - 01:50 PM

What is the difference between the valid one and the invalid one? I want to try but I have never played it before:
Was This Post Helpful? 2
  • +
  • -

#4 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2263
  • View blog
  • Posts: 9,468
  • Joined: 29-May 08

Re: Code Challenge: Sudoku Solver (Intermediate - Hard)

Posted 11 June 2011 - 02:04 PM

Fixed the stupido mastike.
Was This Post Helpful? 0
  • +
  • -

#5 codeprada  Icon User is offline

  • Changed Man With Different Priorities
  • member icon

Reputation: 947
  • View blog
  • Posts: 2,355
  • Joined: 15-February 11

Re: Code Challenge: Sudoku Solver (Intermediate - Hard)

Posted 11 June 2011 - 02:30 PM

Command line,GUI or it doesn't matter?
Was This Post Helpful? 0
  • +
  • -

#6 v0rtex  Icon User is offline

  • Caffeine: db "Never Enough!"
  • member icon

Reputation: 223
  • View blog
  • Posts: 773
  • Joined: 02-June 10

Re: Code Challenge: Sudoku Solver (Intermediate - Hard)

Posted 11 June 2011 - 02:41 PM

@ codeprada: I imagine its not too important but making it look pretty is always nice :)
Was This Post Helpful? 0
  • +
  • -

#7 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 906
  • View blog
  • Posts: 3,171
  • Joined: 12-May 09

Re: Code Challenge: Sudoku Solver (Intermediate - Hard)

Posted 11 June 2011 - 02:46 PM

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.
Was This Post Helpful? 0
  • +
  • -

#8 MathiasVP  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 154
  • Joined: 08-August 10

Re: Code Challenge: Sudoku Solver (Intermediate - Hard)

Posted 11 June 2011 - 05:45 PM

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.
Was This Post Helpful? 0
  • +
  • -

#9 skorned  Icon User is offline

  • New D.I.C Head

Reputation: 13
  • View blog
  • Posts: 41
  • Joined: 30-August 08

Re: Code Challenge: Sudoku Solver (Intermediate - Hard)

Posted 12 June 2011 - 10:03 AM

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.
Was This Post Helpful? 2
  • +
  • -

#10 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 906
  • View blog
  • Posts: 3,171
  • Joined: 12-May 09

Re: Code Challenge: Sudoku Solver (Intermediate - Hard)

Posted 12 June 2011 - 01:45 PM

View Postskorned, 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

Was This Post Helpful? 0
  • +
  • -

#11 Patrunjel  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 17
  • View blog
  • Posts: 298
  • Joined: 28-October 10

Re: Code Challenge: Sudoku Solver (Intermediate - Hard)

Posted 13 June 2011 - 01:10 PM

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? ;;) )
Was This Post Helpful? 1
  • +
  • -

#12 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2263
  • View blog
  • Posts: 9,468
  • Joined: 29-May 08

Re: Code Challenge: Sudoku Solver (Intermediate - Hard)

Posted 13 June 2011 - 04:25 PM

Here's my 88 LoC Brute-force Solver.


Module Code


Spoiler



Cell
This class encapsulate a Sudoku Cell.

Spoiler



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

Spoiler



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


Spoiler

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

Was This Post Helpful? 1
  • +
  • -

#13 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2263
  • View blog
  • Posts: 9,468
  • Joined: 29-May 08

Re: Code Challenge: Sudoku Solver (Intermediate - Hard)

Posted 13 June 2011 - 06:14 PM

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

Was This Post Helpful? 0
  • +
  • -

#14 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 906
  • View blog
  • Posts: 3,171
  • Joined: 12-May 09

Re: Code Challenge: Sudoku Solver (Intermediate - Hard)

Posted 13 June 2011 - 09:42 PM

View PostPatrunjel, 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
Was This Post Helpful? 0
  • +
  • -

#15 RetardedGenius  Icon User is offline

  • >>──(Knee)──►
  • member icon

Reputation: 126
  • View blog
  • Posts: 555
  • Joined: 30-October 10

Re: Code Challenge: Sudoku Solver (Intermediate - Hard)

Posted 14 June 2011 - 03:18 PM

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! :o
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1