Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #10024

Re: Sumbrero puzzle solver

Show key headers only | View raw

>>>>> "Marcel" == Marcel Hendrix <mhx@iae.nl> writes:

> 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)

[..]

> 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 ]

Right, my mistake.

> and has condition number 7.2369e+016

Nice how numeric math fails even for small matrices with integer
entries.  In Octave I get

  det(a'a) = 7.2013e-14

which obviously is impossible, as a determinant over integer matrices
must itself be integer.  So I'd say it is safe to assume that the
condition number is 0 :)

That just made me remember how integer matrix systems with integer
solutions can be solved exactly by using arithmetic mod N (with N
prime).  Division modula a prime N can be nicely defined [1] so you get
an exact gauss algorithm.  The result is still modulo N, but that's
mostly no problem if N is large enough.  Still doesn't help much with
under-constrained systems of equations, as there is no (useful)
pseudo-inverse in modulo arithmetic.

> 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.

In Octave I'd use ols() to get the least-squares solution (i.e. what
pseudo-inverse usually is used for).  I don't think that the solution
would be far off, it'd just be not an integer solution, so pretty
useless.  

The space of possible solutions should be three-dimensional (?).  I
think there might be some pseudo-polynomial algorithm for searching that
space for an integer solution, very similar to the pseudo-polyonmial
algorithm for the NP-complete "subset sum problem" [2]

Hmm, taking the whole problem modulo a small prime, we could just
brute-force the 3-dimensional solution space in something like 17^3
operations.  Then we'd just have to scan those candidate solutions for
one that satisfies all constaints, and still works in non-modulo
arithmetic (i.e. didn't wrap-around).

[..]

>> 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.

Not unless you want to solve many, many (say 10^8) puzzles :)

Although you're right, I find it somewhat unsatisfying that a computer
needs a million tries for a problem easily solved by a human.

cheers,

David

[1] http://sourceforge.net/p/fkt/code/2/tree/trunk/mod.fs?force=True
[2] https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution

-- 
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

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