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

Groups > comp.lang.forth > #9978 > unrolled thread

Sumbrero puzzle solver

Back to article view | Back to comp.lang.forth

Contents

  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

#9978 — Sumbrero puzzle solver

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

0 VALUE a	0 VALUE b	0 VALUE c	0 VALUE d
0 VALUE e	0 VALUE f	0 VALUE g

CREATE problems PRIVATE
   8 , #14 , #13 ,    3 , #16 , #16 ,    8 , #11 , #16 ,
   9 , #12 ,   7 ,    4 , #12 , #12 ,    3 , #12 , #13 ,
   4 ,   9 ,   4 ,    4 ,   9 ,   4 ,    4 ,   9 ,   4 ,
 #15 , #23 ,   8 ,  #15 , #23 ,   8 ,  #15 , #16 , #15 ,

HERE problems - 9 CELLS / =: #problems PRIVATE
0 VALUE barray  PRIVATE

: @b    ( ix -- ) CELLS barray + @ ; PRIVATE
: .B    ( -- ) CR ." b = ["  8 0 DO  I @b .  LOOP  8 @b 0 .R ." ]" ; PRIVATE
: (NEW) ( -- ) #problems CHOOSE 9 CELLS * problems + TO barray ; PRIVATE (NEW) 
: NEW   ( -- ) (NEW) .B ;


-- No smart backtracking is used, simply try all possibilities.
: (STUPID) ( -- )
	#10 1 DO I TO a  #10 1 DO I TO b  #10 1 DO I TO c
	#10 1 DO I TO d  #10 1 DO I TO e  #10 1 DO I TO f
	#10 1 DO I TO g

		 a f = ?LEAVE 	
		 c e = ?LEAVE   
		 a d = ?LEAVE   
		 d e = ?LEAVE   
		 b d = ?LEAVE  

                 b e = ?LEAVE  b f = ?LEAVE  e f = ?LEAVE
		 a b = ?LEAVE  a c = ?LEAVE  b c = ?LEAVE

		 b g =  
		 c g = OR  
		 d g = OR
		 f g = OR 0=

		 a f + 	    0 @b = AND
		 b d + g +  1 @b = AND
		 c e + 	    2 @b = AND
		 a d + 	    3 @b = AND
		 b e + f +  4 @b = AND
		 c g +	    5 @b = AND
		 d e + 	    6 @b = AND
		 a b + c +  7 @b = AND
		 f g +	    8 @b = AND 

		   IF  UNLOOP UNLOOP UNLOOP 
		       UNLOOP UNLOOP UNLOOP 
		       UNLOOP EXIT  
		ENDIF

	LOOP LOOP LOOP LOOP LOOP LOOP LOOP TRUE ABORT" (STUPID) failed" ; PRIVATE

: STUPID  (STUPID) CR ." Found it: y = [" a . b . c . d . e . f . g 0 .R ." ]" ;

:ABOUT	CR ." Try STUPID to solve the Sumbrero puzzle " .B 
	CR ."     NEW generates a new problem for you." 
	CR ."     File contains " #problems . ." problems." ;

		.ABOUT -sumbrero CR
		DEPRIVE

                              (* End of Source *)

[toc] | [next] | [standalone]

#9983

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

[toc] | [prev] | [next] | [standalone]

#9985

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

[toc] | [prev] | [next] | [standalone]

#10024

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

[toc] | [prev] | [next] | [standalone]

#10214

David Kuehling <dvdkhlng@gmx.de> writes Re: Sumbrero puzzle solver

>>>>>> "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/.
 [..]
>> 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.

In that case my second iteration to the sumbrero is probably more 
to your liking. 

-marcel

PS: The timings have only a few ms resolution.

-- --------------------------------------------------------------------
(*
 * LANGUAGE    : ANS Forth with extensions
 * PROJECT     : Forth Environments
 * DESCRIPTION : Game solver
 * CATEGORY    : Example 
 * AUTHOR      : Marcel Hendrix 
 * LAST CHANGE : March 10, 2012, Marcel Hendrix 
 * LAST CHANGE : Saturday, March 17, 2012, 18:03, mhx, better algorithm
 *)



	NEEDS -miscutil

	REVISION -sumbrero "--- Sumbrero puzzle     Version 0.02 ---"

	PRIVATES

