Graph Colouring, Part Five

re: Graph Colouring, Part Five

AlexOld — Mon, 02 May 2011 09:08:36 GMT

The Status property fails (returns Solved) in degenerate case when required number of colours = 1. Some check must be added. I think Eric would do it in the most elegant way.

The whole job is just marvellous (breathtaking). Thank you very much, Eric.

re: Graph Colouring, Part Five

EugenUS — Mon, 04 Oct 2010 20:15:18 GMT

@Eris - awesome post.

@All - anybody knows other blogs where somebody would explain other algorithms from real world with a step by step implementation. I hate those blogs with theory only. :) Eric rules with his posts.

re: Graph Colouring, Part Five

Visitor — Thu, 09 Sep 2010 11:49:45 GMT

@Greg - if you claim that graph coloring is solvable by doing transitive closure with matrices please present the solution or leave a reference. Or even just for Sudoku. Not kidding - it's considered to be NP-complete and transitive closure is computable in N^3, so just in case that there might be a golden shortcut in some corner of the internet - one never knows :-)

re: Graph Colouring, Part Five

Greg — Tue, 17 Aug 2010 23:43:34 GMT

There is an optimized way of doing this by using a square matrix to represent transitions between nodes and then using matrix multiplication to find the transitive closure of the matrix. The memory footprint, upper bound on the number of multiplications and performance information is known ahead of time for this implementation.

re: Graph Colouring, Part Five

Chris — Thu, 05 Aug 2010 15:33:42 GMT

Now what;s the chances for a solver for next weeks lotto?

re: Graph Colouring, Part Five

Micah — Wed, 04 Aug 2010 14:27:01 GMT

@configurator: Toget an exception for a non-unique solution you would use:

return solution.Single();

re: Graph Colouring, Part Five

tobi — Tue, 03 Aug 2010 13:01:43 GMT

rofl what a nice surprise. a sudoku solver is a nine-colorer of some specific graph.

re: Graph Colouring, Part Five

configurator — Sun, 01 Aug 2010 13:35:34 GMT

@Brian: Or change the line in Solve():

from

return solutions.FirstOrDefault();

return solutions.First();

if you want an exception for non-unique solutions

re: Graph Colouring, Part Five

Brian — Thu, 29 Jul 2010 21:17:54 GMT

@oldnewthing: That's boring. All it takes to do that is to mark the first solution found as invalid, thus forcing the backtracker to search for an alternative solution.

re: Graph Colouring, Part Five

Raymond Chen - MSFT — Thu, 29 Jul 2010 19:36:55 GMT

Exercise: Extend this program so it also reports whether the solution is unique, a detail often lost in Sudoku puzzle creation.