 |
Cheat Engine The Official Site of Cheat Engine
|
View previous topic :: View next topic |
Author |
Message |
Santtu K Newbie cheater
Reputation: 0
Joined: 01 Mar 2008 Posts: 17
|
Posted: Sat Mar 01, 2008 4:40 am Post subject: [Release] Sudoku Solver |
|
|
Hello guys!
This is my first post and I hope its good!
So here is program I have written C++ at the bottom you can download it and here is the source for it:
I give source because, I read the rules and it say so.
It has instructions how to use.
Code: |
//koodin kirjoittanut Santtu Kerppainen
#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;
}
|
Here is the Download:
http://rapidshare.com/files/96127538/SudokuAI.zip
Last edited by Santtu K on Sat Mar 01, 2008 4:56 am; edited 1 time in total |
|
Back to top |
|
 |
AtheistCrusader Grandmaster Cheater
Reputation: 6
Joined: 23 Sep 2006 Posts: 681
|
Posted: Sat Mar 01, 2008 4:48 am Post subject: |
|
|
Nice but you should make comments english not finnish
|
|
Back to top |
|
 |
Santtu K Newbie cheater
Reputation: 0
Joined: 01 Mar 2008 Posts: 17
|
Posted: Sat Mar 01, 2008 4:56 am Post subject: |
|
|
masterkert3 wrote: | Nice but you should make comments english not finnish |
Wow you know finland and finnish? But im finnish so I put comments always in finnish...
_________________
nowadaysidoc++andasm |
|
Back to top |
|
 |
Jani Grandmaster Cheater
Reputation: 2
Joined: 29 Dec 2006 Posts: 804
|
Posted: Sat Mar 01, 2008 5:05 am Post subject: |
|
|
Stolen. Original post at http://www.ohjelmointiputka.net/koodit_nayta.php?tunnus=1498 by Touho on 18.01.2006.
And ppl are telling that this doesn't even work properly. Try eg.
Code: | 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 |
Solution:
Code: | 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 |
Santtu K wrote: | masterkert3 wrote: | Nice but you should make comments english not finnish |
Wow you know finland and finnish? But im finnish so I put comments always in finnish... | Why to post on international forums then?
Last edited by Jani on Sat Mar 01, 2008 5:10 am; edited 1 time in total |
|
Back to top |
|
 |
HolyBlah Master Cheater
Reputation: 2
Joined: 24 Aug 2007 Posts: 446
|
Posted: Sat Mar 01, 2008 5:09 am Post subject: |
|
|
Code: | 0 8 0 0 1 7 0 0 0
0 0 1 8 0 0 6 0 0
0 3 4 5 6 0 0 0 7
0 0 0 0 0 1 0 0 0
5 0 0 0 7 0 0 0 4
0 0 0 2 0 0 2 0 0
4 0 0 0 5 2 7 8 0
0 0 9 0 0 0 3 0 0
0 0 0 7 4 0 0 6 0 | Unsolved but possible.
|
|
Back to top |
|
 |
Santtu K Newbie cheater
Reputation: 0
Joined: 01 Mar 2008 Posts: 17
|
Posted: Sat Mar 01, 2008 5:10 am Post subject: |
|
|
dude, I posted this there -.-" ages ago. It is a finnish programming site, they have forum and other things.
_________________
nowadaysidoc++andasm |
|
Back to top |
|
 |
HolyBlah Master Cheater
Reputation: 2
Joined: 24 Aug 2007 Posts: 446
|
Posted: Sat Mar 01, 2008 5:12 am Post subject: |
|
|
Still not working...
|
|
Back to top |
|
 |
Santtu K Newbie cheater
Reputation: 0
Joined: 01 Mar 2008 Posts: 17
|
|
Back to top |
|
 |
AtheistCrusader Grandmaster Cheater
Reputation: 6
Joined: 23 Sep 2006 Posts: 681
|
Posted: Sat Mar 01, 2008 5:42 am Post subject: |
|
|
im estonian and finnish is like almost next to estonia , and languages are like almost same so i understand a little.
So.... does this solve extreme sudokus?
edit: When i compile it just says solved....and something then send and dont send screen appears.
|
|
Back to top |
|
 |
Santtu K Newbie cheater
Reputation: 0
Joined: 01 Mar 2008 Posts: 17
|
Posted: Sat Mar 01, 2008 6:18 am Post subject: |
|
|
it solves basic sudokus when the screen appears there should have been created a file named solution in the fodler were the program is open it
_________________
nowadaysidoc++andasm |
|
Back to top |
|
 |
AtheistCrusader Grandmaster Cheater
Reputation: 6
Joined: 23 Sep 2006 Posts: 681
|
Posted: Sat Mar 01, 2008 6:57 am Post subject: |
|
|
nope, it didnt make any file for me.
Btw attach source and exe in a rar file.
maybe i compiled or did something wrong
|
|
Back to top |
|
 |
Santtu K Newbie cheater
Reputation: 0
Joined: 01 Mar 2008 Posts: 17
|
|
Back to top |
|
 |
AtheistCrusader Grandmaster Cheater
Reputation: 6
Joined: 23 Sep 2006 Posts: 681
|
Posted: Sat Mar 01, 2008 9:00 am Post subject: |
|
|
wow!!! and i thought i was stupit..
I have this sudoku book and i had 1 impossible suduko unfinished there.
0 0 0 0 0 2 0 0 5
4 0 8 7 0 0 0 0 1
3 9 0 0 0 0 4 0 0
0 0 7 6 5 0 0 0 0
0 0 0 1 0 4 0 0 0
0 0 0 0 7 8 1 0 0
0 0 5 0 0 0 0 4 9
9 0 0 0 0 5 2 0 7
7 0 0 8 0 0 0 0 0
So i put it in the program and guess what numbers it gave me?
UNsolved...
And the exact numbers that i had solved.
BUt then again it is a very good program. +rep.
|
|
Back to top |
|
 |
atom0s Moderator
Reputation: 205
Joined: 25 Jan 2006 Posts: 8587 Location: 127.0.0.1
|
Posted: Sat Mar 01, 2008 9:59 am Post subject: |
|
|
Stolen, and no, you didn't write this "ages" ago. This is taken from that site that was written in 2006. If anyone cares to know, this account is used by the person that was just recently banned for ripping code, skyllakarean.
Sorry but using a proxy, from the looks of it, doesn't help when you log into another account using it at the same time.
What don't you understand about copyright infringement? Stealing others work does not make you look good and people in this section know how to Google and locate work that others post here and take credit for. Every single post you have made on your other account was found elsewhere from years before or on sites that you definitely don't own, run, or are a member to.
Do yourself a favor and stop lying and actually read a book and learn for yourself.
Locked and warned.
_________________
- Retired. |
|
Back to top |
|
 |
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum You cannot attach files in this forum You can download files in this forum
|
|