Koodasin hienoa kudosugen-ohjelmaa. Ei toimi. Mälsää. Miksei? Alla näkyvä koodi sanoo ajettaessa ihan uppo-outoja ruudukoita. Kyseinen ohjelma tulostaa myös mitä saisi laittaa ruudukoihin, oudosti ne näyttäisivät olevan oikein, mutta numerot - eivät sinne päinkään!
main.cpp:
#include <stdio.h>
#include <iostream>
#include <ctime>
class numero {
public:
bool sopivat[9];
int itsenumero;
bool sopiiko(int n) {
return sopivat[n-1];
};
void arvoSopiva() {
int i,o[9],p=0;
for(i=1;i<10;i++) {
if(sopiiko(i)) { o[p]=i; p++; }
}
if(p<=0) itsenumero=-128;
if(p>0) itsenumero=(rand()%p)+1;
};
void sopii(int n) {
sopivat[n-1]=true;
};
void eisovi(int n) {
sopivat[n-1]=false;
};
numero() {
int i;
for(i=0;i<9;i++)
sopivat[i]=true;
itsenumero=0;
};
numero(int n) {
itsenumero=n;
int i;
for(i=0;i<9;i++)
sopivat[i]=false;
sopivat[itsenumero-1]=true;
};
~numero() {
};
};
class ruudukko {
public:
numero ruudut[9][9];
void tulosta() {
int i,o;
printf("//-----------------\\\\\n");
for(i=0;i<9;i++) {
printf("| ");
for(o=0;o<9;o++)
printf("%i ",ruudut[i][o].itsenumero);
printf("|\n");
}
printf("\\\\-----------------//\n\n");
};
void tulostaMahdollisuudet() {
int i,o,p;
printf("-----Mahdollisuudet-----\n");
for(i=0;i<9;i++) { //X!
for(o=0;o<9;o++) { //Y!
for(p=1;p<10;p++) //N!
if(ruudut[i][o].sopiiko(p))
printf("%i|",p);
else
printf("!|",p);
printf("\n");
}
}
printf("------------------------\n");
};
void hoidaDependenssit(int x,int y) {
int i;
for(i=0;i<9;i++) {
//if(i==y) continue;
//if(ruudut[x][i].itsenumero==0) continue;
ruudut[x][y].eisovi(ruudut[x][i].itsenumero);
}
for(i=0;i<9;i++) {
if(i==x) continue;
if(ruudut[i][y].itsenumero==0) continue;
ruudut[x][y].eisovi(ruudut[i][y].itsenumero);
}
};
void putsisKliindependenssit() {
int i,o;
for(i=0;i<9;i++)
for(o=0;o<9;o++)
hoidaDependenssit(i,o);
};
ruudukko() {
ruudut[0][0].itsenumero=(rand()%9)+1;
ruudut[1][3].itsenumero=(rand()%9)+1;
ruudut[2][6].itsenumero=(rand()%9)+1;
//toiset
ruudut[3][1].itsenumero=(rand()%9)+1;
ruudut[4][4].itsenumero=(rand()%9)+1;
ruudut[5][7].itsenumero=(rand()%9)+1;
//kolmannet
ruudut[6][2].itsenumero=(rand()%9)+1;
ruudut[7][5].itsenumero=(rand()%9)+1;
ruudut[8][8].itsenumero=(rand()%9)+1;
int i,o;
for(i=0;i<9;i++) {
for(o=0;o<9;o++) {
if(ruudut[i][o].itsenumero==0) ruudut[i][o].arvoSopiva();
putsisKliindependenssit();
}
}
};
~ruudukko() {
};
};
int main(int argc,char *argv[]) {
srand(time(0));
ruudukko ruutupaita = ruudukko();
ruutupaita.tulosta();
ruutupaita.tulostaMahdollisuudet();
return 0;
}Esimerkkitulostus:
//-----------------\\ | 2 1 6 1 2 1 1 5 4 | | 3 4 4 3 1 2 2 2 3 | | 2 5 3 5 4 1 2 3 1 | | 5 6 4 1 3 3 1 1 1 | | 6 4 2 1 3 4 4 3 3 | | 5 2 3 2 4 4 4 2 2 | | 1 1 7 3 1 3 1 2 2 | | 1 1 2 2 5 3 2 5 1 | | 2 3 1 5 2 1 1 2 5 | \\-----------------// -----Mahdollisuudet----- !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|!|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|3|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|5|!|!|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|5|6|7|8|9| !|!|!|!|5|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|!|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|!|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|5|!|!|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|5|!|7|8|9| !|!|!|!|5|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|!|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|4|!|!|!|8|9| !|!|!|!|!|!|!|8|9| !|!|!|!|5|!|!|8|9| !|!|!|4|!|6|!|8|9| !|!|!|!|!|6|!|8|9| !|!|!|!|5|6|!|8|9| !|!|!|!|5|6|!|8|9| !|!|!|4|!|6|!|8|9| !|!|!|!|!|6|!|8|9| !|!|!|4|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|!|8|9| !|!|!|4|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|4|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|4|!|!|7|8|9| !|!|!|!|!|!|7|8|9| !|!|!|!|!|!|!|8|9| !|!|!|4|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|!|!|6|7|8|9| !|!|!|4|!|6|7|8|9| !|!|!|!|!|6|7|8|9| ------------------------
Koodi on luultavasti selvä finglishinkielisten muuttuja(&funktio)nimien johdosta, mutta kysykää toki jos jonkin rivin tarkoitus on harmaan (tai miksei jonkin muunkin värisen) usvan peitossa. Minuahan te silloin vain autatte. ;)
if(p>0) itsenumero=(rand()%p)+1;
Ilmeisesti kuitenkin pitäisi olla näin:
if (p > 0) itsenumero = o[rand()%p];
Kaikin puolin turhan mutkikkaasti tehty... Tuo nyt oli ainoa virhe, jonka pikalukemalla huomasin.
Tuo sopiiko-taulukko kannattaisi korvata vain yhdellä luvulla, jolle tekisi bittioperaatioita. Tällöin ei tulisi virheriskiä taulukon yli osoittamisesta.
unsigned int bitit; // Yleensä 32-bittinen, siis seuraavissa monesko = 0..31
void lisaa(int monesko) {bitit |= 1 << monesko;}
void poista(int monesko) {bitit &= ~(1 << monesko);}
bool onko(int monesko) {return (bitit & (1 << monesko)) != 0;}Korjasin tuon löytämäsi lisäominaisuuden, ja ohjelma toimii muuten hyvin, mutta vaikka säädin tuohon hienon funktion jonka täytyisi käydä kaikki numerot läpi ja sitten laittaa niihin kohtiin, mihin vain yksi numero käy se tietty numero, niin tulee kymppejä (eli mikään ei käy-numeroita) tuonne...
Tässä nykyinen koodi:
main.cpp:
#include <stdio.h>
#include <iostream>
#include <ctime>
class numero {
public:
bool sopivat[9];
int itsenumero;
bool sopiiko(int n) {
if(n>9||n<1) return false;
return sopivat[n-1];
};
void paataSopiva() {
int i,o[9],p=0;
for(i=0;i<10;i++) {
if(sopiiko(i)) { o[p]=i; p++; }
}
if(p==0) itsenumero=i;
}
void arvoSopiva() {
int i,o[9],p=0;
for(i=0;i<10;i++) {
if(sopiiko(i)) { o[p]=i; p++; }
}
if(p<0) itsenumero=-128;
if(p==0) itsenumero=o[0];
if(p>0) itsenumero=o[(rand()%p)];
};
void sopii(int n) {
sopivat[n-1]=true;
};
void eisovi(int n) {
if(n>0&&n<10)
sopivat[n-1]=false;
};
numero() {
int i;
for(i=0;i<9;i++)
sopivat[i]=true;
itsenumero=0;
};
numero(int n) {
itsenumero=n;
int i;
for(i=0;i<9;i++)
sopivat[i]=false;
sopivat[itsenumero-1]=true;
};
~numero() {
};
};
class ruudukko {
public:
numero ruudut[9][9];
void tulosta() {
int i,o;
printf("//-----------------\\\\\n");
for(i=0;i<9;i++) {
printf("| ");
for(o=0;o<9;o++)
printf("%i ",ruudut[i][o].itsenumero);
printf("|\n");
}
printf("\\\\-----------------//\n\n");
};
void tulostaMahdollisuudet() {
int i,o,p;
printf("-----Mahdollisuudet-----\n");
for(i=0;i<9;i++) { //X!
for(o=0;o<9;o++) { //Y!
for(p=1;p<10;p++) //N!
if(ruudut[i][o].sopiiko(p))
printf("%i|",p);
else
printf("!|",p);
printf("\n");
}
printf("\n");
}
printf("------------------------\n");
};
void hoidaDependenssit(int x,int y) {
int i;
for(i=0;i<9;i++) {
if(i==y) continue;
if(ruudut[x][i].itsenumero==0) continue;
ruudut[x][y].eisovi(ruudut[x][i].itsenumero);
}
for(i=0;i<9;i++) {
if(i==x) continue;
if(ruudut[i][y].itsenumero==0) continue;
ruudut[x][y].eisovi(ruudut[i][y].itsenumero);
}
};
void putsisKliindependenssit() {
int i,o;
for(i=0;i<9;i++)
for(o=0;o<9;o++)
hoidaDependenssit(i,o);
};
void varma() {
int i,o;
for(i=0;i<9;i++)
for(o=0;o<9;o++)
ruudut[i][o].paataSopiva();
};
ruudukko() {
ruudut[0][0].itsenumero=(rand()%9)+1;
ruudut[1][3].itsenumero=(rand()%9)+1;
ruudut[2][6].itsenumero=(rand()%9)+1;
//toiset
ruudut[3][1].itsenumero=(rand()%9)+1;
ruudut[4][4].itsenumero=(rand()%9)+1;
ruudut[5][7].itsenumero=(rand()%9)+1;
//kolmannet
ruudut[6][2].itsenumero=(rand()%9)+1;
ruudut[7][5].itsenumero=(rand()%9)+1;
ruudut[8][8].itsenumero=(rand()%9)+1;
int i,o;
putsisKliindependenssit();
varma();
for(i=0;i<9;i++) {
for(o=0;o<9;o++) {
putsisKliindependenssit();
varma();
if(ruudut[i][o].itsenumero==0) { ruudut[i][o].arvoSopiva(); varma(); }
printf("%i %i\n",i,o);
putsisKliindependenssit();
tulosta();
tulostaMahdollisuudet();
}
}
};
~ruudukko() {
};
};
int main(int argc,char *argv[]) {
srand(time(0));
ruudukko ruutupaita = ruudukko();
ruutupaita.tulosta();
ruutupaita.tulostaMahdollisuudet();
return 0;
}Tiedä häntä. Onneksi täällä Putkassa on kuitenkin näitä guruja jotka osaavat. :)
Opettelepa itse debugaamaan. Laita arvontaan tarkistus, että jos tulee kymppi, printataan keskeneräinen ruudukko, niin pääset itse ihmettelemään. On hyvin mahdollista, että ihan oikeasti päädyt tilanteeseen, jossa mikään ei ole mahdollista.
123 456 789 687 321 45. ja 9 ei enää käy, vaikka aiemmat on arvottu "oikein"
Et muuten taida tarkistaa ollenkaan, että jokaisessa neliössä olisi vielä oikeat numerot. Ja kuten voi päätellä siitä, miten vähillä numeroilla saa aikaan sudokun, johon on vain yksi ratkaisu, niin tuo arvontahomma ei ole kovin hyvä, muutenhan ne hankalatkin sudokut ratkeaisivat tuolla aivan käden käänteessä.
Sudoku on vanhalle hyvää aivojumppaa joten tein itsekin sudoku-generaattorin mutta VB5:llä. Sitä ennen tein brute-force-periaatteella ratkaisimen, jolla ruudukko kuin ruudukko ratkeaa yleensä murto-osa sekunnissa ja kertoo myös ratkaisujen määrän jos niitä on useita. Generaattorin tein sitten kahdella eri periaatteella: 1. Arvotaan koko ruudukko ja samalla tsekataan arvotun numeron sopivuus. Tietyissä vaiheissa ei tarvi arpoa vaan löytyy vain yksi sopiva numero kuten rivin tai osaruudukon viimeinen numero. Tämä onnistui kohtuullisen helposti mutta alkunumeroiden valinta niin, että löytyy vain yksi vaikeusasteeltaan sopiva ruudukko olikin sitten ongelma. Toinen tapa oli arpoa esim. 15 numeroa ja sen jälkeen hakea satunnainen ratkaisu. Tämän jälkeen numeroita valitaan lisää kunnes saadaan vain yksi ratkaisu. Mutta edelleen vaikeusasteen saaminen sopivaksi on ongelmallinen. Vaikuttaa siltä että ongelma on muillakin koska esim. Aamulehdessä on usein 5 tähden ruudukko helpompi ratkaista kuin yhden tähden ruudukko. Oma koodini on luotu ihan vaan talonpoikaisjärjellä päättelemällä ja on melkoista purkkaa joten en liitä mukaan. Jos kiinnostaa, voin yrittää kehitellä siitä jonkinlaista pseudokoodia.
Itseasiassa uniikkien sudokujen generointi on varsin helppoa ja nopeaa kunhan vain oivaltaa oikean generointitekniikan. Noin puoli vuotta sitten huomasin sudokuja tutkiessani niissä tiettyä lineaarisuutta. Huomioni pohjalta koodasin C++:lla noin 100 rivin sudoku-generaattorin ja 300 rivin sudokuratkaisijan. Generaattorini pystyi generoimaan valinnan mukaan halutun vaikeustason mukaisia joko symmetrisiä tai epäsymmetrisiä uniikkeja sudokuja. Generaattori ja ratkaisija eivät siis käyttäneet lainkaan brute-forcea
Vinkkinä voin antaa, että kannattaa alkaa sudokujen generointi täydestä sudokusta. Kun sudokun generoi ns. käänteisessä järjestyksessä, niin säästyy monelta ongelmalta ja se on myös hyvin paljon kevyempää ja siten paljon nopeampaa koneellisesti
Hei Jtm, mitä tarkoitat käänteisellä järjestyksellä? Entä kuinka määrität vaikeusasteen? Aihe kiinnostaisi kovasti.
Tarkoitan käänteisellä generointijärjestyksellä sitä, että aloitetaan halutun sudokun generointi täydestä sudokusta ja edetään poistamalla aina yksi luku kerrallaan kunnes meillä on sopiva sudoku.
Kun sudoku generoidaan tuolla tavalla, säästytään monelta ongelmalta mitä generointi tyhjästä + numeroiden lisäys -tekniikka tuo mukanaan.
Haluttu vaikeustaso saadaan kun vaikutetaan generoinnin numeroiden poistoehtoihin tietyn vaikeustason edellyttämillä ehdoilla/säännöillä. Jos esimerkiksi vaikeustaso on helpoin, tuolloin numeroita poistettaessa otetaan huomioon, että pelaaja tarvitsee vain scannaus-tekniikkaa sudokun ratkaisussa. Toisin sanoen myös sudokun generointi vaatii jonkinlaista sudokun ratkaisijaa, jos siis halutaan tehdä täsmälleen tietyn tasoisia sudokuja.
PS. Vaikeustasot yleensä myös määräävät kuinka monta numeroa pitää jäädä jäljelle, jotta saadaan aikaiseksi haluttu vaikeustaso.
Seuraavista sivustoista löytyy useita sudokun ratkaisutapoja kuin myös muuta hyödyllistä tietoa:
http://www.angusj.com/sudoku/hints.php
http://en.wikipedia.org/wiki/Sudoku
Mutta tässähän on ideana tehdä kokonainen (ratkaistu) sudoku, ei poistaa siitä numeroita!
PC-Master, ilmeisesti sitten ymmärsin väärin koko keskustelunne. Et ilmeisesti haluakaan luoda itsellesi pelejä vaan tutkit vain täysinäisiä sudokuja? Turhaan edes puhutte sudokugeneraattorista, kun ette sellaista edes yritä tehdä.
Mutta aiheeseen. Täyden ja hyvin randomoidun sudokun luonti ei ole ongelma eikä mikään. Moinen ei vaadi lähes mitään tarkistuksia. Voit älyttömän helposti ja nopeasti generoida uuden ratkaistun sudokun edellisestä ratkaistusta sudokusta. Omassa sudokugeneraatiokoodissani se vei vain 50 riviä.
Jotta en tee kaikkea työtä puolestasi, saat luvan itse tutkia mitä seuraavalle lineaariselle ratkaistulle sudokulle tapahtuu kun sitä sekoittaa. Tuosta pitäisi huomata sekoitusehdot varsin nopeasti:
1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 4 5 6 7 8 9 1 5 6 7 8 9 1 2 3 4 8 9 1 2 3 4 5 6 7 3 4 5 6 7 8 9 1 2 6 7 8 9 1 2 3 4 5 9 1 2 3 4 5 6 7 8
Aihe on jo aika vanha, joten et voi enää vastata siihen.