Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #9978
| From | mhx@iae.nl (Marcel Hendrix) |
|---|---|
| Subject | Sumbrero puzzle solver |
| Newsgroups | comp.lang.forth |
| Message-ID | <17111793008435@frunobulax.edu> (permalink) |
| Date | 2012-03-10 18:24 +0200 |
| Organization | Wanadoo |
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 *)
Back to comp.lang.forth | Previous | Next — 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