Saturday, May 2, 2020

Four Color Sudoku Theorem

I had some missteps on this latest Sudoku puzzle, but when I stopped making mistakes I was able to solve it in 47:02.  (Full solution below.)

I'm surprised the guy in the video didn't color-code any of the sections.  (He only used color at one point for three of the squares that he knew were identical.)  It was a Killer Sudoku puzzle, so there were a lot of oddly-shaped cages, and it was difficult to see all the outlines on my screen.  Hence, I used three additional colors to fill in the cages:
This got me thinking:  Would it be possible to color in ALL the sections of this puzzle without having any two sections of the same color touching each other--whether in an orthogonal or diagonal manner?  It turns out you can!
Then I wondered:  What if you treated each individual square as its own section.  Could you color in an entire puzzle that way with just four colors, and never have similarly-colored cells touch each other?  It took me a few minutes to realize that--DUH!--it would be easy to do this.  Just devote each column to two colors at a time, and keep those columns separate:
This led me to form the beginnings of a mathematical theorem.  Call it the "Four Color Sudoku Theorem."  It will prove that it's possible for any Sudoku puzzle to be filled in with only four colors, and under the condition that no two sections of the same color touch each other. 

No comments: