Re: NUMB3RS, Grobner bases, and "Trust Metrics"

On Oct 2, 6:48 am, Raphael Jolly <raphael.jo...@xxxxxxx> wrote:
rjf wrote:
After posting that note, I found out that you can see the whole show
at

http://video.aol.com/video-category/numb3rs/2995

You might not find it as interesting as, for example, something I
posted on youtube
http://youtube.com/watch?v=0jw1W9RuIEk

The connection to sci.math.symbolic being that I post in both
places.:)

Yes, I prefer the latter, even though Groebner bases are not involved.

Another real-life domain where these can be used is in solving sudoku:

http://www.cs.amherst.edu/~dac/lectures/gb2.handout.pdf

Raphael

Those notes show a way to attack sudoku puzzles by setting up a graph
coloring problem. Edges connect vertices in the same row, column, or
3x3 box. Polynomial constraints enforce that neighbors not have the
same color.

They show a sudoku example but do not indicate whether it was solved
by the indicated method. While I admit I've not attempted the
computation, I suspect it is not feasible using current software. Has
anyone managed to solve sudoku puzzles using this tactic?

I show below the example from those notes, in Mathematica-esque format
modelled after the SparseArray structure. The "rules" have the obvious
meaning: {i,j}->k means place the numeral k in row i, column j of the
sudoku box.

mat = sparseArray[{{1, 5} -> 3, {1, 6} -> 5, {2, 2} -> 1,
{2, 4} -> 2, {2, 7} -> 9, {3, 1} -> 7, {3, 3} -> 6,
{3, 7} -> 2, {4, 1} -> 6, {4, 4} -> 5, {4, 8} -> 3,
{5, 1} -> 2, {5, 5} -> 4, {5, 9} -> 9, {6, 2} -> 3,
{6, 6} -> 1, {6, 9} -> 5, {7, 3} -> 3, {7, 7} -> 4,
{7, 9} -> 8, {8, 3} -> 4, {8, 6} -> 6, {8, 8} -> 7,
{9, 4} -> 3, {9, 5} -> 1}, 9];

Here is an example I think for various reasons is easier but still
nontrivial.

mat = sparseArray[{{1, 2} -> 6, {1, 4} -> 1, {1, 6} -> 4,
{1, 8} -> 5, {2, 3} -> 8, {2, 4} -> 3, {2, 6} -> 5,
{2, 7} -> 6, {3, 1} -> 2, {3, 9} -> 1, {4, 1} -> 8,
{4, 4} -> 4, {4, 6} -> 7, {4, 9} -> 6, {5, 3} -> 6,
{5, 7} -> 3, {6, 1} -> 7, {6, 4} -> 9, {6, 6} -> 1,
{6, 9} -> 4, {7, 1} -> 5, {7, 9} -> 2, {8, 3} -> 7,
{8, 4} -> 2, {8, 6} -> 6, {8, 7} -> 9, {9, 2} -> 4,
{9, 4} -> 5, {9, 6} -> 8, {9, 8} -> 7}, 9];

If people can get that method to work for these or similar examples,
I'd be interested to hear about it.

Daniel Lichtblau
Wolfram Research




.

Relevant Pages

  • Re: Is someone working on solving Othello?
    ... Rick Pikul wrote: ... that can solve Sudoku puzzles for you. ... "How do you write a program that can solve any given Sudoku puzzle?" ... since electronic calculators are so prevalent. ...
    (rec.games.board)
  • Re: Sudoku
    ... > Why is it that when I ask research mathematicians whether they're ... It took me two hours to write a program that solves Sudoku puzzles. ... Prev by Date: ...
    (sci.math)
  • Re: Cross words
    ... what is the name of the software for sudoku? ... bh-wages at swbell.net ... :>: Has Sudoku hit the States yet? ... I got some s/w for about $15 that will print as many Sudoku puzzles as I ...
    (alt.support.diabetes)
  • Re: a good worthy project ??
    ... A sudoku solver or a sudoku problem generator. ... 6670903752021072936960 sudoku puzzles, which is about 10^21. ...
    (comp.lang.c)
Quantcast