Løsning af et puslespil

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	Løsning 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> (permalink)
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

Show key headers only | View raw

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

Back to dk.edb.programmering | Previous | Next — Next in thread | Find similar

Thread

Løsning af et puslespil Bertel Lund Hansen <gadekryds@lundhansen.dk> - 2018-01-09 18:58 +0100
  Re: Løsning af et puslespil jesper.quorning@gmail.com - 2019-03-09 06:02 -0800

csiph-web