Futoshiki Bulmacası -1

LATİN KARELERİ ve ÜRETİMİ

n dereceden olan Latin kareleri, nxn boyutlu kare matris (tablo) olup hanelerinde (1, n) arası sayılar yerleşmekte ve her satır ve sütun, değerlerini {1,2,…,n} kümesi elemanlarının yer değişmesinden almaktadır. 4. dereceden Latin karesi örnekleri aşağıda verilmiştir.

 

1 2 3 4 A B C D

3 4 1 2 B C D A

4 3 2 1 C D A B

2 1 4 3 D A B C

n’ye bağımlı olarak farklı Latin karelerin sayısı üssel olarak artmaktadır. n. dereceden en az n!*(n-1)!*(n-2)!*…*3!*2!*1 sayıda farklı Latin kareleri olmaktadır. n=2, 3, 4 için uygun L(n) Latin kareleri L(n)=2, 12, 576 iken L(10), yaklaşık olarak 1037 gibi bir sayıyla ifade edilir. Latin karelere kenarları da renklenmiş 2-renkli Kn,n grafları seklinde bakılabilir. Aynı renkteki ui düğümleri Latin karesinin satırlarına uygun gelmektedir. Diğer renkte olan vj düğümleri ise sütunlara karsılık düşecektir. Kn,n grafının kenarları grafın her düğümü, n renkte olabilen kenarlardan yalnız biriyle komsuluk oluşturacak şekilde renglenmektedir.

 

 

Latin karelerin oluşturulmasında aşağıdaki teoremi verebiliriz.

Teorem. n*n boyutlu A matrisinin aij elemanları, satır ve sütun değerlerinin

(mod n)’ye göre toplamından oluşmuşsa A matrisi n. dereceden Latin karesidir. aij = i+j (mod n) (i, j =1, 2, … , n) Örneğin 3*3’lük matrisin satır ve sütun değerlerinin toplamıyla oluşturulmuş 3. dereceden Latin karesi mod 3 işlemine göre kolaylıkla elde edilmektedir.

2 3 4 2 0 1

3 4 5 0 1 2

4 5 6 1 2 0

 

 

Futoshiki nin Çözümü

 

Yukarıda da ifade ettiğimiz gibi futoshiki latin karelerden yararlanılarak çeşitler kurallara göre hazırlanan ve çözülen bir bulmacadır. Bu bölümde futoshikinin çözümü üzerinde duracağız. Latin karelerden bildiğimiz gibi matrisimizin satır ve sütun boyunca sayılar tekrarsız yerleştirilir. Futoshikide de n tane ipuçlu bulmaca tablosunu satır ve sütun boyunca sayıları tekrarsız ve hüçrelerin birbirlerine göre durumunu baz alarak çözüm üretilir. Aşağıda 4*4’lük bulmaca ve çözümü verilmiştir.

 

Şekil 1. 4*4 Futoshiki Bulmacası ve Çözümü

Yukarıdaki örnekte de görüldüğü üzere bulmaca, verilen ipuclarından hareketle her satır ve sütun boyunca sayılar tekrarsız yerleştirilmiştir. Şimdi bu çözümün bilgisayardaki programı üzerinde duralım.

 

Futoshiki tablosunu bilgisayarda n*n bir matris gibi düşünebiliriz ve tek yapmamız gereken matrisin boş olan kısımlarını verilen kısıtlamaları (>,<,^,v) baz alarak uygun sayılar yerleştirmek. Programımızda ilk olarak verilen matriste boş olan her aij alternatif değer üreten bir fonksiyon bulunmaktadır.

Aşağıdaki örnekte verilen matriste boş olan hanelere fonksiyonu ürettiği alternatif değerler verilmiştir.

 

 

Alternatif Değerleri Bulan Fonksiyonun C Kodları

 

void alternatif_degerleri_yerlestir()