DOC
(*
     The figure below shows a board containing seven squares, a..g. 
     Each square should eventually contain a number [1 9]. Each line
     may contain only the numbers [1 9], where duplicates are not allowed.
     It is ok to use the same number on different lines.

  	 a            The board has 6 diagonal lines of squares,
      d     f         three horizontals ones, and three vertical 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	   a <> f
      b + d + g = 14       b <> d <> g
      c + e     = 13       c <> e
      a + d     = 3	   a <> d
      b + e + f = 16       b <> e <> f
      c + g     = 16  	   c <> g
      d + e     = 8	   c <> e
      a + b + c = 11	   a <> b <> c
      f + g     = 16	   f <> g
    
    Discussion
    ----------
    Of course, this implies 
	a =  b2 + b3 - b5 - b6 + g
	b = -b2 - b3 + b6 + b7
	c =  b5 - g
	d = -b2 + b5 + b6 - g
	e =  b2 - b5 + g
	f =  b0 - b2 - b3 + b5 + b6 - g
*)
ENDDOC

0 VALUE a	0 VALUE b	0 VALUE c	0 VALUE d
0 VALUE e	0 VALUE f	0 VALUE g

CREATE problems PRIVATE
   8 , #14 , #13 ,    3 , #16 , #16 ,    8 , #11 , #16 ,
   9 , #12 ,   7 ,    4 , #12 , #12 ,    3 , #12 , #13 ,
   4 ,   9 ,   4 ,    4 ,   9 ,   4 ,    4 ,   9 ,   4 ,
 #15 , #23 ,   8 ,  #15 , #23 ,   8 ,  #15 , #16 , #15 ,

HERE problems - 9 CELLS / =: #problems PRIVATE
0 VALUE barray  PRIVATE

: bx    CREATE CELLS , DOES> @ barray + @ ; PRIVATE

	0 bx b0	  1 bx b1   2 bx b2	3 bx b3
	4 bx b4   5 bx b5   6 bx b6	7 bx b7
	8 bx b8

: single2? ( a b -- bool ) = ; PRIVATE 
: single3? ( a b c -- bool ) 2DUP = >S  2 PICK = >S  =  S> OR  S> OR ; PRIVATE 

: single? ( -- bool )
	a f   single2? IF  FALSE EXIT  ENDIF
	c e   single2? IF  FALSE EXIT  ENDIF
	a d   single2? IF  FALSE EXIT  ENDIF
	c g   single2? IF  FALSE EXIT  ENDIF
	d e   single2? IF  FALSE EXIT  ENDIF
	f g   single2? IF  FALSE EXIT  ENDIF
	b d g single3? IF  FALSE EXIT  ENDIF
	b e f single3? IF  FALSE EXIT  ENDIF
	a b c single3? IF  FALSE EXIT  ENDIF
	TRUE ; PRIVATE

: range? ( u -- bool ) 1 #10 WITHIN ;
: testA ( -- bool ) b2 b3 +  b5 -  b6 - g + 	   DUP TO a  range? ; PRIVATE
: testB ( -- bool ) b6 b7 +  b2 -  b3 -     	   DUP TO b  range? ; PRIVATE
: testC ( -- bool ) b5 g -                  	   DUP TO c  range? ; PRIVATE
: testD ( -- bool ) b5 b6 + b2 - g -        	   DUP TO d  range? ; PRIVATE
: testE ( -- bool ) b2 b5 -  g +                   DUP TO e  range? ; PRIVATE
: testF ( -- bool ) b0 b2 -  b3 -  b5 +  b6 + g -  DUP TO f  range? ; PRIVATE

: .B     ( -- )    CR ." b = [" b0 . b1 . b2 . b3 . b4 . b5 . b6 . b7 . b8 0 .R ." ]" ; PRIVATE
: REPORT ( ix -- ) CR ." y = [" a . b . c . d . e . f . g 0 .R ." ] (" 0 .R ." ) " ; PRIVATE
: (NEW)  ( -- )    #problems CHOOSE 9 CELLS * problems + TO barray ; PRIVATE (NEW) 
: NEW    ( -- )    (NEW) .B ;

