Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > dk.edb.programmering > #58 > unrolled thread

Løsning af et puslespil

Back to article view | Back to dk.edb.programmering

Contents

  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

#58 — Løsning af et puslespil

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

[toc] | [next] | [standalone]

#74

On Tuesday, January 9, 2018 at 6:58:03 PM UTC+1, Bertel Lund Hansen wrote:


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

Det lyder som en opgave for Prolog.


        Jesper.

[toc] | [prev] | [standalone]

Back to top | Article view | dk.edb.programmering

csiph-web