Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #9985
| From | mhx@iae.nl (Marcel Hendrix) |
|---|---|
| Subject | Re: Sumbrero puzzle solver |
| Newsgroups | comp.lang.forth |
| Message-ID | <64100292008435@frunobulax.edu> (permalink) |
| Date | 2012-03-11 01:25 +0200 |
| References | <87vcmckpaf.fsf@snail.Pool> |
| Organization | Wanadoo |
David Kuehling <dvdkhlng@gmx.de> writes Re: Sumbrero puzzle solver
>>>>>> "Marcel" == Marcel Hendrix <mhx@iae.nl> writes:
>> Here is a general solution to the so-called Sumbrero puzzle. Some
>> examples can be found on http://www.omegajunior.net/code/sumbrero/.
[..]
>> Sample problem:
>> a + f = 8
>> b + d + g = 14
>> c + e = 13
>> a + d = 3
>> b + e + f = 16
>> c + g = 16
>> d + e = 8
>> a + b + c = 11
>> f + g = 16
[..]
>> x = [a b c d e f g]'; b = [8 14 13 3 16 16 8 11 16]'; A * x = b;
>> A^t * A * x = A^t * b x = (A^t * A)^-1 * A^t * b
>> This doesn't work: A'*A is not invertible (quadruple eigenvalue)
> Did I misunderstood something? x=[a....g], b=[8,14,13,...16]
> A =
> [1,0,0,0,0,1,0
> 0,1,0,1,0,0,1
> 0,0,1,1,0,0,0
> 1,0,0,1,0,0,0
> 0,1,0,0,1,1,0
> 0,0,1,0,0,0,1
> 0,0,0,1,1,0,0
> 1,1,1,0,0,0,0
> 0,0,0,0,0,1,1]
Actually, the matrix A is
[ 1 0 0 0 0 1 0
0 1 0 1 0 0 1
0 0 1 0 1 0 0
1 0 0 1 0 0 0
0 1 0 0 1 1 0
0 0 1 0 0 0 1
0 0 0 1 1 0 0
1 1 1 0 0 0 0
0 0 0 0 0 1 1 ]
and has condition number 7.2369e+016
> A'*A is
> 3 1 1 1 0 1 0
> 1 3 1 1 1 1 1
> 1 1 3 1 0 0 1
> 1 1 1 4 1 0 1
> 0 1 0 1 2 1 0
> 1 1 0 0 1 3 1
> 0 1 1 1 0 1 3
A'*A =
[ 3 1 1 1 0 1 0
1 3 1 1 1 1 1
1 1 3 0 1 0 1
1 1 0 3 1 0 1
0 1 1 1 3 1 0
1 1 0 0 1 3 1
0 1 1 1 0 1 3 ]
> which *is* invertible. Even if A'*A were not invertible, still
> (A'*A)^-1*A' is the pseudo-inverse of A which AFAIR is well-defined even
> for non-invertible A'A.
It should give the best solution in a least-square sense, but it is far off the
mark. Computed in Matlab it completely useless, computed with iForth's 80-bit
floats is was somewhat better but still unsatisfying.
> Also I don't get the "quadruple eigenvalue"
> argument: a 4x4 diagonal matrix with only ones on the diagonal has a
> quadruple eigenvalue and is clearly invertible.
Yes, I made an unforgiveable error there.
> The problem at hand is an instance of the "closest lattice point"
> problem. I.e. minimize the squared error (Ax - b)^T*(Ax - b) over the
> integeger vectors 'x'. It is NP-hard. Well, in case you know that
> there is an exact solution with error=0, the problem should be no harder
> than NP-complete.
That's a relief :-) Very interesting, I must remember that.
Note that I forgot to document the fact that it is forbidden to use
same numbers on a single diagonal or vertical line. That's what the
?LEAVE and ORs are for. The additional constraints make using the CLP
even less competitive?
> AFAIK Lattice Reduction is one of the best known polynomial-time
> algorithms for finding approximate solutions to the lattice point
> problem. For exact solutions, the "Sphere Decoder" is going to be
> (asymptotically) faster than the brute force approach that you
> implemented, but still exponential run-time (exponential over puzzle
> sizes; not really a meaningful statement for the constant-size puzzles
> at hand).
There are only about five million possibilities to test for.
I found it takes a maximum of 20 ms to find the hardest solution
(1 million tries). There is no reason to go for a better algorithm
here.
Thanks for your interesting observations.
-marcel
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Sumbrero puzzle solver mhx@iae.nl (Marcel Hendrix) - 2012-03-10 18:24 +0200
Re: Sumbrero puzzle solver David Kuehling <dvdkhlng@gmx.de> - 2012-03-11 00:30 +0100
Re: Sumbrero puzzle solver mhx@iae.nl (Marcel Hendrix) - 2012-03-11 01:25 +0200
Re: Sumbrero puzzle solver David Kuehling <dvdkhlng@gmx.de> - 2012-03-11 23:27 +0100
Re: Sumbrero puzzle solver mhx@iae.nl (Marcel Hendrix) - 2012-03-19 00:00 +0200
Re: Sumbrero puzzle solver "A. K." <akk@nospam.org> - 2012-03-19 08:24 +0100
Re: Sumbrero puzzle solver mhx@iae.nl (Marcel Hendrix) - 2012-03-20 20:36 +0200
Re: Sumbrero puzzle solver mhx@iae.nl (Marcel Hendrix) - 2012-03-20 23:12 +0200
Re: Sumbrero puzzle solver "A. K." <akk@nospam.org> - 2012-03-21 12:06 +0100
Re: Sumbrero puzzle solver "A. K." <minforth@arcor.de> - 2012-03-11 12:10 +0100
Re: Sumbrero puzzle solver "A. K." <akk@nospam.org> - 2012-03-12 21:51 +0100
Re: Sumbrero puzzle solver Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-03-11 19:22 +0000
Re: Sumbrero puzzle solver David Kuehling <dvdkhlng@gmx.de> - 2012-03-11 22:35 +0100
Re: Sumbrero puzzle solver C G Montgomery <cgm@physics.utoledo.edu> - 2012-03-11 18:23 -0400
csiph-web