This numerical tour explores the use of numerical schemes to solve the Sudoku game.
Contents
This tour was written by Yue M. Lu and Gabriel Peyré.
- Installing toolboxes and setting up the path.
- Game Encoding and Decoding
- Encoding Constraints
- Sudoku Rules Constraints
- Inpainting Constraint
- Solving the Sudoku by Binary Integer Programming
- Removing the Binary Constraint
- Solving the Sudoku by Projection on Convex Sets
- Decoding Using L1 Sparsity
- Decoding Using more Aggressive Sparsity
I'll feature this example in the Compressed Sensing games page. One of the things that came out of the discussion with Gabriel was that there is a set of problems that cannot seem to be solved by using the L1 /sparsity or the POCS solution. Unbeknownst to me, there are difficult Sudoku problems and it looks like that sparsity alone is not a good enough a constraint to provide a solution for some problems. such as the AL Escargot. I learn something everyday. If you recall Gabriel has released two other examples of compressive sensing already in his numerical tours:
Suresh let me know on Twitter that there is some interesting activity on the Theoretical Computer Science Q&A website on Compressed Sensing, and surely enough one of the best answers so far is that of Piotr Indyk. From now on, my daily search for stuff on compressed sensing will include this Q&A.
You probably recall this story of the Kodak engineers who acknowledged they had no idea about the usefulness of the first digital camera. Well Dick Gordon sent me the following as a comment:
Sunday, August 22, 2010 1:39 AM from Winnipeg
Re: the Kodak engineers produced the first digital camera...
Maybe a line from the technical report written at the time sums it up best: “The camera described in this report represents a first attempt demonstrating a photographic system which may, with improvements in technology, substantially impact the way pictures will be taken in the future"....But in reality, we had no idea.”
Nonsense. I had written them a letter (in the days before e-mail!) suggesting that they go one step further, mosaicing focal planes to select in-focus pixels and produce the first camera that could not take an out of focus picture. Got no reply. The other obvious problem was lack of self-confidence at Kodak: they made a digital back for a Nikon camera. Nikon is still around, and Kodak is just about dead. Moribund leadership for a once great company, I suspect.
I know a fellow at University of Manitoba who still has this Kodak unit.
Yours, -Dick Gordon gordonr@cc.umanitoba.ca
In a different direction, somebody asked me to provide a hyperlink linking his/her name to his/her webpage. Please, if your name appears with no hyperlink or to the wrong one, let me know and I'll try to correct it asap. To give you an idea as to why it is important to be linked from Nuit Blanche, I usually receive some spam requests asking to include links on recent entries for free. I also get some amount of spam from people trying to use the comment section to l.ink back to their "content". Recently however, something new happened, I received an email from a gentleman who proposed to pay a hundred dollars to plant a link in an old entry of this blog... this is interesting on so many levels. With no further due and using you, the readers as filters, here is a set of meetings that are probably of interest to you: Pierre Vandergheynst let me know of a meeting in Marseille mostly in French on signal processing in biology. It is here. Mark Plumbley also let me know of the INSPIRE 2010 Conference in London.
INSPIRE 2010 Conference on information representation and estimation
Date, Time & Location
University College London
Monday 06/09/2010 - Wednesday 08/09/2010
09:00-18:00
Description
Mathematical methods for signal processing and in general for data representation and inference are growing more and more sophisticated. Successful applications of such methods range from medical imaging to security. Developments in mathematics and signal processing are however often divergent. Therefore, the main aim of this conference is to bring together signal processing researchers with statisticians and mathematicians working on problems related to data modelling and estimation, to encourage the exchange of ideas as well as to discuss theoretical underpinning of the methods and domains of application.
The INSPIRE 2010 conference will be held at the Anatomy JZ Young LT at University College London from September 6 till September 8, 2010.
Please visit the conference website to register: http://www.network-inspire.org/events/view/3
The Programme is available at the following link: http://www.commsp.ee.ic.ac.uk/~pld/programmeINSPIRE2010.pdf
Contact Professor Sofia Olhede
No comments:
Post a Comment