Bertel Lund Hansen
2018-01-09 17:58:02 UTC
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?
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
/Bertel