-- No smart backtracking is used, simply try all possibilities for g.
-- There are multiple solutions.
: (SMART) ( -- #tries )
	0 LOCAL #tries 
	9 1+ 1
	  DO  
		1 +TO #tries  I TO g  
		testA       testB AND testC AND 
		testD   AND testE AND testF AND 
		single? AND IF  #tries REPORT  ENDIF
	LOOP ; PRIVATE

: SMART  TIMER-RESET (SMART) CR .ELAPSED ;

:ABOUT	CR ." Try SMART to solve the Sumbrero puzzle " .B 
	CR ."     NEW generates a new problem for you." 
	CR ."     File contains " #problems . ." different problems." ;

		.ABOUT -sumbrero CR
		DEPRIVE

                              (* End of Source *)

-- output --------------------------------------------------------------

FORTH> in sumbrero
Creating --- Sumbrero puzzle     Version 0.02 ---

Try SMART to solve the Sumbrero puzzle
b = [8 14 13 3 16 16 8 11 16]
    NEW generates a new problem for you.
    File contains 4 different problems.
 ok
FORTH> new smart
b = [8 14 13 3 16 16 8 11 16]
y = [1 3 7 2 6 7 9] (9)
0.003 seconds elapsed. ok
FORTH> new smart
b = [4 9 4 4 9 4 4 9 4]
y = [1 5 3 3 1 3 1] (1)
y = [3 5 1 1 3 1 3] (3)
0.007 seconds elapsed. ok
FORTH> new smart
b = [9 12 7 4 12 12 3 12 13]
y = [3 4 5 1 2 6 7] (7)
0.003 seconds elapsed. ok
FORTH> new smart
b = [15 23 8 15 23 8 15 16 15]
y = [6 8 2 9 6 9 6] (6)
0.003 seconds elapsed. ok
FORTH> new smart
b = [4 9 4 4 9 4 4 9 4]
y = [1 5 3 3 1 3 1] (1)
y = [3 5 1 1 3 1 3] (3)
0.006 seconds elapsed. ok

[toc] | [prev] | [next] | [standalone]

#10221

On 18.03.2012 23:00, Marcel Hendrix wrote:
> David Kuehling<dvdkhlng@gmx.de>  writes Re: Sumbrero puzzle solver
>
>>>>>>> "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/.
>   [..]
>>> 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.

It does NOT !!
Reducing the solution space is a core topic in constraint programming.
see f.ex.
http://kti.ms.mff.cuni.cz/~bartak/constraints/index.html
How do you think that your car navigation system works? Or DNA 
sequencing? Or flight schedulers for airports? Absolutely impossible by 
brute force.

For further playing, the other one should take a bit longer to run:
http://www.omegajunior.net/code/sumbrero/sixbythree.html

[toc] | [prev] | [next] | [standalone]

#10251

"A. K." <akk@nospam.org> writes Re: Sumbrero puzzle solver

> On 18.03.2012 23:00, Marcel Hendrix wrote:
>> David Kuehling<dvdkhlng@gmx.de>  writes Re: Sumbrero puzzle solver

>>>>>>>> "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/.
[..]
>>>> 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.

> It does NOT !!

What doesn't? Is this reaction aimed at David or to me?

I have published solutions to two kinds of sumbrero's now. Both reduce
the problem much more than a constraint solver would/can, then solve
the constraints rather clumsily. Whatever, I am quite sure the solution
is much (400 times or more?) faster than, say, minion can do it.

Even so, I think it is no shame to use brute force for a problem that
yields to it, It gives much faster development than first writing a 
Prolog engine.

> Reducing the solution space is a core topic in constraint programming.
> see f.ex.
> http://kti.ms.mff.cuni.cz/~bartak/constraints/index.html

I learned a few interesting things there. Unfortunately/amazingly these
codes all seem to be proprietary.

> How do you think that your car navigation system works? Or DNA 
> sequencing? Or flight schedulers for airports? Absolutely impossible by 
> brute force.

I am sure our brains didn't sit around while Bartak developed their 
foundation.

> For further playing, the other one should take a bit longer to run:
> http://www.omegajunior.net/code/sumbrero/sixbythree.html

I have not yet found a sixbythree in a newspaper. At some point the
algorithm should degenerate.

-marcel

[toc] | [prev] | [next] | [standalone]

#10254

mhx@iae.nl (Marcel Hendrix) writes Subject: Re: Sumbrero puzzle solver
[..]
>> Reducing the solution space is a core topic in constraint programming.
>> see f.ex.
>> http://kti.ms.mff.cuni.cz/~bartak/constraints/index.html

> I learned a few interesting things there. Unfortunately/amazingly these
> codes all seem to be proprietary.
[..]

MINION isn't proprietary, is very good (at most 200x slower than handcoded), 
and has a very easy to understand syntax.  

-marcel

-- ----------------------
MINION 3

**VARIABLES**

BOUND a {1..9}
BOUND b {1..9}
BOUND c {1..9}
BOUND d {1..9}
BOUND e {1..9}
BOUND f {1..9}
BOUND g {1..9}
BOUND h {1..9}
BOUND i {1..9}
BOUND j {1..9}
BOUND k {1..9}
BOUND l {1..9}
BOUND m {1..9}
BOUND n {1..9}
BOUND o {1..9}

**SEARCH** 

PRINT [ [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o] ]

**CONSTRAINTS**

sumgeq([a,d], 4)
sumleq([a,d], 4)
alldiff([a,d])

sumgeq([b,e,g,j], 10)
sumleq([b,e,g,j], 10)
alldiff([b,e,g,j])

sumgeq([c,f,h,k,m], 26)
sumleq([c,f,h,k,m], 26)
alldiff([c,f,h,k,m])

sumgeq([i,l,n], 14)
sumleq([i,l,n], 14)
alldiff([i,l,n])

sumgeq([b,f,i], 7)
sumleq([b,f,i], 7)
alldiff([b,f,i])

sumgeq([a,e,h,l,o], 19)
sumleq([a,e,h,l,o], 19)
alldiff([a,e,h,l,o])

sumgeq([d,g,k,n], 14)
sumleq([d,g,k,n], 14)
alldiff([d,g,k,n])

sumgeq([j,m], 13)
sumleq([j,m], 13)
alldiff([j,m])

sumgeq([a,b,c], 6)
sumleq([a,b,c], 6)
alldiff([a,b,c])

sumgeq([d,e,f], 7)
sumleq([d,e,f], 7)
alldiff([d,e,f])

sumgeq([g,h,i], 10)
sumleq([g,h,i], 10)
alldiff([g,h,i])

sumgeq([j,k,l], 18)
sumleq([j,k,l], 18)
alldiff([j,k,l])

sumgeq([m,n,o], 14)
sumleq([m,n,o], 14)
alldiff([m,n,o])

**EOF**

C:\minion\minion-0.12\bin>minion sumbrero5x3.minion
# Minion Version 0.12
# Git version: 65512633daee570de1fdf16a0025d919f6f3753e
# Git last changed date: Mon Feb 8 17:33:56 2010 +0000
# Run at: UTC Tue Mar 20 21:57:52 2012

# http://minion.sourceforge.net
# Minion is still very new and in active development.
# If you have problems with Minion or find any bugs, please tell us!
# Mailing list at: https://mail.cs.st-andrews.ac.uk/mailman/listinfo/mug
# Input filename: sumbrero5x3.minion
# Command line: minion sumbrero5x3.minion
Parsing Time: 0.031200
Setup Time: 0.015600
First Node Time: 0.000000
Initial Propagate: 0.000000
First node time: 0.000000
Sol: 3 1 2 1 2 4 3 5 2 4 6 8 9 4 1

Solution Number: 1
Time:0.000000
Nodes: 6

Solve Time: 0.000000
Total Time: 0.046800
Total System Time: 0.031200
Total Wall Time: 0.179000
Maximum Memory (kB): 0
Total Nodes: 6
Problem solvable?: yes
Solutions Found: 1

[toc] | [prev] | [next] | [standalone]

#10268

On 20.03.2012 19:36, Marcel Hendrix wrote:
> "A. K."<akk@nospam.org>  writes Re: Sumbrero puzzle solver
>
>> On 18.03.2012 23:00, Marcel Hendrix wrote:
>>> David Kuehling<dvdkhlng@gmx.de>   writes Re: Sumbrero puzzle solver
>
>>>>>>>>> "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/.
> [..]
>>>>> 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.
>
>> It does NOT !!
>
> What doesn't? Is this reaction aimed at David or to me?

I am sorry, no. I did not want to get at any person or at any good Forth 
solution. The reaction was aimed at the "brute force" or "million tries" 
idea. It is the obvious way to go with imperative programming languages 
like Forth.

What I was trying to say was just "Hey, there are much better algorithms 
outside the Forth realm." Eg CLP deals with clever algorithms to reduce 
the solution space BEFORE the actual search.

> I have published solutions to two kinds of sumbrero's now. Both reduce
> the problem much more than a constraint solver would/can, then solve
> the constraints rather clumsily. Whatever, I am quite sure the solution
> is much (400 times or more?) faster than, say, minion can do it.
>
> Even so, I think it is no shame to use brute force for a problem that
> yields to it, It gives much faster development than first writing a
> Prolog engine.

Classical Prolog uses an inference machine combined with a depth-first 
search engine through the combinatoric tree spanned by rules and facts.
Although you have ! (cuts) or negations to force backtracking (trim the 
tree), the search mechanism through the uncut branches still remains 
brute force.
But many real-world problems "suffer" from combinatorial explosion. So 
even with fast Prlog engines it would take astronimical time to solve 
the goal.

>> Reducing the solution space is a core topic in constraint programming.
>> see f.ex.
>> http://kti.ms.mff.cuni.cz/~bartak/constraints/index.html
>
> I learned a few interesting things there. Unfortunately/amazingly these
> codes all seem to be proprietary.

I can't speak for him, but I really doubt it. The CLP/Prolog community 
has a strong and very polite and cooperative academic background.
www.eclipseclp.org alone provides a wealth of open code.

>> How do you think that your car navigation system works? Or DNA
>> sequencing? Or flight schedulers for airports? Absolutely impossible by
>> brute force.
>
> I am sure our brains didn't sit around while Bartak developed their
> foundation.
>
>> For further playing, the other one should take a bit longer to run:
>> http://www.omegajunior.net/code/sumbrero/sixbythree.html
>
> I have not yet found a sixbythree in a newspaper. At some point the
> algorithm should degenerate.
>
> -marcel
>

That's it. This puzzle has a theoretical space of 10^18 variable 
combinations. Brute force would just generate too much CO2.  :-)