{

 for(int i=0;i<satir;i++)

 for(int j=0;j<sutun;j++)

{

 if(dizi[i][j][0]!=0) //dizideki alan dolu ise alternatif değerleri iptal et

 {for(int k=0;k<satir;k++)

 dizi_a[i][j][k]=-1;

 continue;

 } 

 //satir-sutun boyunca kesin olan sayıları alternatiflerden ele.

 for(int z=i-1;z>=0;z--)

 if(dizi[z][j][0]!=0) 

 {

 dizi_a[i][j][dizi[z][j][0]-1]=-1; 

 } 




 for(int z=i+1;z<satir;z++)

 if(dizi[z][j][0]!=0) 

 {

 dizi_a[i][j][dizi[z][j][0]-1]=-1; 

 } 




 for(int z=j-1;z>=0;z--)

 if(dizi[i][z][0]!=0) 

 {

 dizi_a[i][j][dizi[i][z][0]-1]=-1; 

 } 




 for(int z=j+1;z<sutun;z++)

 if(dizi[i][z][0]!=0) 

 {

 dizi_a[i][j][dizi[i][z][0]-1]=-1; 

 } 

} 

 for(int i=0;i<satir;i++)

 for(int j=0;j<sutun;j++)

 {

 for(int yon=1;yon<=4;yon++) 

 yardimci_fonksiyon(i,j,yon);

 }




}

//her hücrenin diğer hücrelerler olan ilişkisine göre alternatif değerleri değerlendir (<,>,v,^) 

void yardimci_fonksiyon(int i,int j,int yon)

{

 bool bayrak=false; 

 int a=0,b=0; //a=yatay ,b=düşey 




 switch(yon)

 {

 case 1:a=1;b=0;break;

 case 2:a=-1;b=0;break;

 case 3:a=0;b=-1;break;

 case 4:a=0;b=1;break; 

 }




 if(dizi[i][j][yon]==1) 

 {

 if(dizi[i][j][0]!=0) // karşıdaki hücre sabit sayıya sahipse 

 for(int z=dizi[i][j][0]-1;z<satir;z++) 

 {dizi_a[i+b][j+a][z]=-1; 

 }

 else if(dizi[i+b][j+a][0]!=0)

 { for(int z=dizi[i+b][j+a][0]-1;z>=0;z--) 

 dizi_a[i][j][z]=-1; 

 }




 else 

 {

 dizi_a[i][j][0]=-1;

 dizi_a[i+b][j+a][satir-1]=-1;




 for(int x=1;x<satir;x++)

 { 

 for(int y=0;y<x;y++){

 if(dizi_a[i+b][j+a][y]!=-1&&(dizi_a[i][j][x]>dizi_a[i+b][j+a][y]))

 bayrak=true;} 




 if(!bayrak) 

 dizi_a[i][j][x]=-1;

 bayrak=false; 

 }}} 

 else if(dizi[i][j][yon]==2)

 {

 if(dizi[i][j][0]!=0) // karşıdaki hücre sabit sayıya sahipse 

 for(int z=dizi[i][j][0]-1;z>=0;z--) 

 {dizi_a[i+b][j+a][z]=-1; 

 }







 else if(dizi[i+b][j+a][0]!=0)

 { for(int z=dizi[i+b][j+a][0]-1;z<satir;z++) 

 dizi_a[i][j][z]=-1; 

 }




 else 

 {

 dizi_a[i][j][satir-1]=-1;

 dizi_a[i+b][j+a][0]=-1;

 bayrak=false;







 for(int x=0;x<satir-1;x++)

 { 

 for(int y=1;y<satir;y++){

 if(dizi_a[i][j][x]!=-1&&(dizi_a[i+b][j+a][y]>dizi_a[i][j][x]))

 bayrak=true;

 } 




 if(!bayrak) 

 dizi_a[i][j][x]=-1;

 bayrak=false; 

 }}}}

 

 

Her boş olan hücrelerin alternatif değerleri belirlen dikten sonra, satır ve sütun boyunca alternatif sayıların tekrar etme durumunu kontrol edilerek ,tekrar sayısı bir alon alternatif durum bulunduğu hücreye kesin değer olarak yerleştirilir ve aynı zamanda alternatif değer olarak sadece bir değer alan hücrede aldığı alternatif değer kesin değer olarak atanır.

Şekil 2’de ki örnekte kesin değerler aşağıdaki gibidir.

a11=3 ,a12=1,a23=3,a33=1 olarak atanır.

Şekil 3.Kesin Olan Değerleri Yerleştirilen Matris

 

 

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.

2 comments

  1. We’re a group of volunteers and starting a new scheme in our community. Your web site provided us with valuable info to work on. You’ve done a formidable job and our entire community will be grateful to you.

Leave a Reply

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