Did you ever get half way through a really tough sudoku and begin to wonder if it really has a solution, or finish one and wonder if when you decided that one cell was a five and not a three that if you had picked the other one it STILL would have worked out? The answer, my friend, lies in polynomials.
Recently learned about all this from a nice article you can read for yourself, and maybe if you find my mistakes, drop me a line.
The authors point out that every Sudoku puzzle can be thought of as a graph with 81 vertices (nine rows and nine columns). Now think of the nine numbers in the top row..they would all have to be connected to each other with an edge. They would all have to be connected to each of the cells that are in their same column, and also to the eight others in their sub-square (but they have already been connected to at least four of those, two in their row and two others in their column). By my calculation, that means that each of the 81 vertices would have 8+8+4=20 edges connected to it, for a total of 810 edges.
Now if we associate the number in each cell as a color, a solution would be the same as a properly colored graph (no edge connects two vertices of the same color). An unfinished Sudoku is then a partially colored graph, and solving it is just a matter of finding a way to color the remaining vertices so that no edge connects two vertices of the same color. If it is not possible to do that, there is no solution... and if you can do it more than one way, there is more than one solution.
Now comes the polynomial part. It seems it is "well known" that "The number of ways of coloring a graph G with n colors is well known to be a polynomial in n of degree equal to the number of vertices of G." (Where have I been?). Wait, that means we are looking for a polynomial with degree 81... Ummm.. that may take a little time, so let's look at a simple example.
Suppose we have a simple graph like a triangle, the complete graph of degree three, usually called K3. [A complete graph has each vertex connected to every other vertex with an edge.] It should be clear it can not be properly colored with one or two colors, but with three colors we could do it in six ways (3!). But how many ways could you color if if you had four colors available, or five, or nine, or a complete box of 64 crayola crayons. The answer is pretty easy using the associated polynomial. For K3 the number of ways to color it using n colors is n(n-1)(n-2). So for four colors you could complete the coloring in 24 different ways. You can easily extend the polynomial for a complete graph of t vertices using n colors to get Kt to be n(n-1)(n-2)....(n-t+1).
Ok, so what about one like this?
Can you do it in three colors, four, five? If you can write the polynomial for it it should tell you. I admit that I am not sure about how to write some of the pretty simple ones... for instance, if a vertex is joined to two vertices that have n-2 colors possible each, but they are not connected; should that new vertex contribute a (n-3) or an (n-2). Trying to learn as I go along, but mostly by drawing simple ones that I can enumerate all the possible colorings.Complications spring up when you have a graph that is more complex (and especially if it has 81 vertices), but if you had the polynomial, then you could just evaluate it for n=9 and it would tell you how many solutions there are. The authors did point out some simple theorems that pop out when you make the connection to graphing. For example, any sudoku that gives you only seven of the nine numbers in the "given" must have more than one solution (if it has any). Consider that if you have a solution you could interchange all the cells that have the two missing colors and get another solution. So a puzzle with a unique solution must contain at least eight of the nine numerals. The authors suggest that the number of cells that must be "given" in the problem is an unsolved problem, but they have unique examples with as few as 17, so that would be an upper bound on the solution. The puzzle at the top has eight of the nine digits in it, and exactly 17 cells "given". So does it have a solution? or two? Happy graph coloring children.
Here is a simpler problem, can you write the coloring polynomial for this graph, and find the number of colors for n=3, 4, and 10 colors?
>Ok, so what about one like this? Can you do it in three colors, four, five?
ReplyDeleteI'm not getting the polynomial part yet, but I know the first graph can be colored in 4 colors or less, because this is the same as the map coloring theorem. So any planar graph can be colored in 4 colors or less. (I got that from Euler's Gem, by Dave Richeson, which I'm in the middle of.)
I just worked it out (drew a map), and discovered that a loop of 4 in the graph is equivalent to a situation where 4 corners touch (like CO, UT, NM, AR).
I've convinced myself that 4 colors are needed. To explain my reasoning, I'll use letters. Coming down the left, I have A on top, then B, the third one down touches both the first two, so it needs a third letter, C. The last one touches the 3rd and top, so it can be B. Next to C must be A, since it touches bottom left. Below that must be a C. Now the second down on the right touches A, B, and C, so must be D, leaving B for the top right.
Yes, If it is planer...(this one obviously is, it is drawn without lines crossing; But keep in mind that even simple graphs like K-five (think of a pentagon with a pentagram inside it).. and that isn't planer. (in fact it is half the "forbidden" that Kuratowski's theorem uses to define Planer. This one obviously is, and I agree, it must have four colors, but how many different ways could it be colored with just four colors?? (by the way you know if it can be colored in four colors, none of the polynomial factors could be (n-a) could have a>3 since that would produce zero ways to color it with four colors (and you just proved it COUlD be done in four)..
ReplyDeleteOne of the factors has to be n, and the other seven(remember with eight vertices, it will be an eighth degree polynomial) will be either (n-1), (n-2) or (n-3) ... I'm betting on a lot of (N-3) factors.. but (ugly confession) I'm not sure I have the polynomial for that one yet.