IT Tutorial IT Tutorial | Oracle DBA | SQL Server, Goldengate, Exadata, Big Data, Data ScienceTutorial
Futoshiki bulmacasını çözen kodları anlatmaya devam ediyoruz.
Kesin Sayıları Yerleştiren Fonksiyonun C kodları
bool kesin_sayi_bul()
{
int sayac=0,yer,counter=0;
for(int i=0;i<satir;i++)
for(int k=0;k<satir;k++)
{
for(int j=0;j<sutun;j++)
if(dizi_a[i][j][k]!=-1)
{ sayac++;yer=j;}
if(sayac==1)
{dizi[i][yer][0]=k+1;counter++;
alternatif_degerleri_yerlestir();
} sayac=0;
}
for(int j=0;j<sutun;j++)
for(int k=0;k<satir;k++)
{
for(int i=0;i<satir;i++)
if(dizi_a[i][j][k]!=-1)
{ sayac++;yer=i;}
if(sayac==1)
{dizi[yer][j][0]=k+1;
counter++;
alternatif_degerleri_yerlestir();
}sayac=0;
}
sayac=0;
for(int i=0;i<satir;i++)
for(int j=0;j<sutun;j++)
{
for(int k=0;k<satir;k++)
if(dizi_a[i][j][k]!=-1)
{sayac++;yer=k;}
if(sayac==1)
{ dizi[i][j][0]=yer+1;counter++;
alternatif_degerleri_yerlestir();} sayac=0;} if(counter)return true; else return false;}
Matrise kesin sayılar yerleştirildikten sonra oluşan yeni matris aynı işlemlere tabi tutulur ta ki matristeki tüm değerler yerleşene kadar. Fakat bazen alternatif değerler arasından satır-sütun boyunca yalnız bir kere tekrar eden sayı bulunmamaktadır. Buda bulmacanın birden fazla çözümünün olduğunu gösterir. Böyle durumlarda satır-sütün boyunca birden fazla tekrar eden alternatif değerlerden rastgele biri kesin değer olarak atanır ve tekrar oluşan yeni matriste
diğer çözüme gidilir.
Rastgele Değer Atayan Fonksiyonun C kodları
/*secilen hüçredeki alternatif değerlerden satır-sütun boyunca tekrar sayısı az olan alternatif değer
asıl değer olarak atanır */
bool rasgele_yerletir()
{
int i,j,k;
int ***dizi1;
int ***dizi_a1;
bool kontrol=false;
for( i=0;i<satir;i++)
for(j=0;j<sutun;j++)
if(dizi[i][j][0]==0)
kontrol=true;
if(!kontrol)
{return true;
}
i=rand()%satir;
j=rand()%sutun;
while(dizi[i][j][0])
{i=rand()%satir;
j=rand()%sutun;
}
int max,sayac=0,*tmp=new int[satir];
sirala(tmp,i,j);
x:
for(int n=0;n<satir;n++)
if(tmp[n]!=-1)sayac++;
if(!sayac)return false;
max=tmp[0];
for(int n=0;n<satir;n++)
if(tmp[n]>=max)
{max=tmp[n];k=n;}
tmp[k]=-1;
sayac=0;
kopyala(dizi1,dizi_a1);
dizi[i][j][0]=k+1;
alternatif_degerleri_yerlestir();
bool durum=true;
while(durum)
{durum=kesin_sayi_bul();
alternatif_degerleri_yerlestir();
}
if(!rasgele_yerletir())
{geri_al(dizi1,dizi_a1);
yik(dizi1,dizi_a1);
goto x;
}
delete tmp;
return true;
}
Şekil 4.Tüm Asıl Değerleri Yerleştirilen Matris
Futoshiki nin Üretimi
Bulmacanın üretiminde çözüm aşamalarından faydalanacağız. İlk olarak bize latin kareler kuralına göre rastgele dizilmiş bir matris lazım. Bu matrisi elde etmenin çeşitli algoritmaları bulunmaktadır. Latin Kareler bölümünde bunlardan bir kaçını vermiştik. Biz matrisin oluşturulmasında verdiğimiz algoritmaların dışında bir yol vereceğiz. İlk olarak sıfır ipuclu bir matrisi üstte
algoritması ve kodlarını verdiğimiz Futoshikinin Çözümü‘le çözeceğiz. Aşağıda boş bir matrisin kurallar çerçevesinde çözümü verilmiştir.
a b
Şekil 5.a-)5*5’lü Boş Matris, b-)5*5’lü Boş Matrisin Çözümü
Üretimin ikinci aşamasında oluşturulan matrisin hücreleri arasındaki ilişkiler belirlenir.
Şekil 6.Hücreler Arasındaki İlişkiler
Hücreler Arasındaki İlişkiyi Bulan Fonksiyonun C kodları
void Hucreler_arasındaki_iliskiyi_belirle()
{ int a=0,b=0,c=0;
for(int i=0;i<satir;i++)
for(int j=0;j<sutun;j++)
{
for(int yon=1;yon<=4;yon++)
{if(dizi[i][j][yon]==-1)continue;
switch(yon)
{case 1:a=1;b=0;c=2;break;
case 2:a=-1;b=0;c=1;break;
case 3:a=0;b=-1;c=4;break;
case 4:a=0;b=1;c=3;break; }
if(i!=satir&&j!=sutun)
{
if(dizi[i][j][0]>dizi[i+b][j+a][0])
{dizi[i][j][yon]=1;dizi[i+b][j+a][c]=2;}
else
{dizi[i][j][yon]=2;dizi[i+b][j+a][c]=1;}
} } } }
Üretim deki son aşama olarak oluşturulan matristen rastgele n tane (n-matrisin boyutuna bağlı) değer silinmeye başlanır. Amaç tek çözümlü bulmaca oluşturmak ise şayet, rastgele her silinen elemanda sonra bulmacanın çözüm sayısı denetlenir tek çözüm bulunması halinde bir sonraki silme işlemini devam edilir. Birden fazla alternatif çözüm olması durumunda silinen eleman tekrar yerine yerleştirilir ve bir sonraki silme işlemine devam edilir. Silme işlemi bittikten sonra bulmacamız oluşturulmuş olur. Aşağıda oluşturulmuş tek çözümlü bir bulmaca örneği verilmiştir.
Şekil 7.5*5’lik Tek Çözümlü Futoshiki Bulmacası
Rastgele Silme İşlemi Yapan Fonksiyonun C kodları
void minimize_et()
{
int x,y;
int ***tmp;
tmp=new int **[satir];
for(int i=0;i<satir;i++)
tmp[i]=new int*[sutun];
for(int i=0;i<satir;i++)
for(int j=0;j<sutun;j++)
tmp[i][j]=new int[5];
for(int i_=0;i_<satir;i_++)
for(int j_=0;j_<sutun;j_++)
for(int k_=0;k_<5;k_++)
tmp[i_][j_][k_]=dizi[i_][j_][k_];
int a_,b_,z;
for(int j=0;j<1000;j++)
{
y=rand()%satir;
x=rand()%sutun;
z=rand()%5;
while(tmp[y][x][z]==0)
{
y=rand()%satir;
x=rand()%sutun;
z=rand()%5;}
for(int i_=0;i_<satir;i_++)
for(int j_=0;j_<sutun;j_++)
for(int k_=0;k_<satir;k_++)
dizi_a[i_][j_][k_]=k_+1;
if(z==1)
{ //system("pause");
a_=tmp[y][x][z];
tmp[y][x][z]=0;
if(x<sutun-1){
b_=tmp[y][x+1][z+1];
tmp[y][x+1][z+1]=0;
}
}
else if(z==2)
{ // system("pause");
a_=tmp[y][x][z];
tmp[y][x][z]=0;
if(x>0){
b_=tmp[y][x-1][z-1];
tmp[y][x-1][z-1]=0;
}
}
else if(z==3)
{ // system("pause");
a_=tmp[y][x][z];
tmp[y][x][z]=0;
if(y>0){
b_=tmp[y-1][x][z+1];
tmp[y-1][x][z+1]=0;
}
}
else if(z==4)
{ //system("pause");
a_=tmp[y][x][z];
tmp[y][x][z]=0;
if(y<satir-1){
b_=tmp[y+1][x][z-1];
tmp[y+1][x][z-1]=0;
}}
else if(z==0)
{ // system("pause");
a_=tmp[y][x][z];
tmp[y][x][z]=0;
}
for(int i_=0;i_<satir;i_++)
for(int j_=0;j_<sutun;j_++)
for(int k_=0;k_<5;k_++)
dizi[i_][j_][k_]=tmp[i_][j_][k_];
// yaz(); system("pause");
if(cozumleyici1())
continue;
if(z==1)
{
tmp[y][x][z]=a_;
if(x<sutun-1)
tmp[y][x+1][z+1]=b_;
}
else if(z==2)
{
tmp[y][x][z]=a_;
if(x>0)
tmp[y][x-1][z-1]=b_;
}
else if(z==3)
{
tmp[y][x][z]=a_;
if(y>0)
tmp[y-1][x][z+1]= b_;
}
else if(z==4)
{
tmp[y][x][z]=a_;
if(y<satir-1)
tmp[y+1][x][z-1]= b_;
}
else if(z==0)
{
tmp[y][x][z] =a_;}}
for(int i_=0;i_<satir;i_++)
for(int j_=0;j_<sutun;j_++)
for(int k_=0;k_<5;k_++)
dizi[i_][j_][k_]=tmp[i_][j_][k_]; }
