16-Clue Sudoku Proven Not Possible

Here is an interesting study that proved that a 16-clue Sudoku puzzle is not possible (no unique solution exists). It only took 7.1 million core hours ( Jan 2011 through Dec 2011) on a cluster with 320 compute nodes, and each node had 2 Intel Xeon Hex-core processors with 24GB of RAM. Although this may sound like a brute force simulation, the approach that this group took used a novel algorithm that drastically reduced the computation time, which was previously estimated to be 300,000 years on one computer.


No comments:

Post a Comment