Sudoku Solver

ruff_hi · Oct 23, 2010

Is anyone interested in improving their conceptual (and actual) programing skills by working with me to write a sudoku solver in excel's VBA?

I'm thinking that we spend the first week discussing the various approaches to coding this up, sharing the ideas and collectively coming to a 'game plan'. Initially, participants should try and come up with a fully conceptual framework of the solution (ie independently), then we share them and discuss. I this way, great ideas aren't missed. Remember the story about how a group of city officials were wondering what to do if a ship caught fire in the harbour? Someone had the crazy idea of getting people to stand on a bridge near the ship and blow it out to see - from that came the official solution - push it out to see with water jets on tug boats.

From there, we'll break the project up into logical components and spend the weeks after that putting together (and debugging) code.

I am not looking for someone to point out a fully worked solution ... the primary aim of this project is to improve the participants coding approach, logical thinking and project management - the end product is a by-product

.

@Mods - now, before anyone thinks that this thread has no placing being in the BUG forum, keep in mind that the BUG team has always been about improving coding skills and team building. We are also thinking about putting a sudoku puzzler in BUG and we have to provide a solver at the same time. A Civ4 Chess puzzle (scroll down to the bottom of the page) has been done before - why not sudoku?

ruff_hi · Oct 26, 2010

Ok, guess I just do it all myself then

.

Terminology
Every good project should start with a terminology section ... and this isn't an exception. Sudoku is a logical puzzle where you have to populate 81 cells (9 x 9) with the numbers 1 to 9 so that the no number appears twice in any row, column of block.

A Sudoku puzzle has 9 blocks, each block is 3 x 3 and no block overlaps with any other block.

I will also be referring to 'regions'. Each sudoku puzzle has 27 regions - 9 rows, 9 columns and 9 blocks. I am pretty sure that I can code using regions and totally ignore if the region is actually a row, column of block - I don't think the code should care.

My Proposed Approach
The approach that I will be looking at developing is based in Excel vba. It will have an empty Sudoku puzzle that the user can populate as well as a 'Solve' macro button. The solve macro will not fully solve the puzzle. Instead, it will run a single series of 'tests' against the puzzle to see if it can solve some of the cells. By repeatedly clicking on the solve button, the puzzle should eventually get solved. I'm planning on using this step wize approach to simplify the initial coding (yeah, sure - I will probably add a 'do until solved' loop) but also so that the user can experience the fun of solving the puzzle too.

I am planning to use 'classes' extensively. I am sure that EFool will chirp in and correct my class-ify approach and / or terminology

.

Spoiler Soduko Class :

Spoiler Cell class :

Spoiler Region class :

Spoiler Solving Loop :

EmperorFool · Oct 27, 2010

You'll need these methods on Cell:

Set(value) - Store the value for the cell and remove it as a possible for other cells in the Regions to which it belongs. Should enforce that it's a possible value first.
Clear() - Remove the value for the cell (if there is one) and add it back to the possibles for cells in the Regions to which it belongs.

Since I've built this in Java before, I don't want to say too much about a solution. After chatting, though, I think you're solve is going to go way beyond mine.

Another thought: add a property to Cell to track if the current value was entered by the user or derived during the solution. This way you can easily rollback derived values without undoing the user's hard work.

It might be nice to color-code the value's based on this property, too.

ruff_hi · Oct 27, 2010

EmperorFool said:
You'll need these methods on Cell:

Set(value) - Store the value for the cell and remove it as a possible for other cells in the Regions to which it belongs. Should enforce that it's a possible value first.

Clear() - Remove the value for the cell (if there is one) and add it back to the possibles for cells in the Regions to which it belongs.

VBA's Value property can be both a 'get' and 'set' at the same time. Re Clear, I am going to include that but I'm going to utilize excel for that part of it.

Another thought: add a property to Cell to track if the current value was entered by the user or derived during the solution. This way you can easily rollback derived values without undoing the user's hard work. It might be nice to color-code the value's based on this property, too.

