Løsning af et puslespil

From	Bertel Lund Hansen <gadekryds@lundhansen.dk>
Newsgroups	dk.edb.programmering
Subject	Løsning af et puslespil
Date	2018-01-09 18:58 +0100
Organization	A noiseless patient Spider
Message-ID	<tc7mx6gzlerw.dlg@lundhansen.dk> (permalink)

Show all headers | 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