---

Dindes der en metode til at lave en kakuro, der har netop en løsning?

Jeg har spekuleret lidt over problemet, og jeg kan ikke helt
gennemskue om man kan lave sådan en opgave bottom-up med noget
constraint-baseret programmering.

Det jeg gerne vil undgå er at lave noget hvor der er mere end en
korrekt løsning, som f. eks det trivelt simple tilfælde nedenfor, hvor
både {{1,3},{3,1}} og {{3,1},{1,3}} er en korrekt løsning.

+---+---+---+
|\ |\ |\ |
| \ | \ | \ |
| \|4 \|4 \|
+---+---+---+
|\ 4| | |
| \ | | |
| \| | |
+---+---+---+
|\ 4| | |
| \ | | |
| \| | |
+---+---+---+

Jeg har overvejet at løse problemet ved at udfylde tilfældigt
genererede grids, regne totalerne ud, og så bagefter se om de kan
løses uden brug af brute-force metoder. Men spørgsmålet er om det er
en synderligt farbar vej. Det er jo NP-land vi bevæger os i, så jeg er
noget i tvivl om hvorvidt der vil være for mange fejlskud med den
metode.

--
/Wegge

---

Anders Wegge Keller <wegge@wegge.dk> writes:

> Dindes der en metode til at lave en kakuro, der har netop en løsning?

Hvis jeg har en Kakuro og kender en løsning, findes der så en hurtig
metode til at undersøge om denne løsning er unik? Hvis vi kan opfinde
sådan en metode, så kan vi bruge måske den til at konstruere kakuroer.

0) Start med at konstruere en meget simpel kakuro (med løsning). Gem
kakuroens løsning i en vaiabel x.

1) Tilføj en lille ændring til, x, så du får en nu kakuro-løsning, y.

2) Konstruer den kakuro der har løsningen y og kald den k.

3) Hvis y er en unik løsning til k, så gem y i variabelen, x.

4) Goto 1.


Jeg kan ikke på stående fod finde en algoritme der fortæller mig om en
Kakuro-løsning er unik, men derudover synes jeg at metoden burde
virke.

Husk at skrive her i gruppen du finder en algoritme der virker :)

Niels

---

niels.ellegaard@gmail.com (Niels L. Ellegaard) writes:

> Anders Wegge Keller <wegge@wegge.dk> writes:
>
>> Dindes der en metode til at lave en kakuro, der har netop en løsning?

> Hvis jeg har en Kakuro og kender en løsning, findes der så en hurtig
> metode til at undersøge om denne løsning er unik? Hvis vi kan
> opfinde sådan en metode, så kan vi bruge måske den til at konstruere
> kakuroer.

Der findes et subset, hvor løsningen kan findes ved at udelukke
umulige tal, og ad den vej arbejde sig frem til løsningen. Eftersom
det subset er det mest behagelige at arbejde med, når man løser dem,
er jeg indstillet på kun at producere denne type. Her vil jeg mene at
man kan kode sig frem til at finde en løsning på mindre end et sekund.

> 0) Start med at konstruere en meget simpel kakuro (med løsning). Gem
> kakuroens løsning i en vaiabel x.
>
> 1) Tilføj en lille ændring til, x, så du får en nu kakuro-løsning, y.
>
> 2) Konstruer den kakuro der har løsningen y og kald den k.
>
> 3) Hvis y er en unik løsning til k, så gem y i variabelen, x.
>
> 4) Goto 1.

Mener du start med en L-formet ting, hvor summerne er hhv. 3 og 4, og
så arbejde sig videre derfra, ved at tilføje et nyt tal i en eler
anden retning, til den har den passende størrelse?

> Jeg kan ikke på stående fod finde en algoritme der fortæller mig om
> en Kakuro-løsning er unik, men derudover synes jeg at metoden burde
> virke.

> Husk at skrive her i gruppen du finder en algoritme der virker :)

Jeg har fundet noget, der ihvertfald peger i en brugbar retning her:

<http://www.grosse.is-a-geek.com/kaklets01.html#cw>

--
/Wegge

---

Anders Wegge Keller <wegge@wegge.dk> writes:

> Mener du start med en L-formet ting, hvor summerne er hhv. 3 og 4, og
> så arbejde sig videre derfra, ved at tilføje et nyt tal i en eler
> anden retning, til den har den passende størrelse?

Jeg havde forestillet mig noget i følgende retning:

