# Code Challenge: Sudoku Solver (Intermediate - Hard)

Page 1 of 1

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

### #1 AdamSpeight2008

• MrCupOfT

Reputation: 2292
• Posts: 9,531
• Joined: 29-May 08

# Code Challenge: Sudoku Solver (Intermediate - Hard)

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

• ﻿>>──(Knee)──►

Reputation: 126
• 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

• Critical Section

Reputation: 1820
• 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

• MrCupOfT

Reputation: 2292
• Posts: 9,531
• 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

• Changed Man With Different Priorities

Reputation: 952
• Posts: 2,364
• 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

• Caffeine: db "Never Enough!"

Reputation: 223
• 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

• I wrote you an code

Reputation: 1020
• Posts: 3,567
• 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

• D.I.C Head

Reputation: 27
• 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

• New D.I.C Head

Reputation: 13
• 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

• I wrote you an code

Reputation: 1020
• Posts: 3,567
• Joined: 12-May 09

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

Posted 12 June 2011 - 01:45 PM

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

Was This Post Helpful? 0

### #11 Patrunjel

• D.I.C Regular

Reputation: 17
• 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

• MrCupOfT

Reputation: 2292
• Posts: 9,531
• 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

• MrCupOfT

Reputation: 2292
• Posts: 9,531
• 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

• I wrote you an code

Reputation: 1020
• Posts: 3,567
• Joined: 12-May 09

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

Posted 13 June 2011 - 09:42 PM

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

### #15 RetardedGenius

• ﻿>>──(Knee)──►

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

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }