what do we know mathematically about soduko

[sao123]

I was solving a soduko puzzle last night and it got me thinking...

Do we know if there is a way to prove each puzzle is guranteed exactly one unique solution?

It seems to solve this we would need to know a lot of variables.

Firstly we would probably have to computer the exact number of all possible valid solutions.

I was thinking it would be easiest to estimate (possibly find exactly) by first starting with a 10 digit seed. A seed would be valid if and only if, it is exactly 10 digits and has the all 10 digits appear exactly once. Then developing a tree of all possible valid solutions for that seed. Then we could multiply that by the number of all possible seeds.

From this tree we could hopefully determine the minimum number of starter numbers needed to ensure that this puzzle selects a unique valid solution from the tree.

Im sure the details are far more grueling or possibly easier if you can do it with some matrix operations (which i suck at terribly)... but has anyone given this any thought or even made an attempt?

 

[sdifox]

this might help

http://www.vsj.co.uk/articles/display.asp?id=540

 

[imported_inspire]

I've thought about it before, yeah - the first time I tried Su Doku, I thought to myself, "I bet I could write and iterative proggy using low-level rules and zip right through this." Turns out that depending on the seed values, that can be either very easy, or very hard.

Likewise, the question of whether there exists a unique solution would be one that depended on the seed values. N-dimensional matrices would certainly help. Trees sound useful, too.

What would be more puzzling is the maximum ratio of open tiles to seed tiles necessary to obtain a unique solution for each tileset (board size). I wonder if such a ratio is fixed or how it behaves.

Almost certainly this sounds like number theory and abstract algebra, but modeling usually gives us a good idea of what's going on. Then, the abstract layer can be proven.

I'll have to read that article sometime. I'm willing to make an attempt at writing a program or digging deeper into this if you guys don't mind brainstorming algorithms. I can code C++ and JAVA and IML in SAS - I deal a lot with matrix operations - I'm studying for an M.S. in Biostatistics.

 

[videogames101]

You just use the start numbers and put every possible number in each box and it narrows itself until it's done. Takes longer then solving it, lol.

 

[sao123]

Originally posted by: inspire
I've thought about it before, yeah - the first time I tried Su Doku, I thought to myself, "I bet I could write and iterative proggy using low-level rules and zip right through this." Turns out that depending on the seed values, that can be either very easy, or very hard.

Likewise, the question of whether there exists a unique solution would be one that depended on the seed values. N-dimensional matrices would certainly help. Trees sound useful, too.

What would be more puzzling is the maximum ratio of open tiles to seed tiles necessary to obtain a unique solution for each tileset (board size). I wonder if such a ratio is fixed or how it behaves.

Almost certainly this sounds like number theory and abstract algebra, but modeling usually gives us a good idea of what's going on. Then, the abstract layer can be proven.

I'll have to read that article sometime. I'm willing to make an attempt at writing a program or digging deeper into this if you guys don't mind brainstorming algorithms. I can code C++ and JAVA and IML in SAS - I deal a lot with matrix operations - I'm studying for an M.S. in Biostatistics.

I theorize that using any given seed, that the tree shape and depth would be pretty consistent without dependency to the choice of seed. If this is true, there should be a constant minimum for the ratio you speak of. I think this shall be a worthy effort.


To begin I think ill code an app which will compute and list all possible seeds numbers in the range 123456789 to 987654321, of which there should be exactly 9! valid seeds.

 

[BrownTown]

making a program to slove soduko should be pretty trivial, the aproach is entirely algorithmic, would probably take only an hour or 2 to nail down a functional algorithm to solve Sudukos in a reasonable amount of time.

 

[DrPizza]

I've pondered whether or not there is a "simple" way to solve Sudoku puzzles.. Seeing the phrases "unique solution" and "matrix" near each other should get any math person started thinking about linear algebra... I've just never had the time to play around with it.

 

[Laputa]