[toc] | [prev] | [next] | [standalone]

#10001

Am 10.03.2012 17:24, schrieb Marcel Hendrix:
> 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

The sombrero puzzle is a nearly trivial programming exercise for CLP(FD) 
in Prolog.

But of course, Forth is the best horse in any race...   ;-)

I would hate it too. It's like chopping wood would with a teaspoon.

[toc] | [prev] | [next] | [standalone]

#10059

On 11.03.2012 12:10, A. K. wrote:
> Am 10.03.2012 17:24, schrieb Marcel Hendrix:
>> 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
>
> The sombrero puzzle is a nearly trivial programming exercise for CLP(FD)
> in Prolog.
>
> But of course, Forth is the best horse in any race... ;-)
>
> I would hate it too. It's like chopping wood would with a teaspoon.

B-Prolog code:

###

:- initialization(main).

main :-
	Vars = [A,B,C,D,E,F,G], Vars :: 1..9,
	A+F #= 8, B+D+G #= 14, C+E #= 13,  % down
	A+D #= 3, B+E+F #= 16, C+G #= 16,  % up
	D+E #= 8, A+B+C #= 11, F+G #= 16,  % vertical
	labeling(Vars),	writeln(Vars).

###

B-Prolog Version 7.7, All rights reserved, (C) Afany Software 1994-2012.
| ?- [sumbrero].
consulting::sumbrero.pl
[1,3,7,2,6,7,9]
yes

