• (2 Pages)
• 1
• 2

## 19 Replies - 3494 Views - Last Post: 02 July 2013 - 07:40 PM

### #1 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12316
• Posts: 45,416
• Joined: 27-December 08

Posted 01 July 2013 - 08:54 AM

I came across an interesting article on Sudoku as Graphs, with an application of graph coloring. I haven't studied the Sudoku problem extensively enough to have a good feel for how to solve it. As a graph theorist though, this solution tickled my fancy.

What strategies do you all use when solving Sudoku puzzles algorithmically? What are your thoughts on this problem?

Quote

Enumerate the 81 cells of the Sudoku board with numbers from 81. Then the graph associated with a Sudoku puzzle consists of 81 vertices (one for each cell of the board), together with edges as follows: two vertices are connected by an edge if the cells that they correspond to are in the same column, row or 3x3 box. We have thus represented the Sudoku grid as a graph. With 81 vertices and several hundred edges it would be a big graph if one wanted to draw it, so let us just think about it without attempting to produce a graphical representation. What about the numbers in the cells of the Sudoku puzzle, how do we represent those? Assign each number from 1 to 9 a color. Now color the vertices corresponding to cell that contains a given number in the color of the number.

It is now easy to see that completing a Sudoku puzzle without vioating the Sudoku condition is equivalent to coloring the vertices of the corresponding graph while ensuring that no two adjacent vertices have the same color.

Is This A Good Question/Topic? 0

## Replies To: Sudoku- Your Strategies

### #2 lordofduct

• I'm a cheeseburger

Reputation: 2668
• Posts: 4,786
• Joined: 24-September 10

Posted 01 July 2013 - 09:55 AM

When you say "solve the puzzles algorithmically", are you being redundant, or are you limiting it to some category. In the ladder case I'm not sure what that category would be. I personally always solve sudoku puzzles algorithmically... what other option is there but to just throw numbers in there and get it wrong nearly every time?

I'm sincerely wondering about this as the question. I don't know if you meant what strategies I use when writing code to solve a generic puzzle, as opposed to how I play the game when sitting on the toilet.

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12316
• Posts: 45,416
• Joined: 27-December 08

Posted 01 July 2013 - 09:58 AM

I was aiming it at a more Computer Science-y approach. More to the point- if you had to write a program to solve Sudoku puzzles, what approach(es) would you use (hopefully that are better than the BFI method)?

### #4 lordofduct

• I'm a cheeseburger

Reputation: 2668
• Posts: 4,786
• Joined: 24-September 10

Posted 01 July 2013 - 09:59 AM

Ok, so you were talking in the context of computer programming.

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12316
• Posts: 45,416
• Joined: 27-December 08

Posted 01 July 2013 - 10:02 AM

You could abstract it out more into the realm of math or computer science if you preferred. Something along those lines though!

### #6 lordofduct

• I'm a cheeseburger

Reputation: 2668
• Posts: 4,786
• Joined: 24-September 10

Posted 01 July 2013 - 10:03 AM

I've never personally approached solving it from a computer science perspective.

As a first rough start, as I like to go it how I go at things in the real world for the fun of it. I'd start by applying my real world algorithms to it. Making the computer emulate me as a player.

I mostly would take this approach because I like making video-games, and having the computer emulate how a player would do it is kind of important to me so that I can have interesting AI to play against in a game.

I'll have to think about how I'd approach it from a computer science perspective though...

### #7 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12316
• Posts: 45,416
• Joined: 27-December 08

Posted 01 July 2013 - 10:06 AM

Quote

As a first rough start, as I like to go it how I go at things in the real world for the fun of it. I'd start by applying my real world algorithms to it. Making the computer emulate me as a player.

If they work in the real world, that's usually a good place to start. I'd be interested in hearing more about how you go about solving these puzzles by hand!

### #8 andrewsw

• RequestedRangeNotSatisfiable

Reputation: 6552
• Posts: 26,565
• Joined: 12-December 12

Posted 01 July 2013 - 10:35 AM

I don't know if this Excel sudoku solver is of interest.

I used to do Sudoku a lot, but haven't for ages. I eventually preferred Killer Sudoku. I suppose these would be easier to break-down, algorithmically; kinda like solving (3D) simultaneous equations

This post has been edited by andrewsw: 01 July 2013 - 10:37 AM

### #9 baavgai

• Dreaming Coder

Reputation: 7183
• Posts: 14,969
• Joined: 16-October 07

Posted 01 July 2013 - 11:27 AM

In an empty sudoku, each cell can contain the entire domain {1..9}.

As you add a value to a cell, you remove that value from all other cells sharing row, column, or box.

On in each iteration, you look at empty cells. If their domain is also empty, then the board is invalid. You then look for any cells with a domain size one. That will be your next pick. When only empty cells with domains of greater than one cardinality exist, you have to guess. This would be a branch in your solver.

### #10 lordofduct

• I'm a cheeseburger

Reputation: 2668
• Posts: 4,786
• Joined: 24-September 10

Posted 01 July 2013 - 11:30 AM

I've never had to guess in sudoku.

I've always been able to reduce by cancelling.

### #11 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12316
• Posts: 45,416
• Joined: 27-December 08

Posted 01 July 2013 - 11:31 AM

baavgai- Have you examined the Traveling Salesman problem before? Your solution seems to emulate an adapted Kruskal approach for finding Hamiltonian circuits on a graph. I like it! It also sounds a lot like the graph coloring problem described in that article!

### #12 lordofduct

• I'm a cheeseburger

Reputation: 2668
• Posts: 4,786
• Joined: 24-September 10

Posted 01 July 2013 - 11:31 AM

If I have to guess, I don't, and instead rethink my strategies and try to adapt them to this new puzzle formation that I just met.

### #13 Draps

Reputation: 34
• Posts: 103
• Joined: 20-November 10

Posted 01 July 2013 - 11:58 AM

I think what baavgai meant by guessing is not what you would do in reality, however using a computer to solve the Sudoku puzzle it would be more efficient to take the possibilities that can be easily checked. (direct rows and columns) Then when you get to a point that has no direct clues, Guess rather than looking up adjacent 3x3's in the same row (and column) and checking the number to see if its valid for the first 3x3. You would guess and if you hit a snag two or three iterations down the branch, backtrack and try again.

### #14 andrewsw

• RequestedRangeNotSatisfiable

Reputation: 6552
• Posts: 26,565
• Joined: 12-December 12

Posted 01 July 2013 - 01:03 PM

A computer solution could, I guess, do something similar to what I might do, which is to fill-in all the known values. With a computer, it can pass through ALL the numbers 1..9 (eliminating extant values, of course), for ALL empty cells, each time checking the row, column and square. [What would we call this approach? Apart from expensive. Well, it is not that expensive these days ]

I believe this is what baavgai also referred to:

Quote

You then look for any cells with a domain size one.

As mere mortals, though, we don't do this: we scan the row/column and square, to narrow down to candidate values. We don't check every value in the domain. Can computers replicate this behaviour? Maybe with AI (about which I know nothing..).

Off-topic: It is this visual aspect that computers lack. After sudoko-ing for a while, we begin to recognise patterns; that is, to quickly spot which number is missing from a zone. This zone is an understanding of the 'square-row-column' as a single entity, rather than three separate objects.

This post has been edited by andrewsw: 01 July 2013 - 01:14 PM

### #15 lordofduct

• I'm a cheeseburger

Reputation: 2668
• Posts: 4,786
• Joined: 24-September 10