Using square matrix and linear algebra method of approach will be the right path, but you can also use a quicker approach since all 9 of the 9 squares must counter balance each other. It's like selecting 9 consective numbers and put them into a 3x3 square and each number can only take place at one spot. However, how you balance them so that the 3 numbers will add up equally vertically and horizontally is what really matters. If you use boolean algebra and combine it with linear algebra, the process will become much simpler since that single number can be legally place there or you can't.

 

[BrownTown]

you really don't need any math simply so solve a suduko, jsut tell the computer to run the same algorithm you do when you solve one. There are simple rules which govern this game, tell the computer to follow them until it reaches a point where it would be forced to guess, then simple push all the guesses onto a stack and solve them like they were origional puzzles. If you are using a resonable starting matrix which is designed so that you don't ahve to make 10 guesses and there are 1000 possible solutions then the computation time shouldn't be bad.

Perhaps this does not solve for every single one imaginable, but it would deffinitely be able to get anything you would find in a suduko book. (Obviuosly if you tries to run it on a blank matrix it would simplly generate EVERY single possible solution which would take a very large amount of time)

 

[CycloWizard]

I noticed that the beta version of MS Office 2007 has a Sudoku solver functionality or example...

I would think it's pretty trivial to solve such a puzzle using a computer. I've never really done Sudoku, but I think I have a general idea of the rules and how it works. I think that each number (1-9) can only appear once per row, once per column, and once per 3x3 sub-matrix. Thus, perhaps the simplest (albeit not the most efficient approach) would be to substitute numbers until the sum of each row/column is equal to 45 (1+2+3+4+5+6+7+8+9) with the constraint on the digits in the 3x3 matrix. A computer could surely solve it faster than a person using this method, though I'm sure there's a more efficient algorithm out there.

The minimum number of seeded numbers for a unique solution would be the number required to ensure that the rank of the matrix is 9. I'd have to do some thinking to figure out what this minimum would be, though it would probably depend on the locations and values of the seeds.

 

[sao123]

maybe someone misunderstood me...


Im not looking to solve soduko puzzles... I know how to do that quite effectively.

I want to know the math theory behind them so I can create them based on a random seed, and be sure i give enough clues to ensure that the puzzle I create has exactly one unique solvable solution.

 

[CTho9305]

http://www.americanscientist.org/template/AssetDetail/assetid/48550?&print=yes
http://www.sciam.com/article.cfm?chanID...ID=000C6E43-D385-146C-938583414B7F0000

 

[BassBomb]

UBERMATRICES!!!

 

[DrPizza]

Yes, I know I could program a computer to use the typical algorithm that most people use when solving these puzzles... what I'm more interested in, is a question similar to the OP's - is there a more elegant method of solving these?

 

[Born2bwire]

Originally posted by: DrPizza
Yes, I know I could program a computer to use the typical algorithm that most people use when solving these puzzles... what I'm more interested in, is a question similar to the OP's - is there a more elegant method of solving these?

/me steals idea.

This sounds like something I could get funding for! To DARPA, quick!

 

[MrDudeMan]

Originally posted by: DrPizza
Yes, I know I could program a computer to use the typical algorithm that most people use when solving these puzzles... what I'm more interested in, is a question similar to the OP's - is there a more elegant method of solving these?

yes - there are several techniques and several webpages with better information, but that is just an example. i used the x-wing technique today as a matter of fact.

 

[DrPizza]

By more elegant, I was referring to a method that didn't involve steps such as what you linked to...
I'm looking for a more mathematical solution.

The only thought I had put into it was to simply assign a relatively prime number to each of the digits 1-9. Then, I stopped thinking about it. Thus, when you're thinking, "well, this column has all these numbers, this square has all these numbers, this row has all these numbers..."
I'm employing some process where I'm multiplying and dividing... if I come up with 35, then I know there are two possibilities: 5 or 7. I'd think that using some process or combination of processes from linear algebra, eventually I or someone better at math than I am, could come up with a very simple algorithm that didn't rely on a lot of recursive steps.

 