###

Example 1 "Different numbers from 1 to 7"

:- initialization(main).
main :-
	Vars = [A,B,C,D,E,F,G], Vars :: 1..7, alldifferent(Vars),
	A+F #= 9, B+D+G #= 12, C+E #= 7,   % down
	A+D #= 4, B+E+F #= 12, C+G #= 12,  % up
	D+E #= 3, A+B+C #= 12, F+G #= 13,  % vertical
	labeling(Vars),	writeln(Vars).

B-Prolog Version 7.7, All rights reserved, (C) Afany Software 1994-2012.
| ?- [sumbrero].
consulting::sumbrero.pl
[3,4,5,1,2,6,7]
yes

[toc] | [prev] | [next] | [standalone]

#10007

In article <17111793008435@frunobulax.edu>, Marcel Hendrix <mhx@iae.nl> wrote:
>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

I seem to be able to do this almost by heart.
  b+d+g+b+e+f -f-g = 14 +16 -16 (II, V, negate IX)
  2b + d+ e =14    (combine with VII )
  b = 3
Oh jee, look at VI and IX, c and f surely are equal ...
a+c=8   d+g=11 c+e=13 a+d=3 e+c=13 c+g=16 d+e=8 a+c=8

Look we have a+c and e+c twice, and we are left with 6 variables
and 6 equation which is much more reasonable.

