Chromatic Numbers: Sudoku

[Xittenn]

I have little to no interest in Sudoku what so ever! This said I was wondering if anybody could briefly explain how one could use Graph Colouring and Chromatic Numbers to solve a Sudoku puzzle?

 

thx,

daPincess

[Xittenn]

To further elaborate or to make this question less redundant I will attempt to add structure to this as a thread/question.

 

I mean numbers are assigned in a Sudoku puzzle and these numbers are considered under Graph Theory to be of a Chromatic nature. The method of my approach in a puzzle such as this, with having as afore mentioned absolutely no interest in the puzzle, is to use brute force!

 

All I have at my disposal in terms of literature on this at present is well Wiki and Wolfram. They seem to suggest there is some advanced methodologies which can be applied in aiding one to solve such puzzles. What are these algorithms and how are they formatted mathematically? With regards to Soduko of course!

 

Is this a terribly ugly field of mathematics? I have never really heard of Graph Theory until I just started reading a new text I bought. Leafs and trees kind of threw me off. I heard a couple of guys talking on the bus about chromatic numbers and I had to look it up. When I did it looked just as garbly as their conversation. It's not even so much that I'm not understanding, I just seem to be missing the substance that makes this branch of mathematics useful............

[forufes]

i hope somebody would clear this up..i visited both wolfram and wiki and got lost, but i'm interested in this mathematical field, it seems so complex and challenging. but soo unattainable.

[Xittenn]

So I've been looking at stuff and I feel I am making progress on this. I'm still not there but I am getting somewhere.

 

First off would a Sudoku be a form of Planarity? I think this is a yes, but Planarity seems to be both a definition and an actual game.

 

Second, I guess the best approach would be to represent the graph in matrix form. This would allow for manipulation with respect to algorithms right? And this is where I see this coming into play. I recently had an email with regards to a Matlab developer who had developed a Matlab tool that solved Sudokus; this was however brute force(can't find the newsletter.) Would lazy random walks on a given matrix representation of a graph not be an effective starting point towards finding solutions to such problems? With appropriate analytic algorithms of course... the word adjoint came to mind for this sentence but the definition wasn't the one expected...

 

I've been looking at Haskel for some possible projects, Natural Language/Speech, AI, as lazy functional languages seem to be appropriate for these tasks. I might have to try and approach Sudoku also, I think it might help me learn how to approach graphs as matrices... I also think it to be geared towards Graph Reduction..

 

Any thoughts?

Edited February 28, 2010 by buttacup