Yep - color coding will come into play ... again, it will be done in excel not in vba.

I'm attaching v1 of the spreadsheet. Zero VBA yet, but I have the excel framework up and ... errr ... not running ... I guess sitting.

PieceOfMind · Oct 30, 2010

I had a java sudoku solver I was working on ages ago. I never got around to finishing it because I never did learn how to build a GUI for it (one has to enter the numbers one by one at the command prompt), and the solver wasn't able to solve all puzzles (almost always the easy ones though). If you have a look at the terminology used by the pros, my program is limited to finding 'hidden singles' and 'naked singles'.

It's interesting because your overall approach has things that are similar. I suppose that's not all that amazing though, considering it's an approach to a common puzzle.

Anyway, if you're interested, I'll attach my code. Are you worried about spoilers? Remember, it's not a full solution yet, but an implementation similar to what you have described. And it's all in java - no VBA.

ruff_hi · Oct 30, 2010

I've finished the excel interface element of my sudoku solver (latest version attached) ... and here is where excel provides some very useful advantages over other programming languages, it comes with its own interface pre-built.

I've also found a nice puzzle (Rated Very Hard) to solve ...

I was able to solve it in about 10 minutes which is the quickest that I have solved a 'very hard' puzzle.

My current solver can identify cells that only have 1 value (ie the other 8 are eliminated) as well as cells that contain a unique solution (ie the only cell in a region that contains a number). Using those two methods, it was able to get the puzzle to this stage ...

My solver also provides a diagnostic output that shows the 'possible' solutions for the puzzle.

ruff_hi · Oct 30, 2010

I can see two obvious improvements ... blocking and group elimination.

Blocking
If you look at the puzzle above, you can see that in the middle left region, only the center row contains a '7'. Thus no other cell in that row can contain a '7' and all 7s should be eliminated. With my current coding set up, this would mean that information from one region would need to interact with another region. I am still thinking about ways of doing that.

Group Elimination
There are 3 examples of group elimination that I can think of (there are probably more). An example can be seen in the center block. The center left and center top cells are the only cells that contain a '2' and an '8'. Thus those are the cells that must contain those values and the other 'possibles' in those cells can be eliminated. With that information, then you can see that the '1' value for the center block must go in the right column of that block and thus you get a unique solution below (the 1 drops out of the 13 cell).

This is an example of a grouping elimination followed by a blocking elimination yields a cell solution and how the order of running these eliminations has an impact on finding (or not) a solution for a cell.

Other forms of Group Elimination are shown below:
Row: 123, 12, 13, 1345, 135
You can see that the first 3 cells for a group (123, 12, 13) and those values can be eliminated from the 4th and 5th cells

Row: 28, 28, 128, 2348, 2348
The first 2 cells for a group (28, 28) and those values can be eliminated from the other cells.

Row: 28, 27, 78, 2348, 23478
The first 3 cells for a group (28, 27, 78) and those values can be eliminated from the other cells.

I think I have a programmatic solution for the second example above (as well as the '28' group in the picture) but I don't yet have a solution for the first and third grouping examples.

ruff_hi · Oct 30, 2010

PieceOfMind said:
If you have a look at the terminology used by the pros, my program is limited to finding 'hidden singles' and 'naked singles'.

Holy cow - what have I gotten myself into ... look at the list of strategies on this site.

Anyway, if you're interested, I'll attach my code. Are you worried about spoilers? Remember, it's not a full solution yet, but an implementation similar to what you have described. And it's all in java - no VBA.

'worried about spoilers' ... I guess the answer is 'yes' and 'no'. 'Yes' in that I would like the first bite at identifying areas to improve my solver and developing code to address those areas. 'No' in that I fully expect myself to miss areas of improvement and not be able to develop code that provides solutions identified.

Also, as you know, everyone's code is a little bit idiosyncratic so understanding the solution and understanding how it is implemented in the code is two totally different things. I guess what I am saying is ... feel free to point out solution techniques that I am missing and provide code suggestions when I get stuck ... how does that sound?

