Path: csiph.com!aioe.org!eternal-september.org!feeder.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Bertel Lund Hansen <gadekryds@lundhansen.dk>
Newsgroups: dk.edb.programmering
Subject: =?iso-8859-1?Q?L=F8sning_af_et_puslespil?=
Date: Tue, 9 Jan 2018 18:58:02 +0100
Organization: A noiseless patient Spider
Lines: 34
Message-ID: <tc7mx6gzlerw.dlg@lundhansen.dk>
Mime-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="1c7aef4fc41077ddb298d234f525f052"; logging-data="2124"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18WbX9fxf6PfO1faCTWQwK6bVQw9e2fJTUcM4MA4/pOkA=="
User-Agent: 40tude_Dialog/2.0.15.84
Cancel-Lock: sha1:YVXeoqlbAi21nIKtoV1XrayRPPY=
Xref: csiph.com dk.edb.programmering:58

Der findes en type puslespil hvor man skal skravere nogle felter.
Hvis opgaven f.eks. ser sådan ud:

            2   2
    |    |    |    |    |
2 |    |    |    |    |
2 |    |    |    |    |
    |    |    |    |    |

Når der kun står et 2-tal, så skal der i den pågældende række
eller søjle findes en blok på to felter og ikke andet. Hvis der
havde stået "2 1" så skulle der være en blok på 2 og en blok på 1
med mindst ét mellemrum imellem.

Så er løsningen:

            2   2
    |    |     |    |    |
2 |    | X | X |    |
2 |    | X | X |    |
    |    |     |    |    |

Jeg faldt over en opgave hvor kassen var 25*25. Jeg prøvede to
gange og løb ind i noget der ikke kunne passe. Jeg besluttede
derfor at lave et program (brute-force) der kunne løse opgaven.
Men ak, da det havde kørt en tre-fire timer, var det højeste
feltnummer der havde været pillet ved, 31 - og der er jo 625 i
alt, såeh ...

Kan man finde en metode der kan løse opgaven i mindre end
astronomisk tid?

-- 
/Bertel