“The Chaos within Sudoku” is a paper about solving Sudoku puzzles with physics. They simulate an imaginary physical system, let it run, and when it stops the puzzle is solved. See the video below:

The thing about Sudoku is that Sudoku is hard. More specifically, when Sudoku is generalized to grids of arbitrary size, it’s NP-complete. What happens when you translate an NP-complete problem to a physical simulation? The authors find chaotic dynamics.  And in the process, they identify the hardest Sudoku puzzle…
[Read more…]