Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #10214
| From | mhx@iae.nl (Marcel Hendrix) |
|---|---|
| Subject | Re: Sumbrero puzzle solver |
| Newsgroups | comp.lang.forth |
| Message-ID | <56030316008435@frunobulax.edu> (permalink) |
| Date | 2012-03-19 00:00 +0200 |
| References | <878vj6epth.fsf@snail.Pool> |
| Organization | Wanadoo |
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
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