Good old Gauss elimination would work, and it is the first thing to
try. (My prof told me never to use matrix
inversion, because  Ax=b is better solved directly. )

>
>    Discussion
>    ----------
>    We have 7 unknowns and 9 equations. Note that the constraint says that the solution
>    must not contain numbers out of [0 9].

Note that the constraint is irrelevant. It only makes us reject
a solution in hindsight.

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

This look like the Java syndrome, killing a flie with a cannon.
The problem can be solved in less operations then needed to calculate
A'*A leave alone inspecting it.

<SNIP>

--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#10018

>>>>> "Albert" == Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>> 
>> 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)

> This look like the Java syndrome, killing a flie with a cannon.  The
> problem can be solved in less operations then needed to calculate A'*A
> leave alone inspecting it.

Maybe less operations, but it might take more code :)

In Octave (matlab, too?) you have the reverse division operator '\' for
solving systems of equations without explicitely inverting the matrix A:
to solve Ax=b you write x=A\b . (which is probably implemented via
LR-decomposition of A, then forward/backward substitution to find x).

BTW even if you save some operations, asymptotic complexity is still
O(n^3), so inversion doesn't hurt that much.

cheers,

David
-- 
GnuPG public key: http://dvdkhlng.users.sourceforge.net/dk.gpg
Fingerprint: B17A DC95 D293 657B 4205  D016 7DEF 5323 C174 7D40

[toc] | [prev] | [next] | [standalone]

#10023

Albert van der Horst albert@spenarnc.xs4all.nl wrote:

> In article <17111793008435@frunobulax.edu>, Marcel Hendrix <mhx@iae.nl>
> wrote:
>>-- ----------------------------------------
>>(*
>>     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
> 
> I seem to be able to do this almost by heart.
>   b+d+g+b+e+f -f-g = 14 +16 -16 (II, V, negate IX)
>   2b + d+ e =14    (combine with VII )
>   b = 3
> Oh jee, look at VI and IX, c and f surely are equal ...
> a+c=8   d+g=11 c+e=13 a+d=3 e+c=13 c+g=16 d+e=8 a+c=8
> 
> Look we have a+c and e+c twice, and we are left with 6 variables
> and 6 equation which is much more reasonable.
> 

And if a+d=3, they must be 1 and 2 in some order.  Not many choices left 
to examine.  (But not a general solution.)

> Good old Gauss elimination would work, and it is the first thing to
> try. (My prof told me never to use matrix
> inversion, because  Ax=b is better solved directly. )
> 

cheers   cgm

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web