Futoshiki Bulmacası -2

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_]; }

 

 

About Mehmet Salih Deveci

I am Founder of SysDBASoft IT and IT Tutorial and Certified Expert about Oracle & SQL Server database, Goldengate, Exadata Machine, Oracle Database Appliance administrator with 10+years experience.I have OCA, OCP, OCE RAC Expert Certificates I have worked 100+ Banking, Insurance, Finance, Telco and etc. clients as a Consultant, Insource or Outsource.I have done 200+ Operations in this clients such as Exadata Installation & PoC & Migration & Upgrade, Oracle & SQL Server Database Upgrade, Oracle RAC Installation, SQL Server AlwaysOn Installation, Database Migration, Disaster Recovery, Backup Restore, Performance Tuning, Periodic Healthchecks.I have done 2000+ Table replication with Goldengate or SQL Server Replication tool for DWH Databases in many clients.If you need Oracle DBA, SQL Server DBA, APPS DBA,  Exadata, Goldengate, EBS Consultancy and Training you can send my email adress [email protected].-                                                                                                                                                                                                                                                 -Oracle DBA, SQL Server DBA, APPS DBA,  Exadata, Goldengate, EBS ve linux Danışmanlık ve Eğitim için  [email protected] a mail atabilirsiniz.

Leave a Reply

Your email address will not be published. Required fields are marked *