Timeline for Building a Physical Model to Solve Sudoku
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 20, 2013 at 20:51 | answer | added | Piyush Grover | timeline score: 0 | |
| Aug 15, 2012 at 16:49 | comment | added | paul garrett | Maybe such a computer should be called "analogue", to distinguish it from "digital". The classic example is sorting some (floating-point) numbers by size, by cutting rods (spaghetti?) to the various lengths, and standing all the rods on one end... | |
| Aug 15, 2012 at 12:03 | comment | added | Petra Schwer | Also, some Sudokus allow for several solutions which means the cues suffice to fill the grid but the solution is not unique. To find a physical solver you would then either need to assume uniqueness of the solution given the cues (but how does one test thi in advance??) or the solver should be able to give you all the solutions. | |
| Aug 15, 2012 at 5:35 | comment | added | Steven Landsburg | My brain is a physical system that can solve Sudokus. | |
| Aug 14, 2012 at 22:45 | comment | added | timur | I remember seeing a gradient flow in $SO(n)$ that solves the TSP. Maybe something similar could be done? | |
| Aug 14, 2012 at 22:42 | comment | added | timur | If you mean by Sudoku being NP-complete a setting involving $n\times n$ Sudokus with $n$ tending to $\infty$, then that does not seem to have much relevance in the real life Sudoku where we only have $n=9$. | |
| Aug 14, 2012 at 21:40 | answer | added | Yoav Kallus | timeline score: 3 | |
| Aug 14, 2012 at 21:36 | comment | added | Zack Wolske | Perhaps start with a 4x4 grid and see if there's a physical model that can solve that. It should be much simpler, since there are only 12 possible solutions up to permuting the entries. Non-existence in this case should be easier to do (maybe the models can't distinguish between two of the $4!*12$ solutions) and will imply the nonexistence of the larger solver, since you can embed the 4x4 grid into a 9x9 grid. | |
| Aug 14, 2012 at 20:02 | comment | added | user9072 | I am not sure this question is a good fit for MO. But, you might be interested in this paper by Scott Aaronson scottaaronson.com/papers/npcomplete.pdf | |
| Aug 14, 2012 at 19:22 | history | asked | Benjamin Dickman | CC BY-SA 3.0 |