🏙️ Skyscraper Puzzle Solver

4×4 Skyscraper Bulmacası için optimize edilmiş C tabanlı çözümleyici
42 İstanbul – Piscine Öğrencileri

---

🔍 Proje Özeti

Skyscraper bulmacasında amaç, 4×4 boyutundaki kare bir ızgaraya 1–4 arasında yüksekliklere sahip kuleleri yerleştirmektir. Her satır ve sütun için:

• Tüm değerler unique olmalıdır.
• Dış kenarlardan verilen "görünür kule" ipuçları (clues) sağlanmalıdır.

Program:

• Komut satırından 16 adet clue alır.
• Input formatını subject’e uygun şekilde doğrular.
• Geçersiz durumda Error yazıp çıkış yapar.
• Geçerli durumda bulmacayı çözer ve çıktıyı satır satır yazdırır.

---

📌 Kullanım

./rush01 "4 3 2 1 1 2 2 2 4 3 2 1 1 2 2 2"

Clue'lar top → bottom → left → right sırasıyla 16 adet tam sayı olmalıdır.

Örnek çıktı:

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

---

📁 Dosya Yapısı

📂 skyscraper
├── main.c       
├── solver.c     
├── utils.c      
└── header.h     

🧩 Çözüm Mimarisi

Proje, modüler ve okunabilir olacak şekilde ayrılmıştır. Kullanılan temel yaklaşım backtracking + kısıt kontrolü birleşimidir.

1️⃣ Veri Yapıları

• Board (Izgara): int **grid (Dinamik olarak ayrılmış 4x4 matris)
• Clues (İpuçları): int clues[16]

2️⃣ Kısıt Kontrolü Fonksiyonları

Fonksiyon Adı	Dosya	Sorumluluk Prensibi
is_safe	solver.c	Latin Kare Kısıtını (Benzersizlik) kontrol eder.
count_visible_towers	utils.c	Bir kule dizisinde görünen kule sayısını hesaplar.
partial_ok	solver.c	Erken Budama (Satır/Sütun dolduğunda anlık görünürlük kontrolü) yapar.
check_clues	solver.c	Tam çözüm bulunduğunda, tüm 16 ipucunu son kez doğrular.

3️⃣ Backtracking Akışı (solve)

solve(r, c) ana fonksiyonu, gridi doldururken aşağıdaki optimize edilmiş akışı takip eder:

1. (r, c)'ye Değer Atama: Hücreye (r, c) 1'den 4'e kadar bir değer (num) denenir.
2. Latin Kare Kontrolü: is_safe ile satır ve sütundaki benzersizlik kontrol edilir.
3. Erken Budama: partial_ok ile satır/sütun dolduğunda anlık görünürlük kontrolü yapılır.
4. İlerleyiş: Eğer kısıtlar sağlanıyorsa, solve rekürsif olarak bir sonraki hücreye geçer.

4️⃣ Çıktı ve Hata Yönetimi Akışı

Çözüm akışı başarıyla tamamlandığında veya başarısız olduğunda main fonksiyonu aşağıdaki adımları uygular:

1. Nihai Doğrulama: solve başarılı döndüğünde, check_clues ile çözümün tüm 16 ipucunu sağladığından emin olunur.
2. Çıktı Formatlama: Doğrulanan çözüm, print_grid(grid) fonksiyonu ile 4x4 formatında satır satır yazdırılır.
3. Hata Durumu: Nihai kontrol başarısız olursa veya solve hiç çözüm bulamazsa, ft_putstr("Error") ile hata çıktısı verilir.
4. Bellek Temizliği: Dinamik olarak ayrılan tüm bellek (malloc ile ayrılan grid) en sonunda free ile serbest bırakılır.

⚠️ Hata Yönetimi

Hatalı durumlar:

• Eksik/yanlış argüman sayısı
• Argümanların sayı olmaması
• 1–4 dışı değerler
• Toplam 16 clue olmaması

Error

---

🚀 Performans Notları

