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