Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!news.musoftware.de!wum.musoftware.de!fu-berlin.de!uni-berlin.de!not-for-mail From: David Kuehling Newsgroups: comp.lang.forth Subject: Re: Sumbrero puzzle solver Date: Sun, 11 Mar 2012 00:30:00 +0100 Lines: 95 Message-ID: <87vcmckpaf.fsf@snail.Pool> References: <17111793008435@frunobulax.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: news.uni-berlin.de i1dGvo8wv9YM25roYzK1NAYrDTOubE4DR69ip7UqAIGOuoANg= Cancel-Lock: sha1:L04pj43+fSBw9d4KHsmsp0LaaCU= User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux) Xref: csiph.com comp.lang.forth:9983 >>>>> "Marcel" == Marcel Hendrix 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