• Optimizasyon: Erken Budama (Partial Pruning) Mekanizması

  • Skyscraper bulmacasını çözen standart Backtracking algoritmaları, grid dolana kadar görünürlük kısıtlarını kontrol etmez. Bu durum, yanlış bir başlangıçla başlayan binlerce gereksiz dalın denenmesine yol açar ve performansı düşürür.

  • Sistemin yavaşlığını optimize etmek adına geliştirdiğimiz partial_ok fonksiyonu, bu sorunu çözer:

  • Çalışma Prensibi: Bir hücreye değer atandığında ve o hücrenin bulunduğu satır veya sütun tamamen dolduğunda (örneğin satırın 4. hücresi doldurulduğunda), partial_ok hemen çağrılır.

  • Kısıt Kontrolü: Fonksiyon, o anda dolan satırın/sütunun ilgili iki kenar ipucunu (left/right veya top/bottom) anlık olarak kontrol eder.

  • Etki: Eğer bu kısmi dizi, ipuçlarını ihlal ediyorsa, Backtracking algoritması o dalın tamamını denerken zaman kaybetmez ve hemen geri döner (budama). Bu sayede arama ağacının büyük bir kısmı elenir.

• 4×4 gibi küçük bir grid boyutu için bu optimizasyon, çözüm garantisini çok hızlandırır.

• Fonksiyonlar tek sorumluluk prensibiyle yazıldığından test ve debug kolaydır.

• Bellek yönetimi tamamen kontrol edilmiş, Valgrind ile test edilmiştir:

valgrind --leak-check=full --show-leak-kinds=all 

---

🛠️ Derleme ve Çalıştırma

Derleme:

gcc -Wall -Wextra -Werror *.c -o rush01

Çalıştırma:

./rush01 "4 3 2 1 1 2 2 2 4 3 2 1 1 2 2 2"

🧪 Test İçin Faydalı Komutlar

Doğru çözüm üreten bir senaryo:

./rush01 "4 3 2 1 1 2 2 2 4 3 2 1 1 2 2 2"

Hatalı input:

./rush01 "4 3 2"
-> Error

Karışık ama çözülebilir bir set:

./rush01 "2 2 1 3 3 2 2 1 2 1 3 2 3 2 1 2"

---

🕹️ Bulmacayı Deneyin

Projenin ne kadar karmaşık bir problemi çözdüğünü daha iyi anlamak için, klasik 4x4 Skyscraper bulmacasını kendiniz çözmeyi deneyebilirsiniz!

• Oyun Linki: [Online Skyscraper Puzzle (4x4)] (https://tr.puzzle-skyscrapers.com/)

---

🤝 Katkı ve İletişim

Bu proje, 42 İstanbul C Piscine öğrencileri tarafından bir takım çalışması olarak geliştirilmiştir. Projenin kaynak kodunun temizliği, modülerliği ve optimizasyonu, ortak çabamızın bir sonucudur.

🐛 Hata Bildirimi ve Geliştirme

Proje şu anki kısıtları dahilinde tam çözüm sağlasa da, her zaman geliştirilmeye açıktır. Eğer:

• Kodda bir hata (bug) veya bellek sızıntısı (memory leak) fark ederseniz,
• Daha hızlı veya daha az karmaşık bir algoritma öneriniz varsa (örneğin, 6x6 grid için optimizasyon),
• Projenin dokümantasyonunu (README) iyileştirmek isterseniz,

Lütfen GitHub üzerinden bir Issue açarak veya doğrudan bir Pull Request göndererek katkıda bulunun. Katkılarınız, projenin kalitesini ve öğrenme sürecimizi ileri taşıyacaktır.

📧 Takım Üyeleri

Takım üyeleriyle direkt iletişime geçmek için lütfen aşağıdaki GitHub profillerini kullanınız.

Developer	GitHub Profile
esrairemkumasss	https://github.com/esrairemkumasss
RamiaMzrc	https://github.com/RamiaMzrc
vee-nex	https://github.com/vee-nex

🎯 Sonuç

• Bu proje, Erken Budama ile optimize edilmiş bir Backtracking çözücüsü sunarken; derin algoritma bilgisi, modüler tasarım ve zorlu kısıtlar altında temiz kod üretme yeteneğimizi önemli ölçüde geliştirmemize katkı sağlamıştır. Elde ettiğimiz bu beceriler, gelecekteki karmaşık projeler için sağlam bir temel atmamıza yardımcı olmuştur.

---

⭐️ Bu projeyi faydalı bulduysanız star vermeyi unutmayın!

⬆️ Başa Dön