Tämä ohjelma ratkaisee sudoku-pelin.
Sudokun säännöt:
Täytä kaikki ruudut numeroilla 1-9 siten, että jokaisella pystyrivillä sekä vaakarivillä on numerot 1-9. myös yhdeksän 3*3 ruudun pitää sisältää kaikki numerot 1-9.,
Esimerkkikuva: http://www.hindu.com/thehindu/sudoku/sudokusamq.jpg
HUOM! Muistakaa ottaa pois tuo "*** sudoku.txt" kohta. ohjelma lukee kaikki tarvittavat tiedot, joten se lukee vaan tuon yhden kentän, siispä sen alapuolelle voi laittaa useampia kenttiä muistiin.
sudoku.txt
5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9 tästä eteenpäin ohjelma ei enää lue. Tässä on esimerkkikuvan alkutilanne. 8 1 0 0 0 0 7 0 3 0 0 0 6 0 7 0 0 8 9 0 2 3 1 0 6 0 0 0 4 0 0 7 0 5 6 0 0 0 7 9 0 1 2 0 0 0 6 3 0 4 0 0 9 0 0 0 4 0 9 2 1 0 6 6 0 0 5 0 4 0 0 0 7 0 8 0 0 0 0 5 9
#include <iostream> // output
#include <fstream> //lukemista varten
#include <time.h>
int start_time;
using namespace std;
int i, ii, x, y, x2, y2, i2, var1, var2;
int guesses=0;
int advanced=0;
int loops=0;
class RUUTU // luokka yhdelle pienelle ruudulle
{
public:
bool vaih[10];
short int num;
bool is;
int OnePoss() // jos on vain yksi numerovaihtoehto, OnePoss() palauttaa numeron 1-9
{ // jos on monta, OnePoss() palauttaa 0.
short int thenum=0;
for(i=1;i<10;i++) // montako vaihtoehtoa?
{
if(vaih[i])
thenum++;
}
if(thenum==1) // jos yksi vaihtoehto, niin katsotaan mikä
{
for(i=1;i<10;i++)
{
if(vaih[i])
{
thenum=i;
break;
}
}
}
else thenum=0;
return thenum; // palautetaan numero, joka tulee olemaan tässä ruudussa.
}
};
class SUDOKU // luokka sudoku kentälle
{
public:
RUUTU original[9][9], numero[9][9], numero2[9][9]; // kentät
SUDOKU(short int taulukko[9][9]) // on init..
{
for(x=0;x<9;x++)
for(y=0;y<9;y++)
{
numero[x][y].num=taulukko[x][y]; // annetaan tiedot kenttään
original[x][y].num=numero[x][y].num;
for(i=0;i<10;i++) // laitetaan kaikki numerot mahdolliseksi
numero[x][y].vaih[i]=true;
if(numero[x][y].num==0) // jos numero valmiina, is=true
numero[x][y].is=false;
else
numero[x][y].is=true;
}
}
bool See(short int x, short int y, short int i) // jos 3*3 ruudussa tai pysty tai vaaka viivalla on
{ // numero i, niin palautetaan true
short int x2, y2;
short int place_x, place_y;
y2=y;
for(x2=0;x2<9;x2++) // vaakaviiva
{
if(numero[x2][y2].num==i)
return true;
}
x2=x;
for(y2=0;y2<9;y2++) // pystyviiva
{
if(numero[x2][y2].num==i)
return true;
}
place_x=(short int)((double) x / 3.0);
place_y=(short int)((double) y / 3.0);
for(x2=0;x2<3;x2++) // ruudukko
for(y2=0;y2<3;y2++)
{
if(numero[place_x*3+x2][place_y*3+y2].num==i)
return true;
}
return false;
}
int SeeTwoChanges(short int x, short int y, short int *x_v, short int *y_v, short int *x2_v, short int *y2_v)
{
short int x2, y2;
short int counter;
short int i;
bool one=false;
short int vaihs[10];
for(i=0;i<10;i++)
vaihs[i]=0;
NoGuessing();
for(i=1;i<10;i++)
{
for(y2=0;y2<3;y2++)
for(x2=0;x2<3;x2++) // ruudukko
{
if(numero[x*3+x2][y*3+y2].is==false && numero[x*3+x2][y*3+y2].vaih[i]==true)
{
vaihs[i]+=numero[x*3+x2][y*3+y2].vaih[i];
}
}
}
for(i=1;i<10;i++)
{
if(vaihs[i]==2)
{
for(x2=0;x2<3;x2++) // ruudukko
for(y2=0;y2<3;y2++)
{
if(numero[x*3+x2][y*3+y2].vaih[i]==true &&
numero[x*3+x2][y*3+y2].is==false)
{
if(one)
{
*x2_v=x*3+x2;
*y2_v=y*3+y2;
return i;
}
else
{
*x_v=x*3+x2;
*y_v=y*3+y2;
one=true;
}
}
}
}
}
return 0;
}
bool OnlyPlace(short int o_x, short int o_y, short int o_i)
{
if(numero[o_x][o_y].vaih[o_i]==false)
return false;
short int place_x, place_y;
place_x=(short int)((double) o_x / 3.0);
place_y=(short int)((double) o_y / 3.0);
short int counter=0;
for(x2=0;x2<3;x2++)
for(y2=0;y2<3;y2++)
{
if(numero[place_x*3+x2][place_y*3+y2].vaih[o_i]==true &&
numero[place_x*3+x2][place_y*3+y2].is==false)
{
counter++;
}
}
if(counter==1)
return true;
else
return false;
}
bool AdvancedClear(int vaaka, int pysty, int num)
{
bool changed=false;
short int place_x=(short int)((double) vaaka / 3.0);
short int place_y=(short int)((double) pysty / 3.0);
for(x=0;x<3;x++)
for(y=0;y<3;y++)
{
if(numero[place_x*3+x][place_y*3+y].vaih[num]==true &&
numero[place_x*3+x][place_y*3+y].is==false &&
!(place_x*3+x==vaaka && place_y*3+y==pysty))
{
numero[place_x*3+x][place_y*3+y].vaih[num]=false;
changed=true;
}
}
if(changed)
return true;
return false;
}
bool AdvancedSolving()
{
int num, vaaka, pysty, counter;
int mnum, mvaaka, mpysty;
bool changes=false;
for(num=1;num<10;num++)
{
for(vaaka=0;vaaka<9;vaaka++) //PYSTY
{
counter=0;
for(pysty=0;pysty<9;pysty++)
{
if(See(vaaka, pysty, num) || numero[vaaka][pysty].is)
continue;
counter++;
mpysty=pysty;
}
if(counter==1)
{
advanced++;
if(AdvancedClear(vaaka, mpysty, num))
changes=true;
}
}
for(pysty=0;pysty<9;pysty++) //VAAKA
{
counter=0;
for(vaaka=0;vaaka<9;vaaka++)
{
if(See(vaaka, pysty, num) || numero[vaaka][pysty].is)
continue;
counter++;
mvaaka=vaaka;
}
if(counter==1)
{
if(AdvancedClear(mvaaka, pysty, num))
changes=true;
}
}
}
if(changes)
return true;
return false;
}
void NoGuessing()
{
short int x, x2, y, y2;
bool changes;
while(changes) // looppi
{
loops++;
changes=false;
for(x=0;x<9;x++) // käydään kaikki ruudut läpi
for(y=0;y<9;y++)
{
if(numero[x][y].is==false) // jos ruudussa ei ole numeroa vielä
{
if(numero[x][y].OnePoss()>0) // jos on vain yksi vaihtoehto ruutuun
{
numero[x][y].num=numero[x][y].OnePoss(); // laitetaan varmasti oikea numero ruutuun
numero[x][y].is=true; // ja kerrotaan, että ruudussa on numero
changes=true; // jotain on tapahtunut
}
for(i=1;i<10;i++) // ainoa paikka tälle numerolle
{
if(OnlyPlace(x, y, i)==true && See(x, y, i)==false)
{
numero[x][y].num=i;
numero[x][y].is=true;
changes=true;
break;
}
}
for(i=1;i<10;i++) // käydään kaikki vaihtoehtoiset numerot läpi
{
if(numero[x][y].vaih[i]==true) // jos tämä numero i on mahdollista laittaa kohtaan x, y
{
if(See(x, y, i)) // onko samassa 3*3 ruudussa tai vaaka tai pysty rivissä numeroa i
{
numero[x][y].vaih[i]=false; // oletetaan tämä numero mahdottomaksi tähän ruutuun
changes=true; // jotain on tapahtunut
}
}
}
}
}
if(!changes)
{
if(AdvancedSolving())
changes=true;
}
}
}
bool SearchPair(short int *x, short int *x2, short int *y, short int *y2, short int *i)
{
short int fx, fy, fi;
short int x3, y3, x4, y4;
for(fx=0;fx<3;fx++)
for(fy=0;fy<3;fy++)
{
// for 3*3, palauttaa 2 x ja y:n arvoa. uus systeemi STC:ssä...
if(numero[fx][fy].is==false)
{
fi=SeeTwoChanges(fx, fy, &x3, &y3, &x4, &y4);
*x=x3;
*y=y3;
*i=fi;
*x2=x4;
*y2=y4;
if(fi>0 && fi<10)return true;
}
}
return false;
}
bool GuessSolveLoop()
{
short int x, x2, y, y2, i;
short int forx, fory, fori;
short int random = rand()%2;
if(SearchPair(&x, &x2, &y, &y2, &i))
{
if(random==0)
{
numero[x][y].num=i;
numero[x][y].is=true;
}
else
{
numero[x2][y2].num=i;
numero[x2][y2].is=true;
}
guesses++;
NoGuessing();
if(Check())
return 1;
if(FakeCheck())
{
if(GuessSolveLoop())
return 1;
}
for(forx=0;forx<9;forx++)
for(fory=0;fory<9;fory++)
{
numero[forx][fory].num=numero2[forx][fory].num;
numero[forx][fory].is=numero2[forx][fory].is;
for(fori=0;fori<10;fori++)
numero[forx][fory].vaih[fori]=numero2[forx][fory].vaih[fori];
}
}
return 0;
}
void Guessing(int ms)
{
short int x, x2, y, y2, i;
short int forx, fory, fori;
if(SearchPair(&x, &x2, &y, &y2, &i))
{
for(forx=0;forx<9;forx++)
for(fory=0;fory<9;fory++)
{
numero2[forx][fory].num=numero[forx][fory].num;
numero2[forx][fory].is=numero[forx][fory].is;
for(fori=0;fori<10;fori++)
numero2[forx][fory].vaih[fori]=numero[forx][fory].vaih[fori];
}
if(FakeCheck())
{
while(clock()<start_time+ms)
{
guesses=0;
if(GuessSolveLoop())
return;
}
}
}
return;
}
void Solve() // ratkaistaan sudoku
{
short int x, x2, y, y2;
bool changes=false;
if(!Check())
{
printf("Solving...
");
NoGuessing();
}
if(!Check())
{
printf("Guessing numbers...
");
Guessing(3000);
}
printf("
");
return;
}
bool Check() // katsotaan, onko sudoku ratkaistu
{
int check[10];
int var;
for(x=0;x<9;x++) // jos ei ole kaikkia laitettu, ei sudoku ole ratkaistu
for(y=0;y<9;y++)
if(numero[x][y].is==false)return false;
for(y=0;y<9;y++) // vaakatarkistus
{
for(i=0;i<9;i++)
check[i]=0;
for(x=0;x<9;x++)
{
check[numero[x][y].num]=true;
}
for(i=1;i<10;i++)
{
if(check[i]==false)
return false;
}
}
for(x=0;x<9;x++) // pystytarkistus
{
for(i=0;i<9;i++)
check[i]=0;
for(y=0;y<9;y++)
{
check[numero[y][x].num]=true;
}
for(i=1;i<10;i++)
{
if(check[i]==false)
return false;
}
}
for(i=0;i<3;i++) //3*3 ruututarkistus
for(ii=0;ii<3;ii++)
{
for(x=0;x<9;x++)
check[x]=0;
for(y=0;y<3;y++)
for(x=0;x<3;x++)
{
check[numero[x+i*3][y+ii*3].num]=true;
}
for(x=1;x<10;x++)
{
if(check[x]==false)
return false;
}
}
return true;
}
bool FakeCheck() // katsotaan, onko sudoku ratkaistu
{
int x, y, i;
int check[10];
int var;
for(y=0;y<9;y++) // vaakatarkistus
{
for(i=0;i<10;i++)
check[i]=0;
for(x=0;x<9;x++)
{
check[numero[x][y].num]++;
}
for(i=1;i<10;i++)
{
if(check[i]>1)
return false;
}
}
for(x=0;x<9;x++) // pystytarkistus
{
for(i=0;i<10;i++)
check[i]=0;
for(y=0;y<9;y++)
{
check[numero[x][y].num]++;
}
for(i=1;i<10;i++)
{
if(check[i]>1)
return false;
}
}
for(i=0;i<3;i++) //3*3 ruututarkistus
for(ii=0;ii<3;ii++)
{
for(x=0;x<10;x++)
check[x]=0;
for(x=0;x<3;x++)
for(y=0;y<3;y++)
{
check[numero[x+i*3][y+ii*3].num]++;
}
for(x=1;x<10;x++)
{
if(check[x]>2)
return false;
}
}
return true;
}
void Print() // tuloksen tulostus
{
for(ii=0;ii<9;ii++) //rivit
{
for(i=0;i<9;i++) //ratkaistu
{
if(numero[i][ii].num!=0)
cout << numero[i][ii].num << " ";
else
cout << "- ";
if(i%3==2)cout << " ";
}
cout << " ";
for(i=0;i<9;i++) //ratkaisematon
{
if(original[i][ii].num!=0)
cout << original[i][ii].num << " ";
else
cout << "- ";
if(i%3==2)cout << " ";
}
cout << endl;
if(ii%3==2)cout << endl;
}
return;
}
void PrintVaih() // tuloksen tulostus
{
for(ii=0;ii<9;ii++) //rivit
{
for(i=0;i<9;i++) //ratkaistu
{
for(x=1;x<10;x++)
{
cout << numero[i][ii].vaih[x];
}
if(i%3==2)cout << " ";
else
cout << " ";
}
cout << endl;
if(ii%3==2)cout << endl;
}
return;
}
};
void Read(short int taulukko[9][9]) // luetaan kenttä tiedostosta sudoku.txt
{
ifstream read;
read.open("sudoku.txt");
for(y=0;y<9;y++)
for(x=0;x<9;x++)
{
read >> taulukko[x][y];
}
read.close();
}
int main()
{
srand(time(NULL));
start_time=clock();
short int taulukko[9][9]; //tehdään taulukko, jolla annetaan alkutilanne
Read(taulukko); //luetaan alkutilanne
SUDOKU Sudoku(taulukko); //tehdään sudokukenttä
Sudoku.Solve(); //ratkaistaan kenttä
Sudoku.Print(); //tulostetaan ratkaistu ja ratkaisematon kenttä
if(Sudoku.Check())
{
printf("
Solved!
");
printf("Info:
-Time: %dms
-Guesses: %d
-Advanced moves: %d
-Solving loops: %d
",
clock(), guesses, advanced, loops);
int taso=0;
taso+=guesses*30;
taso+=advanced*15;
taso+=loops;
if(taso>100)
printf("-Difficulty: Impossible (%d)
", taso);
else if(taso>30)
printf("-Difficulty: Hard (%d)
", taso);
else if(taso>10)
printf("-Difficulty: Medium (%d)
", taso);
else
printf("-Difficulty: Easy (%d)
", taso);
ofstream write("solution.txt");
write << "Original:
";
for(ii=0;ii<9;ii++) //rivit
{
for(i=0;i<9;i++) //ratkaistu
{
if(Sudoku.original[i][ii].num!=0)
write << Sudoku.original[i][ii].num << " ";
else
write << "0 ";
if(i%3==2)write << " ";
}
write << endl;
if(ii%3==2)write << endl;
}
write << "
Solved:
";
for(ii=0;ii<9;ii++) //rivit
{
for(i=0;i<9;i++) //ratkaistu
{
if(Sudoku.numero[i][ii].num!=0)
write << Sudoku.numero[i][ii].num << " ";
else
write << "- ";
if(i%3==2)write << " ";
}
write << endl;
if(ii%3==2)write << endl;
}
}
else
printf("
Unsolved!
");
system("PAUSE");
return 0;
}Oletko kokeillut osaako tuo ratkaista kaikki vaikeimmat sudoku tehtävät joita löytyy esim lehdistä tms?
Ei osaa ratkaista läheskään kaikkia, se käyttää ratkaisuun vain kaikkein simppeleintä metodia: jos ruutuun voi laittaa vain yhden luvun, se laittaa sen luvun ruutuun. Harvat Sudokut ratkeavat pelkästään tällä metodilla.
Esimerkiksi tästä tämä solveri ei sano mitään:
3 0 7 0 4 0 0 0 0 0 0 0 0 0 0 0 9 1 8 0 0 0 0 0 0 0 0 4 0 0 0 0 0 7 0 0 0 0 0 1 6 0 0 0 0 0 0 0 2 5 0 0 0 0 0 0 0 0 0 0 3 8 0 0 9 0 0 0 0 5 0 0 0 2 0 6 0 0 0 0 0
Vaikka tälle löytyy uniikki ratkaisu, jonka esimerkiksi oma solverini löytää:
317|849|265 245|736|891 869|512|473 ---+---+--- 456|398|712 732|164|958 981|257|634 ---+---+--- 174|925|386 693|481|527 528|673|149
Koodia voisi muuttaa sen verran, että vaihtaa alun fstream.h:n fstream:ksi, heittää perään using namespace std;, ja antaa Read- ja Print-funktioille palautusarvoksi void. Kääntyisi siten ehkä useammallakin kääntäjällä ilman muokkauksia.
Ihan hieno. Deewiant mainitsikin virheet.
Okei. Nyt laitoin uusimman version ohjelmasta. tämä on ratkaissut websudoku.comin kaikki evil tasot mitkä olen kokeillut. Myös deewiantin mainitseman.
Tämä myöskin tekee tiedoston, josta on helppo kopioida tuloksen.
EDIT: Uusimpia koodeja en ole kommentoinut.
Rivinvaihdot hajonneet? Johtunee 'Putkasta, ellei kääntäjäsi syö tuollaisia katkonaisia rivejä. Jos kyse on siitä, kannattaa suosiolla vaihtaa vaikka endl-vakioon, kun kerran iostreamia käytät.
Iostreamista puheen ollen voisi printf-kutsutkin ottaa pois, turha sitä on kahta eri IO-tapaa käyttää.
Ja tuo ei muuten ratkaise tuota mainitsemaani Sudokua. Johtuu siitä, että kommentoit FakeCheck()-funktion pois. Se ulos, niin johan skulaa. Tässä eräs, jota tämä ei ratkaise edes maksimioptimoinneilla omalla koneellani tuossa 3000 ms rajassa - vähän typerää, että onnistuminen riippuu koneen nopeudesta tuon aikarajoituksen takia:
0 0 0 0 7 0 9 4 0 0 7 0 0 9 0 0 0 5 3 0 0 0 0 5 0 7 0 0 8 7 4 0 0 1 0 0 4 6 3 0 0 0 0 0 0 0 0 0 0 0 7 0 8 0 8 0 0 7 0 0 0 0 0 7 0 0 0 0 0 0 2 8 0 5 0 2 6 8 0 0 0
Ei tätä tosin omanikaan ratkaise arvaamatta. Arvaamistahan ei tosin tueta, kyllähän sillä ratkaisee minkä tahansa Sudokun. Logiikalla ne pitää tehdä ;-)
Noi rivin vaihdot taitaa olla putkan bugi, koska omalla kääntäjälläni ne ovat tavallisia välilyöntejä. En keksinyt muita tapoja ratkasta mahdollisimman monta sudokua, kuin tuo arvaaminen. Joissain paikoissa kommentit taitaa olla päin metsää, koska olen koodia kopioinut paikasta toiseen... Suokaa anteeksi.
EDIT: Missä siis olen kommentoinut traagisesti FakeCheckin pois?
Touho kirjoitti:
EDIT: Missä siis olen kommentoinut traagisesti FakeCheckin pois?
//printf("FakeCheck: %d
", (int)Sudoku.FakeCheck());Täällä Putkassa tuo ei tietenkään näy uloskommentoituna, mutta jos nuo rivinvaihdot korjataan, saadaan tällainen rivi, jossa FakeCheck():ä ei siis kutsuta:
//printf("FakeCheck: %d\n\n", (int)Sudoku.FakeCheck());lainaus:
En keksinyt muita tapoja ratkasta mahdollisimman monta sudokua, kuin tuo arvaaminen.
Jos jaksaa kiinnostaa, paras (lue: nopein - laskee kaikki mahdolliset ratkaisut kaikille Sudokuille millisekunneissa) tunnettu metodi on Donald Knuthin kehittämä Dancing Links. Nopeutensa ansiosta sitä käytetäänkin monissa Sudokugenerattoreissa, jotka tekevät Sudokuja generoimalla ruudukoita ja sitten testaavat tuolla algoritmilla, voiko sen ratkaista ja kuinka monta ratkaisua löytyy.
Ei tuo rivi vaikuta sudokun ratkaisemiseen milläänlailla. Virhe tulee luultavasti siitä, että se täällä putkassa ei kommentoi koko lauseketta vaan pelkästään puolet siitä. Koodipätkä oli vain tuon funktion testausta vasten, joten otan sen nyt pois.
Touho kirjoitti:
Ei tuo rivi vaikuta sudokun ratkaisemiseen milläänlailla.
Tarkistin koodia, ja siltä vaikuttaakin. Syy sille, miksi tämä ei välillä tee mitään, johtuu ilmeisesti kääntäjästäni (MinGW:n GCC 3.4.2). Kokeilin toista ja johan skulasi. Kummaa.
Onko se C++ muka niin hauska... Teenpä oman versioni (ups, meinasin sanoa jo)
Aihe on jo aika vanha, joten et voi enää vastata siihen.