Backtracking Algoritmasi hakkinda

[degetthe]

Arkadaslar. Odev olarak Sudoku cozen bir program yapmam gerekiyor. Algoritma olarak backtracking kullanmam istendi. Bildigim kadari ile bir calisma yaptim. Internetten de bazi kodlara goz attim algoritma icin. Ben yaptigim uygulamayi backtracking saniyorken biri cikip bu backtraking degil brute-force algoritmasi dedi.

Bende netten arastirmaya basladim backtraking algoritmasini. Bazilari benim yaptigim gibi, bazilarinin alakasi yok. Yazdigim kodun backtraking oldugundan emin olabilmem ve calimsaya devam edebilmem icin bana ornek bir backtracking algoritmasi gonderebilir misiniz?? Benim calismam asagidaki linkten indirilebilir. Vakti olan arkadaslar varsa ve ilgilenebilirlerse cok memnun olurum.. Ogrenmek istedigim, acaba benim yaptigim dogru algoritmami, degilse dogrusuna bir ornek..

http://dosya.co/ypx98nduqltr/SudokuENG.rar.html

Simdiden tesekkur ederim..

 

[Champion78]

Senin kodunu incelemedim ama backtracking'in brute force dan tek farkı erkenden durabilmesi. Yani sudokudan gidecek olursak, tek bir çözüm için, brute force tüm boşlukları doldurur sonra bakar oldu mu olmadı mı diye; ancak backtracking boşlukları tek tek doldurur ve herhengi bir uyuşmazlık varsa hemen sonraki sayıyı dener. Örnekle de açıklayayım: sudokunun tek karesini ele alalım 3x3. İçinde de 8 tanesi dolu 1 tane boş yer var. Oraya gelmesi gereken de 5 olsun mesela. Brute force ile yaptığın zaman, önce o boşluğa 1 koyar sonra diğer tüm boş karaleri doldurur ondan sonra bakar bu çözüm oldu mu diye, dolayısıyla çözümün bulunması uzun sürer. Ama backtracking kutuya 1 koyduğu anda bakar ki kural ihlali var, başka hiçbir kutuyla uğraşmadan hemen 2 yi dener. Böyle böyle 5'e gelince bir sonraki boş kutuya bakar. Benim wikipedia'dan anladığım bu şekilde.

http://en.wikipedia.org/wiki/Backtracking

 

[degetthe]

Ilginize tesekkur ederim.

Artik backtracking algoritmasini cozdum ama bir sorunum var. Cozulmeye hazir, bazi kutucuklari dolu bir Sudoku tablosu dusunursek, backtracking ile kare kare ilerliyorum, uygunsa degeri yaziyor. Bir hucre icin 9'a kadar denedigi halde uygun deger bulamazsa bir kare geriye gidip onu degistiriyor. Ancak bir onceki kare sudoku ilk basladiginda verilen ipucu degerlerinden birisi ise onu da siliyor.

Bunu nasil engellerim??

 

[degetthe]

Arkadaslar bir sorunu daha hallettim ancak sorunlar halen devam ediyor. Suanki sorunum, uygun bir deger atanamazsa bir kare geriye gelmesi ve farkli bir deger ile denemesi. Bunun icin kullandigim kodu asagidaki gibi.. Ancak kodun yaptigi su:

Ornegin
[2,4] icin 8 degerini atiyor.
[2,5] icin uygun bir deger bulamiyor
[2,4] e geri donuyor.
[2,4] un degerini siliyor
[2,5] e geciyor.

Haliyle [2,4] bos kaliyor. Kodun bir sucu yok. Soyleneni yapiyor ancak ben bu durumu nasil cozerim tam olarak bilemiyorum. Istedigim, bir kare geri gelip oradaki degeri silip, baska bir degerle denemesi. Ancak ne denediysem olmadi...


if (val == 9 && !chkAll(x, y, val, ref sudokuCells))
{
if (x > 0 || y > 0)
{
if (x > 0 && y == 0)
{
x--;
y = 8;
}
else
{
y--;
sudokuCells[x, y] = 0;
}
}
}

 

[Toughwolf]

Bactracking recursive bir algoritmadir.Sonraki deger uymadiginda recursive dondugun icin kacirdigin nokta olmaz. Diyelim ki P senin sorun matrisin C cozum matrisin olsun. x,y mevcut bulundugun koordinat, xn, yn sonraki koordinat olsun.

x=0, y=0;
Backtrack (P , x, y)
{
[x,y] [8,8] mi? //son koordinat
evet=>
     [x,y] de deger var mi?
         evet=>
                 cevabi yaz =>C
                 return true
         hayir=>
                   i=1
                   while i<10
                  { 
                        [x,y] ye i yazilabilir mi
                              evet=> 
                                    cevabi yaz=> C
                                    return true
                              hayir=> i++
                   }
                   degeri sil
                   return false // problem cozulemez
hayir=>
     [x,y] de deger var mi?
         evet=> 
                 return Backtrack (P , xn, yn) //bir sonraki koordinata gec
         hayir=>
                   i=1
                   while i<10
                  { 
                        [x,y] ye i yazilabilir mi
                              evet=> 
                                    Backtrack (P , xn, yn) true donuyor mu?
                                         evet=>return true
                                         hayir=> i++
                              hayir=> i++
                   }
                   degeri sil
                   return false // problem bu noktadan sonra cozulemez geri don

}

Kabaca psudocodunu yazdim. Eger backtrack fonksiyonu true dondururse problem cozumu C olur. false donerse problem hatalidir. Yazdigim psudocode u mantigini anlaman icin yazdim optimize edebilirsin. Temel olarak degeri yazdiktan sonra bir sonraki degerin yazilabilirligine bakiyorsun. Sonraki deger yazilamiyorsa geri donup yazilincaya kadar deniyorsun.

 

[degetthe]

Toughwolf cok tesekkur ederim. Cok faydali bir ornekleme oldu benim icin.. Hemen kendi uygulamama optimize etmeye calisicam.
Insallah becerebilirim. Sonucu buradan yine paylasacagim..