Du kan repræsentere din kakuro-løsning med et 8x8 array, hvor ethvert
element har en værdi mellem 1 og 9 eller værdien null. Null betyder at
man ikke skal skrive et tal i feltet. Man kan initialisere arrayet ved
at sætte alle felterne til null. Gentag nu følgende skridt mange gange

Vælg et tilfældigt felt i dit 8x8-array.
Skriv et tal mellem 1 og 9 (eller null) i feltet.
Check at den nye løsningen er lovlig (Eks. 1+1 er ikke en lovlig sum)
Hvis den nye løningen lovlig check at den er unik.
Hvis den nye løsning også er unik så er den fin
goto start

Metoden kan sikkert gøres hurtigere, men i første omgang er det vel OK,
hvis at bare virker.

> Der findes et subset, hvor løsningen kan findes ved at udelukke
> umulige tal, og ad den vej arbejde sig frem til løsningen. Eftersom
> det subset er det mest behagelige at arbejde med, når man løser dem,
> er jeg indstillet på kun at producere denne type. Her vil jeg mene at
> man kan kode sig frem til at finde en løsning på mindre end et sekund.

Så er du jo snart færdig. Jeg glæder mig til at se din løsning :)

Niels

---

niels.ellegaard@gmail.com (Niels L. Ellegaard) writes:


> Vælg et tilfældigt felt i dit 8x8-array. Skriv et tal mellem 1 og 9
> (eller null) i feltet. Check at den nye løsningen er lovlig
> (Eks. 1+1 er ikke en lovlig sum) Hvis den nye løningen lovlig check
> at den er unik. Hvis den nye løsning også er unik så er den fin
> goto start

Det er nødvendigt at starte med 3 udfyldte felter i en vinkel, hvis
den algoritme skal overleve mere end første gennemløb. Det er i sagens
natur umuligt at afgøre rækkefølgen af to tal, når man kun har deres
sum, hvorfor placeringen af det andet tal altid vil ende med en
ikke-unik opgave.

--
/Wegge

---

Anders Wegge Keller <wegge@wegge.dk> writes:

> niels.ellegaard@gmail.com (Niels L. Ellegaard) writes:
>
>
>> Vælg et tilfældigt felt i dit 8x8-array. Skriv et tal mellem 1 og 9
>> (eller null) i feltet. Check at den nye løsningen er lovlig
>> (Eks. 1+1 er ikke en lovlig sum) Hvis den nye løningen lovlig check
>> at den er unik. Hvis den nye løsning også er unik så er den fin
>> goto start
>
> Det er nødvendigt at starte med 3 udfyldte felter i en vinkel, hvis
> den algoritme skal overleve mere end første gennemløb. Det er i sagens
> natur umuligt at afgøre rækkefølgen af to tal, når man kun har deres
> sum, hvorfor placeringen af det andet tal altid vil ende med en
> ikke-unik opgave.

Hov det har du ret i. Jeg glemte at en kokuro-opgavestiller ikke
nævner summen på rækker, der kun indeholder et enkelt tal.

Måske kan man initialisere systemet ved at placere en masse øer, der
hver især består af tre tal i vinkel. Hvis disse øerne er let
adskilte, så er man sikker på at løsningen stadig er unik. (Til
gengæld ser det lidt dumt ud hvis programmet ender med at generere en
kokuro hvor talfelterne ikke er sammenhængende, så det bliver man nødt
til at checke for).

Det kan også være at man kan finde på en smartere metode til at skabe
et kokuro-løsningsforslag på baggrund af et andet. Det må være let at
undgå at kokuro-løsninger der indeholder øer der kun består af et
enkelt tal, men jeg ved ikke om den ide kan generaliseres på en smuk
og enkel måde.

I princippet burde man huske alle mellemregningerne hver gang man
checker om en løsning er unik. Måske kan man bruge disse
mellemregninger når man genererer en nye løsninger. Det kan sikkert
blive enormt smart, men det bliver også noget bøvl at programmere.

Niels

---

niels.ellegaard@gmail.com (Niels L. Ellegaard) writes:

> Anders Wegge Keller <wegge@wegge.dk> writes:

>> Det er nødvendigt at starte med 3 udfyldte felter i en vinkel, hvis
>> den algoritme skal overleve mere end første gennemløb. Det er i sagens
>> natur umuligt at afgøre rækkefølgen af to tal, når man kun har deres
>> sum, hvorfor placeringen af det andet tal altid vil ende med en
>> ikke-unik opgave.

