Test Run - Solving Sudoku Using Combinatorial Evolution RRS feed

  • General discussion

  • James McCaffrey explains how write a program to solve difficult Sudoku problems, using a technique he calls combinatorial evolution, a set of general guidelines that can be used to design a concrete algorithm to solve a specific optimization problem.

    Read this article in the November issue of MSDN Magazine

    Monday, October 31, 2016 7:24 PM

All replies

  • Just a new way to call good old Genetic Algorithm
    Tuesday, November 15, 2016 11:39 AM
  • I love these Test Run articles but wish there were made available with F# code examples.  I'd have thought F# would be a better fit for solving problems discussed in this column.

    Still, great work. Thanx,

    Michael McD.

    Wednesday, November 16, 2016 12:51 PM
  • He says that the evolution works by taking the best worker and best explorer organisms and combining them to produce a (hopefully) superior organism that you keep in favour of the worst. Two questions...

    1) Why does he only produce one new organism? Why not take the top (say) ten organisms and "breed" them to produce five new ones? Wouldn't this find an optimal solution more quickly?

    2) How does he know that combining two organisms will produce a better offspring? Even if the parents have a low error, by combining them, you might be producing a combination with a high error. This is important for using this heuristic against other problems, as you would need to know what is a valid way to combine.

    Anyone able to explain?

    <p><strong>FREE custom controls for Lightswitch!</strong> A collection of useful controls for Lightswitch developers (Silverlight client only). <a href="http://visualstudiogallery.msdn.microsoft.com/9c342bec-e3e5-4c08-9993-35ccb26d3c9f"> Download from the Visual Studio Gallery</a>.</p> <p>If you're really bored, you could read about my experiments with .NET and some of Microsoft's newer technologies at <a href="http://dotnetwhatnot.pixata.co.uk/">http://dotnetwhatnot.pixata.co.uk/</a></p>

    Wednesday, November 30, 2016 5:43 PM
  • In the article, James McCaffrey says "The demo problem is non-easy because the brute-force algorithm doesn't work". In my opinion Sudoku is a classic problem to be solved with brute-force, I can't see why it should not work for example on the demo problem. So I wrote a relatively simple recursive algorithm that probes all values from 1 to 9 for each field that is empty....et voilá...the problem may be non-easy, but could be solved with brute force. Or have I misunderstood the definition of non-easy/brute-force in this context?
    Friday, December 30, 2016 8:12 AM