ruff_hi · Oct 30, 2010

ruff_hi said:
I think I have a programmatic solution for the second example above

My thinking re this set is to loop through the numbers 1 to 9 and build a string of the cells in a region where that number is possible.

Thus my string of possible cell solutions for the middle region for the number '2' would be '24' (ie cell 2 and cell 4 - cells numbered left to right, top to bottom). My string solution for the number '8' would also be '24'.

Once I have built the array of string solutions, I then loop over all of the combinations, comparing them and if I get a match, then I can eliminate the non paired possibles from those cells.

I actually 'cheat' and use this string based approach in my current code when looking for unique (or hidden singles). I loop over the 9 numbers, building a string of the cell location where that number is a possible. If the string is length 1, then that number only appears once and the value of that string tells me the cell. Thus I have the string variable pulling double duty by using its length and value.

PieceOfMind · Oct 30, 2010

Actually, your solution above already covers what my code was capable of.

By the way, instead of using strings, I just used another dimension of the array and stored binary values (1 for a value that's possible, 0 for one that's eliminated). You could even have a fourth dimension that stores one of the 3 values - solved, unsolved, provided by puzzle - for each cell.

ruff_hi · Oct 30, 2010

I did write a vba solver that had multi-dimensions but it got to hard to remember what dimension did what. This version focuses on classes (I am trying to improve my knowledge and handling of classes) which means (I think) that my code can be more focused and I don't have to try and remember all of the dimension stuff

.

Oh - let me know if you want me to post my code here in spoilers instead of forcing you to d/l my excel file.

EmperorFool · Oct 30, 2010

A few notes since you've gone pretty far already.

Block Elimination

In my solver, this was a simple consequence of setting a Cell to a value. Each Cell knew the three Blocks to which it belonged. Cell.setValue() looked like this:

Code:

Cell.setValue(int value) {
    this.value = value;
    for (Block block : this.blocks) {
        block.removePossible(value);
    }
}

Block.removePossible(int value) {
    for (Cell cell : this.cells) {
        cell.removePossible(value);
    }
}

As you can see, setting the value in a Cell caused it to be removed from the list of possibles for every Cell in every Block to which the first Cell belonged, including itself. There's a further optimization you can do here, but I'll leave that for you to mull over.

Group Elimination

In my solution, I used Java's Set to track the possibles. It represents a mathematical set with union and intersection operations. VBA might have something similar you could use. Another thing that might help would be to track how many Cells in each Block have each value as a possible. This would be another array of nine integers, each starting with 9 since every Cell can contain every number before any values are set.

In your example above, the center Block would have these values:

Code:

4 2 0 0 0 6 4 2 4

Four cells can have a 1; two can have a 2; none can have 3, 4, or 5 since they are solved, etc. Maybe you can combine this with the above information to detect groups. You could further track which cells can contain which numbers (the reverse of the possible values sets) in a block.

Another option is to store the possibles using binary operations by treating each number/position (1..9 translated to 0..8) as a bit position. You could store these in 16-bit numbers which VBA must support. I don't know if VBA has bit operations (AND, OR, XOR), but you can perform union, intersection, and subtraction using them. This falls more into optimization, but if VBA doesn't have a Set class and you don't want to make one, they would suffice.

That being said, writing a simple Set class would be a pretty cool learning experience.

ruff_hi · Oct 30, 2010

EmperorFool said:
Block Elimination
In my solver, this was a simple consequence of setting a Cell to a value. Each Cell knew the three Blocks to which it belonged.