> Måske kan man initialisere systemet ved at placere en masse øer, der
> hver især består af tre tal i vinkel. Hvis disse øerne er let
> adskilte, så er man sikker på at løsningen stadig er unik. (Til
> gengæld ser det lidt dumt ud hvis programmet ender med at generere
> en kokuro hvor talfelterne ikke er sammenhængende, så det bliver man
> nødt til at checke for).


Jeg tror den revidere udgave skal se sådan ud:

1. Vælg en tilfældig af de forudberegnede unikke 2x2 løsninger.
2a. Find et tilfældigt felt, der er nabo til et allerede udfyldt felt,
som kun har en udfyldt nabo.
2b. Find et tilfældigt felt, der er nabo til et allerede udfyldt felt.
3. Indsæt en tilfældig værdi her, og check om der er en algoritmisk løsning.
...

Pointen med 2a og 2b, er at undgå at lave opgaver, hvor der kommer
til at stå mere end et tal i en blindgyde. Jeg har ikke prøvet at se
hvad der sker ved det, så jeg er ikke helt sikker på at det er en
gangbar vej, men jeg tror det er det bedste bud i første omgang.

> Det kan også være at man kan finde på en smartere metode til at
> skabe et kokuro-løsningsforslag på baggrund af et andet. Det må være
> let at undgå at kokuro-løsninger der indeholder øer der kun består
> af et enkelt tal, men jeg ved ikke om den ide kan generaliseres på
> en smuk og enkel måde.

Den side jeg tidligere linkede til angriber problemet fra den
modsatte side, ved at starte med en tom opgave, og så fylde den
ud. Udfyldningsalgoritmen er så vidt jeg kan se baseret på at finde en
værdi til et felt, der giver en entydig sum, som f. eks. "1.." ->
"123" og "...." -> "2345". Begge tilfælde giver en sum der kun har en
mulig kombination af tal med sig. Om den metode er mere gangbar
(bortset fra at opgaverne er pænere at se på, når de er
rotationssymmetriske), har jeg ikke lige overblik over pt.

> I princippet burde man huske alle mellemregningerne hver gang man
> checker om en løsning er unik. Måske kan man bruge disse
> mellemregninger når man genererer en nye løsninger. Det kan sikkert
> blive enormt smart, men det bliver også noget bøvl at programmere.

Bare en 3x3 med et hul i midten bliver til 9483264 forskellige
muligheder, så det ender ret hurtigt med nogle astronomiske
datamængder der skal håndteres.

--
/Wegge

---

Anders Wegge Keller <wegge@wegge.dk> writes:
> Den side jeg tidligere linkede til angriber problemet fra den
> modsatte side, ved at starte med en tom opgave, og så fylde den
> ud. Udfyldningsalgoritmen er så vidt jeg kan se baseret på at
> finde en værdi til et felt, der giver en entydig sum, som
> f. eks. "1.." -> "123" og "...." -> "2345". Begge tilfælde giver en
> sum der kun har en mulig kombination af tal med sig. Om den metode
> er mere gangbar (bortset fra at opgaverne er pænere at se på, når
> de er rotationssymmetriske), har jeg ikke lige overblik over pt.

Hmm.. ved nærmere eftertanke så har du måske ret i at Grosses metode
er den smarteste. Når man først har implementeret hans Kokuro-løser,
så må det være forholdsvis let også at forstætte med at impementere
hans kokuro-generator.

Jeg tror at jeg vil nøjes med at trække i land, og gentage linket til
hans side til glæde for google :)

http://www.grosse.is-a-geek.com/kaklets01.html#cw

Niels

---

Anders Wegge Keller <wegge@wegge.dk> wrote in
news:8763i5fz5f.fsf@huddi.jernurt.dk:

> Dindes der en metode til at lave en kakuro, der har netop en løsning?
>
Prøv at kikke her:
http://www.experiencefestival.com/sudoku_-_construction/articleindex

Hilsen
Leif F

---

Leif Frandsen <frandsen@stofanet.dk> writes:

> Anders Wegge Keller <wegge@wegge.dk> wrote in
> news:8763i5fz5f.fsf@huddi.jernurt.dk:
>
>> Dindes der en metode til at lave en kakuro, der har netop en løsning?
>>
> Prøv at kikke her:
> http://www.experiencefestival.com/sudoku_-_construction/articleindex

Der står ikke noget om kakuro der...

--
/Wegge