Neural nets and Sudoku
J. J. Hopfield, of neural net fame, just put out a new paper on associative memory and Sudoku. The Sudoku part involves constructing a (highly nonrandom) neural net that models a linear programming relaxation of the puzzle; as would perhaps be unsurprising to IPCO types, it works well on instances of moderate difficulty and only needs a small amount of branching even on quite hard instances. More intriguing to me in connection to Sudoku were some earlier examples (figures 1 and 2) of figures where the human visual system can find information quickly amid what seems a lot of noise, and where once found the signal seems to "pop" from the field; I sometimes get a similar "pop" feeling when I am solving Sudoku instances by hand, so (whether or not one believes that our eyes can solve arbitrary linear programs) he may be on a good track by using similar mechanisms to explain Sudoku solving and human visual memory.