Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #9983
| From | David Kuehling <dvdkhlng@gmx.de> |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | Re: Sumbrero puzzle solver |
| Date | 2012-03-11 00:30 +0100 |
| Message-ID | <87vcmckpaf.fsf@snail.Pool> (permalink) |
| References | <17111793008435@frunobulax.edu> |
>>>>> "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/.
> The puzzle seems to be constructed in a way that makes solving it by
> numerical methods very difficult. I couldn't do it with squaring
> followed by matrix inversion.
> I hate puzzles.
> -marcel
> -- ---------------------------------------- (* * LANGUAGE : ANS Forth
> with extensions * PROJECT : Forth Environments * DESCRIPTION : Game
> solver * CATEGORY : Example * AUTHOR : Marcel Hendrix * LAST CHANGE :
> March 10, 2012, Marcel Hendrix *)
> NEEDS -miscutil
> REVISION -sumbrero "--- Sumbrero puzzle Version 0.01 ---"
> PRIVATES
> DOC (* The figure below shows a board containing seven squares, a..g.
> Each square should eventually contain a number [1 9].
> a The board has 6 diagonal lines of squares, d f three
> horizontals ones, and three verticals ones. b The sum of the target
> numbers on the diagonals e g and the verticals is given (NOT the
> horizontals). c The task is to find the 7 numbers.
> 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
> Discussion ---------- We have 7 unknowns and 9 equations. Note
> that the constraint says that the solution must not contain numbers
> out of [0 9].
> 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]
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
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. 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.
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.
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).
cheers,
David
--
GnuPG public key: http://dvdkhlng.users.sourceforge.net/dk.gpg
Fingerprint: B17A DC95 D293 657B 4205 D016 7DEF 5323 C174 7D40
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