I don't have to do this. My Sudoku class is the owner of each cell (all 81 of them) and the individual cells keep track of what is possible for them. The region class borrows their 9 cells (by reference) and runs the tests (the regions do the heavy lifting re eliminations, etc) against its (borrowed) 9 cells, updating the cell information which is magically transported back to the sudoku's cells (the regions use a pointer to its 9 cells - vba doesn't have pointers but if I am understanding the concept correctly, this is what I have set up).

That said, my approach will need to be modified to catch the 'blocking' situation I've mentioned above. I'm thinking of creating another class (Ring?) that contains cells for situations where you know a number is within that ring (the rings cells?). Then if a region contains all of the cells within that ring, then I can eliminate the forced number from the non-ring cells.

I'd have to create some code to add and destroy rings as the process of solving the puzzle continues. My classes to date have been static (81 cells, 27 regions, etc). That would be a good learning exercise.

Code:
Group Elimination
In my solution, I used Java's Set to track the possibles. It represents a mathematical set with union and intersection operations. VBA might have something similar you could use. Another thing that might help would be to track how many Cells in each Block have each value as a possible. This would be another array of nine integers, each starting with 9 since every Cell can contain every number before any values are set.

In your example above, the center Block would have these values:

Code:

4 2 0 0 0 6 4 2 4

Four cells can have a 1; two can have a 2; none can have 3, 4, or 5 since they are solved, etc. Maybe you can combine this with the above information to detect groups. You could further track which cells can contain which numbers (the reverse of the possible values sets) in a block.

Another option is to store the possibles using binary operations by treating each number/position (1..9 translated to 0..8) as a bit position. You could store these in 16-bit numbers which VBA must support. I don't know if VBA has bit operations (AND, OR, XOR), but you can perform union, intersection, and subtraction using them. This falls more into optimization, but if VBA doesn't have a Set class and you don't want to make one, they would suffice.

That being said, writing a simple Set class would be a pretty cool learning experience.

This is a pretty good idea ... the whole idea of union, intersection, etc. I am pretty sure that vba doesn't have the classes that you described ... might see if anyone has written some for me

.

I've been thinking about this and realized that my current hidden single (starting to use PoM's suggested terminology - this is what I called 'unique solution' above) solution is a special case of the hidden pairs (the 28 I reference above). Its conceivable to write code that looks for hidden 'n's and use that with n=1.

EmperorFool · Oct 30, 2010

I'm not sure I understood your thing about rings. Each region (to use your terminology) contains nine cells, and each cell belongs to three regions. This relationship is static: you create it when you build the board. Whenever you assign a value to a cell, by necessity that number cannot appear in any other cell in the three regions to which the first cell belongs.

Now, you can handle this by setting the value and making a second pass over the board to look for any cell that belongs to a region that contains a cell that has a value, and remove that value from the possibles of the first cell . . . or you could just eliminate the value from the possibles of related cells when the value is first set. I believe the logic will be the same. The difference is that this method requires running a pass for every number in every cell every "turn." Doing the elimination up front does the work only when it can possibly have any results: when a value is set.

Neither method is more correct--I just didn't get yours unless you meant what I just said above--they just have different paths. In my solver, the focus was more on keeping board state current. I think yours is focused more on having separate strategies that you run through, much like that wiki site you linked (very cool). It looks like their code is probably available in Javascript if you care to take a look later.

ruff_hi · Oct 30, 2010

EmperorFool said:
Now, you can handle this by setting the value and making a second pass over the board to look for any cell that belongs to a region that contains a cell that has a value, and remove that value from the possibles of the first cell

I don't have to make a second pass when I set the value of a cell.

I've created a variable (pSudoku) using my Sudoku class. To this variable, I have added 81 cell variables (using my cell class) and 27 region variables (using my region variables). Each region also contains 9 cells (cell class). I have set the region cells to point back to the appropriate cell variable. Thus if I do this ...

Code:

pSudoku.cell(1).value = 1

... then I have also set the following to '1'

Code:

pSudoku.region(1).cell(1).value   (ie the value of the first cell in the first row)
pSudoku.region(10).cell(1).value   (ie the value of the first cell in the first column)
pSudoku.region(19).cell(1).value   (ie the value of the first cell in the first region)

... and visa-versa.

Spoiler sudoku class :

EmperorFool said:
I'm not sure I understood your thing about rings.

ruff_hi said:

If you look at the middle left block, you can see that '7' can only appear in 3 cells. I am thinking of adding code to create a ring-fence (or sub region) around those 3 cells. Then when I am processing a different region, I can check if any other region contains all the cells of any of the rings that I have created (in this example, the 5th row) and thus I can remove '7' from any cell not in the ring-fence.

I guess the code would go something like this ...

loop over all of the regions
build rings for each unsolved number within a region (ie which cells could the number be in)
delete the ring if all of the cells are not fully contained with 2 regions - so, only keep rings that satisfy any of the following:
- all cells have same region and row
- all cells have same region and column
- all cells have same row and column (this one will be a little difficult)
I guess at this stage I should attach the affected regions to the ring
loop over all rings, removing the number from cells in the affected region that are outside the ring

Does that make any sense?

PieceOfMind · Oct 30, 2010

ruff_hi said:
I did write a vba solver that had multi-dimensions but it got to hard to remember what dimension did what. This version focuses on classes (I am trying to improve my knowledge and handling of classes) which means (I think) that my code can be more focused and I don't have to try and remember all of the dimension stuff .

Oh - let me know if you want me to post my code here in spoilers instead of forcing you to d/l my excel file.

Spoiler code would be great.

ruff_hi · Oct 30, 2010

fine - see spoiler in above post for sudoku class

Spoiler cell class :

Spoiler region class :

ruff_hi · Oct 30, 2010

and the code for interfacing with the excel front end ... you'll really need to look at the spreadsheet to understand some of the navigation items as well as how the macros are setting up the class variables. The linkage between cells and regions is also controlled by the stuff in the worksheets.

Spoiler solve button :

Spoiler solve complete button :

Spoiler roll back button :

Spoiler clear button :

Spoiler sudoku initialize :

Spoiler load sudoku puzzle :

Spoiler solve sudoku :

Spoiler update worksheet :

Spoiler excel utilitites :

EmperorFool · Oct 30, 2010

I'm talking about removing the value as a possibility from other cells in the regions to which the first cell belongs.

For example, when you set cell C2 (A..J are rows, 1..9 are columns, starting at the top-left corner) to 6, you can remove 6 as a possible value for all cells in row C, column 2, and box 1 (top-left box). In my solver, the cell would tell its three regions to remove 6 as a possibility, and those regions would in turn tell each cell they held to remove 6 as a possibility.

Is this happening in your solver?

ruff_hi · Oct 31, 2010

EmperorFool said:
Is this happening in your solver?

Ahh - ok. Yes and No. I don't do it when the value of a cell is set but I do do it each 'pass' as part of the 'simpleelimination' for each region ...

part of the 'solve' execution said:

Code:

Private Sub SolveSudoku()
Dim r As Integer

For r = 1 To pSudoku.RegionCount
    With pSudoku.Region(r)
        If Range("xSimpleElimination").Value Then .SimpleElimination
        If Range("xSinglePossibility").Value Then .SinglePossibility
        If Range("xUniqueValue").Value Then .UniqueValue
    End With
Next r
End Sub

method from the region class said:

Code:

Public Sub SimpleElimination()
Dim c1 As Integer
Dim c2 As Integer
Dim cV As Integer

For c1 = LBound(m_oCells) To UBound(m_oCells)
    If m_oCells(c1).isSolved Then
        cV = m_oCells(c1).Value
        For c2 = LBound(m_oCells) To UBound(m_oCells)
            If c1 <> c2 Then m_oCells(c2).Possible(cV) = False
        Next c2
    End If
Next c1
End Sub

Sudoku Solver

Live 4ever! Or die trying

Live 4ever! Or die trying

Deity

Live 4ever! Or die trying

Attachments

Drill IV Defender

Live 4ever! Or die trying

Attachments

Live 4ever! Or die trying

Live 4ever! Or die trying

Live 4ever! Or die trying

Drill IV Defender

Live 4ever! Or die trying

Deity

Live 4ever! Or die trying

Deity

Live 4ever! Or die trying

Drill IV Defender

Live 4ever! Or die trying

Live 4ever! Or die trying

Deity

Live 4ever! Or die trying

Similar threads