[BrownTown]

EDIT: im confused again, but anyways, use 2^x to represent the nubmers, not prime numbers.

 

[AyashiKaibutsu]

I wrote a program a few years ago that solved this. Basicly, I made a 3 dimensional array with the first two being the game board and the third being the possible solutions for each square that didn't break the rules. Then I had an algorithm that went through and filled in the results.

 

[eLiu]

My understanding is that solving Sudoku problems is NP-complete and hence the only known solutions are brute force & some ugly polynomial time. It also means that if you find the "elegant" solution to Sudoku, you'll be damn famous b/c you'll have solved ALL NP problems

Edit: To clarify a little, I think this is the simplest example of an NP-complete problem: given a set of integers, can you find a subset that sums to some value X? There's no obvious, fast way to do this (and as far as theoretical CS/math know, there's no fast way to do this period.)

Now you're going to say... who cares about polynomial time? It's a 9x9 grid!
Well you can "generalize" sudoku and make much bigger grids

It's trivial to write a solver that works (but not trivial to write an efficient one... see above); I think it took me all of an hour... a friend of mine did it even faster for some kind of CS contest. But again all the algorithms here are brute force with some minor tricks applied, which are not the kind of 'elegant' solutions DrPizza is wondering about. So yeah... the NP-completeness means that the best method we know about is to try every possible solution. Granted there are some small tricks to speed this up somewhat, but ultimately... nothing special.

As for uniqueness... I think they found that 4 given #s short of a full grid is the maximum number you can specify and still not have a unique solution. But the minimum # of specfied #s without a unique solution is still unknown--empirically it's in the high teens.

If you wiki for sudoku or mathematics of sudoku or something like that, you'll find a wealth of information that I won't bother repeating any further.

 

[imported_inspire]

Originally posted by: DrPizza
By more elegant, I was referring to a method that didn't involve steps such as what you linked to...
I'm looking for a more mathematical solution.

The only thought I had put into it was to simply assign a relatively prime number to each of the digits 1-9. Then, I stopped thinking about it. Thus, when you're thinking, "well, this column has all these numbers, this square has all these numbers, this row has all these numbers..."
I'm employing some process where I'm multiplying and dividing... if I come up with 35, then I know there are two possibilities: 5 or 7. I'd think that using some process or combination of processes from linear algebra, eventually I or someone better at math than I am, could come up with a very simple algorithm that didn't rely on a lot of recursive steps.

I'm thinking 'Cyclic Groups' right now. I'm not sure how that works out, but that's my gut instinct. I haven't had much time to think about it, but I'm sure that if we put our heads together, we can figure something out.

 

[gbuskirk]

This question may be along the lines the OP intended: There are many symmetries in the Sudoku grid, and the set of 9 symbols can be shuffled. Suppose we have an algorithm to normalize any minimal solvable puzzle to a unique representative for its equivalence group. How many unique normalized minimal solvable Sudoku puzzles are there?

 

[imported_inspire]

I would think we'd have as many normalized unique solvable Sudoku puzzles as we have normalized unique solutions, but that would require more than a warm fuzzy to proove. But it does seem like it might be trivial...

 

[Thraxen]

I have a question for the math whizzes in here. What is the minimum number of numbers that can be provided at the start in a Sudoku puzzle that will still ensure only a single possible solution? That's something I've wondered about before but have no real idea how to solve such a question myself.

 

[sao123]

Originally posted by: Thraxen
I have a question for the math whizzes in here. What is the minimum number of numbers that can't be provided at the start in a Sudoku puzzle that will still ensure only a single possible solution? That's something I've wondered about before but have no real idea how to solve such a question myself.

that was part of my original question, in order to solve it, it seems we must examine a set of solutions to determine a geometric pattern.