2005-09-11
Sudoku
Last weeks I spent some time with this popular number puzzle, Sudoku. For those who have never heard of it, have a look at the Wikipedia. I don’t really like to spent my time on puzzles with a known solution. I prefer puzzles that have not yet been solved. But the Sudoku is interesting, since it contains many unsolved questions. I was not interested in a particular solution, but the general solution of Sudoku’s. I had the following questions:
I also found an answer on the third question. I turns out to be 17. But again, there is no mathematical proof. I found no answer for the fourth question. Unfortunately I’m not that good in mathematics (I’m a physicist) to help the world with some nice solutions on the questions.
What about the first question? I do not have a complete solution for every Sudoku. But I found and implemented several rules. I started with a small program to solve the Sudoku of the daily newspaper. It contained one rule:
1. A number may occur only once at a row, column and block (3x3 cells).
This rule reduces the number of options for a cell. With the first Sudoku I tried this rule was enough to solve it. I was quite disappointed that the puzzle was that simple. The next day the puzzle was more difficult. I had to add a second rule.
2. A number must occur one at a row, column and block.
This rule was a great help. About 95% of the puzzles in the newspapers can be solved with these two rules. The figure below shows the solution process. The white squares represent the remaining options in a cell. A square in upper-left corner represents a 1, next to it is 2 and upper-right is 3. Number 4 is underneat the 1, 5 is in the center of the cell, etc.. The black squares indicate that that option is the only remaining option for the number in a row, column or block.
A few days later I found some more difficult puzzles. And I found some rules to solve these.
3. If the remaining options for a number in a block are on one row/column, that number must be in that block on that row/column. The options for that number can be removed from the other blocks of the row/column. In the figure below this is depicted by the cyan colored options for number 6 on row 7. The red options can be removed.
4. Rule 3 can also be reversed: If the remaining options for a number in a row/column are in one block, the options for that number can be removed from the other rows/columns of the block. This is shown in the south block. Number eight must be on column D, and can thus not be in cell F9.
These 4 rules were quite easy to implement on the computer. If I had to write a complete automatic solver, then I would start a trial and error from this point. The number of options has been dramatically reduced and only a few options have to be tried. I found some other rules to solve the Sudoku manually, but these rules are computationally quite expensive. But our brain, especially visual cortex, is well equipped to recognize the patterns. I found a good description of those solution rules on this very good Sudoku site. My last two rules are:
5. Disjoint chain: if a set of two or three numbers occur only in two or three cells (respectively) then these numbers must occur in these cells and other options can be removed. E.g. the dark green 2 and 3 in the east block are a disjoint chain. The yellow 8 can thus be removed, leaving a single (dark blue) 8 in cell G7. The light green 1, 5 and 8 are also a disjoint chain (on column I).
6. Disjoint subset: if 2 (or 3) cells on a row/column or block contain the same subset of 2 (or 3) numbers, then these numbers must occur in those cells and can be removed from the other cells.
(I do not have an example of this rule.)
That was enough about Sudoku for me. Any questions?
- Is there a logical solution method for all Sudoku’s? I mean, is there a set of rules to find the numbers without trial and error?
- How many Sudoku solutions are there?
- What is the minimal number of givens needed to have one unique solution?
- Can I create a Sudoku grid in a mathematical way, i.e. (again) without trial and error.
I also found an answer on the third question. I turns out to be 17. But again, there is no mathematical proof. I found no answer for the fourth question. Unfortunately I’m not that good in mathematics (I’m a physicist) to help the world with some nice solutions on the questions.
What about the first question? I do not have a complete solution for every Sudoku. But I found and implemented several rules. I started with a small program to solve the Sudoku of the daily newspaper. It contained one rule:
1. A number may occur only once at a row, column and block (3x3 cells).
This rule reduces the number of options for a cell. With the first Sudoku I tried this rule was enough to solve it. I was quite disappointed that the puzzle was that simple. The next day the puzzle was more difficult. I had to add a second rule.
2. A number must occur one at a row, column and block.
This rule was a great help. About 95% of the puzzles in the newspapers can be solved with these two rules. The figure below shows the solution process. The white squares represent the remaining options in a cell. A square in upper-left corner represents a 1, next to it is 2 and upper-right is 3. Number 4 is underneat the 1, 5 is in the center of the cell, etc.. The black squares indicate that that option is the only remaining option for the number in a row, column or block.
A few days later I found some more difficult puzzles. And I found some rules to solve these.
3. If the remaining options for a number in a block are on one row/column, that number must be in that block on that row/column. The options for that number can be removed from the other blocks of the row/column. In the figure below this is depicted by the cyan colored options for number 6 on row 7. The red options can be removed.
4. Rule 3 can also be reversed: If the remaining options for a number in a row/column are in one block, the options for that number can be removed from the other rows/columns of the block. This is shown in the south block. Number eight must be on column D, and can thus not be in cell F9.
These 4 rules were quite easy to implement on the computer. If I had to write a complete automatic solver, then I would start a trial and error from this point. The number of options has been dramatically reduced and only a few options have to be tried. I found some other rules to solve the Sudoku manually, but these rules are computationally quite expensive. But our brain, especially visual cortex, is well equipped to recognize the patterns. I found a good description of those solution rules on this very good Sudoku site. My last two rules are:
5. Disjoint chain: if a set of two or three numbers occur only in two or three cells (respectively) then these numbers must occur in these cells and other options can be removed. E.g. the dark green 2 and 3 in the east block are a disjoint chain. The yellow 8 can thus be removed, leaving a single (dark blue) 8 in cell G7. The light green 1, 5 and 8 are also a disjoint chain (on column I).
6. Disjoint subset: if 2 (or 3) cells on a row/column or block contain the same subset of 2 (or 3) numbers, then these numbers must occur in those cells and can be removed from the other cells.
(I do not have an example of this rule.)
That was enough about Sudoku for me. Any questions?
# posted by Sander @ 15:56 
Comments:
Post a Comment
<< Home
The question is: why spend so much time on puzzles when you could have been dancing salsa? ;)
but i'm impressed: you definitely have a very analytical brain. you should chat with some of my old fellow students in cognitive science, they like these things..
but i'm impressed: you definitely have a very analytical brain. you should chat with some of my old fellow students in cognitive science, they like these things..
mmmm, I had no intention to impress. I just wanted to give an impression of what's going on in analytical mind. Salsa makes it slumber, but sometimes it gets restless. I couldn't stop it. Soon my legs will get restless and want to spend time on the dancing floor. I hope they will be stable after the sailing I did last week.
today I did my first sudoku.
quite nice kind of puzzle.
here are some of my 'psychological' experiences (in contrast to the analytical mind of sander)
but first:
only now i understand the semantics of what you were trying to convey in this posting. what i still do not understand is your explanation of the last two rules and the color codings in your picture. You say "the blue 8" and I see a blue dot but I do not see an 8 so I just don't understand what you say in that section.
anyway,
if i understand you correctly, rule 1 and 2 are simply 'the rules of the game', i.e., the givens. (of course, for a computer a game-rule is the same as a game-strategy, not? but for me, psychologically, the first two rules did not help me to solve the problem, they defined it)
the third/fourth rule i immediately chose as my first strategy. start with a row or column or square that looks promising. fill in all the options left in any of the blank cells, check on columns, squares and rows whether these are really the options and hope that somewhere a single number will be left as the only option. then repeat this proces on some other row or on some other column or square.
the computer does this automatically for all cells at the same time, right?
(some AI questions: what if you implemented a program that started with filling in the sudoku grid randomly and only after that started to 'resolve' rule-breaking conflicts by swithing numbers between cells, in such a way that the resulting grid should always contain less conflicts than the previous one? or would this be nonsense concerning the nature of the problem? this would be an example of hill-climbing, right? what is the chance of running in to a 'local minimum' using that strategy? perhaps we could use 'simulated annealing' to resolve that? in any case: would it be faster or slower than 'full search'? could one upscale this strategy to sudoku grids of, say, 200 rows/columns? and when does full search become really cumbersome: how big can the sudokugrid be?)
the last two rules I didn't know, but I had a feeling that 'there was something with these situations'. I guess this is just human intuition at work: whenever we see some pattern (in this case a symmetry: two cells with the same two numbers in it) we know (assume) that it has some meaning. the dissonant element affords action, so the odd number should go. I can already agree with this rule even on gut-feeling, even if I do not understand (grasp) completely why this should be logically so.
my fellow traveller in the train has another strategy. she goes by the number. first she checks all cells on the possibility of ones, then on two's, then on three's and so on. whenever any number in any cell is directly singled out, it is written there. the proces repeats. she does it first on rows, then on columns. only in the later stages she includes checking on the squares. she cannot logically validate this strategy but she has the confidence of the expert in her voice while explaining it. would you consider this strategy to be of any sense?
quite nice kind of puzzle.
here are some of my 'psychological' experiences (in contrast to the analytical mind of sander)
but first:
only now i understand the semantics of what you were trying to convey in this posting. what i still do not understand is your explanation of the last two rules and the color codings in your picture. You say "the blue 8" and I see a blue dot but I do not see an 8 so I just don't understand what you say in that section.
anyway,
if i understand you correctly, rule 1 and 2 are simply 'the rules of the game', i.e., the givens. (of course, for a computer a game-rule is the same as a game-strategy, not? but for me, psychologically, the first two rules did not help me to solve the problem, they defined it)
the third/fourth rule i immediately chose as my first strategy. start with a row or column or square that looks promising. fill in all the options left in any of the blank cells, check on columns, squares and rows whether these are really the options and hope that somewhere a single number will be left as the only option. then repeat this proces on some other row or on some other column or square.
the computer does this automatically for all cells at the same time, right?
(some AI questions: what if you implemented a program that started with filling in the sudoku grid randomly and only after that started to 'resolve' rule-breaking conflicts by swithing numbers between cells, in such a way that the resulting grid should always contain less conflicts than the previous one? or would this be nonsense concerning the nature of the problem? this would be an example of hill-climbing, right? what is the chance of running in to a 'local minimum' using that strategy? perhaps we could use 'simulated annealing' to resolve that? in any case: would it be faster or slower than 'full search'? could one upscale this strategy to sudoku grids of, say, 200 rows/columns? and when does full search become really cumbersome: how big can the sudokugrid be?)
the last two rules I didn't know, but I had a feeling that 'there was something with these situations'. I guess this is just human intuition at work: whenever we see some pattern (in this case a symmetry: two cells with the same two numbers in it) we know (assume) that it has some meaning. the dissonant element affords action, so the odd number should go. I can already agree with this rule even on gut-feeling, even if I do not understand (grasp) completely why this should be logically so.
my fellow traveller in the train has another strategy. she goes by the number. first she checks all cells on the possibility of ones, then on two's, then on three's and so on. whenever any number in any cell is directly singled out, it is written there. the proces repeats. she does it first on rows, then on columns. only in the later stages she includes checking on the squares. she cannot logically validate this strategy but she has the confidence of the expert in her voice while explaining it. would you consider this strategy to be of any sense?
Hi Jelle,
Did you get it that every dot represents a number that could be in the cell? Maybe I was not very explicit about it. I thought it was an obvious notation to represent the options. So the dot in the upper-left corner represents 1, next to it is number 2 and in the upper-right corner is 3. Number 4 is left in the middle, etc.. Thus the (dark) blue dot represents number 8.
It sounds like your fellow traveller is just systematically applying rule 1 and 2 at the same time. She checks the options for every cell. However, you don't specify the rule she applies in her check. As a specification of a computer program this is absolutely worthless. It's quite normal that you give a poor specification. All computer users do that. I'm glad, because it's my job to make clarify such specifications.
so I guess she just checks if the number is not already in the row or column (rule 1) and whether this is the only number in this cell that is not already in a row or column (also rule 1) and then she checks if that cell is the only remaining position for that number on that row or column (rule 2). Probably she does these checks somehow in parallel. Our brain is capable of quite some parallel processing.
My computer program does not compute all the cells at the same time. It does the computations cell after cell, but with such a speed, that we think it done at the same time. To be more precise it does only necessary computations. No computation cycle is waisted. (Hey, it can only do about 500 million operations a second.) It uses some data structures to store all the options. Every time a number is entered in a cell that option is removed from the other cells on the row, column and block. There is a counter per cell for the nr of remaining options (rule 1) and per option there is a counter per row, column and block (rule 2). Every time a number is entered approximately 50 very simple expressions are evaluated. I have not completely automated the solver, but I guess it could solve simple Sudoku grids (with rule 1 and 2 only) in a few microseconds. But this version uses about 1000 times as much time to animated it all on the screen.
It's great that you understood rules 3 and 4 and found them more useful than rule 1 and 2. Especially since there were some typo's in the rules. I fixed them. The current text is as it should have been. My experience is that rules 1 and 2 can done without making something like a grid. One can check every cell just like your fellow traveller does. You need a well trained memory to apply rules 3 and 4 without making notes, because one has to consider all the options in a block.
From your description of your solution process I guess that you're simply using rules 1 and 2 in a clever way. Conclusion: I've written a very poor explanation of the rules.
Your 'AI' question is very interesting. I've not really thought about process to construct a valid sudoku grid. This must be one. I'm not sure if the process is always converging to a valid grid.
You know, solving these kind of problems is most about gut-feeling. You see something regular or dissonant and have the feeling that there must be something there. That's the beginning. It's the way I often solve problems at my work. When there is a strange problem in the software I just start staring at a lot of data hoping to see some regularity or dissonant. Problem solving is pattern matching and associative thinking. Something that humans can do pretty good and computers not. But they are very good in filtering, sorting and aggregating huge amounts of data.
Yeah, sudoku is a simple game, but it gives you a lot to reflect on.
Did you get it that every dot represents a number that could be in the cell? Maybe I was not very explicit about it. I thought it was an obvious notation to represent the options. So the dot in the upper-left corner represents 1, next to it is number 2 and in the upper-right corner is 3. Number 4 is left in the middle, etc.. Thus the (dark) blue dot represents number 8.
It sounds like your fellow traveller is just systematically applying rule 1 and 2 at the same time. She checks the options for every cell. However, you don't specify the rule she applies in her check. As a specification of a computer program this is absolutely worthless. It's quite normal that you give a poor specification. All computer users do that. I'm glad, because it's my job to make clarify such specifications.
so I guess she just checks if the number is not already in the row or column (rule 1) and whether this is the only number in this cell that is not already in a row or column (also rule 1) and then she checks if that cell is the only remaining position for that number on that row or column (rule 2). Probably she does these checks somehow in parallel. Our brain is capable of quite some parallel processing.
My computer program does not compute all the cells at the same time. It does the computations cell after cell, but with such a speed, that we think it done at the same time. To be more precise it does only necessary computations. No computation cycle is waisted. (Hey, it can only do about 500 million operations a second.) It uses some data structures to store all the options. Every time a number is entered in a cell that option is removed from the other cells on the row, column and block. There is a counter per cell for the nr of remaining options (rule 1) and per option there is a counter per row, column and block (rule 2). Every time a number is entered approximately 50 very simple expressions are evaluated. I have not completely automated the solver, but I guess it could solve simple Sudoku grids (with rule 1 and 2 only) in a few microseconds. But this version uses about 1000 times as much time to animated it all on the screen.
It's great that you understood rules 3 and 4 and found them more useful than rule 1 and 2. Especially since there were some typo's in the rules. I fixed them. The current text is as it should have been. My experience is that rules 1 and 2 can done without making something like a grid. One can check every cell just like your fellow traveller does. You need a well trained memory to apply rules 3 and 4 without making notes, because one has to consider all the options in a block.
From your description of your solution process I guess that you're simply using rules 1 and 2 in a clever way. Conclusion: I've written a very poor explanation of the rules.
Your 'AI' question is very interesting. I've not really thought about process to construct a valid sudoku grid. This must be one. I'm not sure if the process is always converging to a valid grid.
You know, solving these kind of problems is most about gut-feeling. You see something regular or dissonant and have the feeling that there must be something there. That's the beginning. It's the way I often solve problems at my work. When there is a strange problem in the software I just start staring at a lot of data hoping to see some regularity or dissonant. Problem solving is pattern matching and associative thinking. Something that humans can do pretty good and computers not. But they are very good in filtering, sorting and aggregating huge amounts of data.
Yeah, sudoku is a simple game, but it gives you a lot to reflect on.
Post a Comment
<< Home
