Danyel Koca Danyel Koca

Javascript Kullanarak Sudoku Nasıl Çözülür?

Yayın: 27 Mayıs 2024

Javascript Kullanarak Sudoku Nasıl Çözülür?

Arka Plan

Önceki blog yazımda, aşağıdaki gibi eksiksiz bir sudoku ızgarası oluşturmanın nasıl yapılacağını yazmıştım. (Bu sudoku ızgarasının gerçek zamanlı olarak oluşturulduğunu unutmayın, bu sayfayı her ziyaret ettiğinizde ızgara değişecektir)

5
9
3
8
4
6
1
2
7
7
1
6
9
3
2
8
5
4
2
8
4
1
5
7
6
3
9
6
5
2
7
1
4
9
8
3
9
3
7
2
8
5
4
1
6
1
4
8
3
6
9
5
7
2
8
6
5
4
2
3
7
9
1
4
2
9
5
7
1
3
6
8
3
7
1
6
9
8
2
4
5

Bu, bu ızgaradan bazı sayıları kaldırarak bir sudoku oyunu oluşturacağımız ve onu çözmek için bir algoritma geliştireceğimiz bir takip yazısıdır.

Sudoku Veri Oluşturma

Bir Sudoku oyunu oluşturmanın ve çözmenin en zor kısmı eksiksiz ızgarayı oluşturmaktır, ki bu sorunu zaten çözdük. Izgarada 81 sayı var ve bu sayıları 81 boyutlu bir diziye kaydediyoruz. İşte üretilen verilerin görünümü:

let grid = [{ "row": 0, "col": 0, "block": "0-0", "value": 5 },

{ "row": 0, "col": 1, "block": "0-0", "value": 9 },

{ "row": 0, "col": 2, "block": "0-0", "value": 3 },

{ "row": 0, "col": 3, "block": "0-1", "value": 8 },

{ "row": 0, "col": 4, "block": "0-1", "value": 4 },

{ "row": 0, "col": 5, "block": "0-1", "value": 6 },

{ "row": 0, "col": 6, "block": "0-2", "value": 1 },

{ "row": 0, "col": 7, "block": "0-2", "value": 2 },

{ "row": 0, "col": 8, "block": "0-2", "value": 7 },

{ "row": 1, "col": 0, "block": "0-0", "value": 7 },

{ "row": 1, "col": 1, "block": "0-0", "value": 1 },

{ "row": 1, "col": 2, "block": "0-0", "value": 6 },

{ "row": 1, "col": 3, "block": "0-1", "value": 9 },

{ "row": 1, "col": 4, "block": "0-1", "value": 3 },

{ "row": 1, "col": 5, "block": "0-1", "value": 2 },

{ "row": 1, "col": 6, "block": "0-2", "value": 8 },

{ "row": 1, "col": 7, "block": "0-2", "value": 5 },

{ "row": 1, "col": 8, "block": "0-2", "value": 4 },

{ "row": 2, "col": 0, "block": "0-0", "value": 2 },

{ "row": 2, "col": 1, "block": "0-0", "value": 8 },

{ "row": 2, "col": 2, "block": "0-0", "value": 4 },

{ "row": 2, "col": 3, "block": "0-1", "value": 1 },

{ "row": 2, "col": 4, "block": "0-1", "value": 5 },

{ "row": 2, "col": 5, "block": "0-1", "value": 7 },

{ "row": 2, "col": 6, "block": "0-2", "value": 6 },

{ "row": 2, "col": 7, "block": "0-2", "value": 3 },

{ "row": 2, "col": 8, "block": "0-2", "value": 9 },

{ "row": 3, "col": 0, "block": "1-0", "value": 6 },

{ "row": 3, "col": 1, "block": "1-0", "value": 5 },

{ "row": 3, "col": 2, "block": "1-0", "value": 2 },

{ "row": 3, "col": 3, "block": "1-1", "value": 7 },

{ "row": 3, "col": 4, "block": "1-1", "value": 1 },

{ "row": 3, "col": 5, "block": "1-1", "value": 4 },

{ "row": 3, "col": 6, "block": "1-2", "value": 9 },

{ "row": 3, "col": 7, "block": "1-2", "value": 8 },

{ "row": 3, "col": 8, "block": "1-2", "value": 3 },

{ "row": 4, "col": 0, "block": "1-0", "value": 9 },

{ "row": 4, "col": 1, "block": "1-0", "value": 3 },

{ "row": 4, "col": 2, "block": "1-0", "value": 7 },

{ "row": 4, "col": 3, "block": "1-1", "value": 2 },

{ "row": 4, "col": 4, "block": "1-1", "value": 8 },

{ "row": 4, "col": 5, "block": "1-1", "value": 5 },

{ "row": 4, "col": 6, "block": "1-2", "value": 4 },

{ "row": 4, "col": 7, "block": "1-2", "value": 1 },

{ "row": 4, "col": 8, "block": "1-2", "value": 6 },

{ "row": 5, "col": 0, "block": "1-0", "value": 1 },

{ "row": 5, "col": 1, "block": "1-0", "value": 4 },

{ "row": 5, "col": 2, "block": "1-0", "value": 8 },

{ "row": 5, "col": 3, "block": "1-1", "value": 3 },

{ "row": 5, "col": 4, "block": "1-1", "value": 6 },

{ "row": 5, "col": 5, "block": "1-1", "value": 9 },

{ "row": 5, "col": 6, "block": "1-2", "value": 5 },

{ "row": 5, "col": 7, "block": "1-2", "value": 7 },

{ "row": 5, "col": 8, "block": "1-2", "value": 2 },

{ "row": 6, "col": 0, "block": "2-0", "value": 8 },

{ "row": 6, "col": 1, "block": "2-0", "value": 6 },

{ "row": 6, "col": 2, "block": "2-0", "value": 5 },

{ "row": 6, "col": 3, "block": "2-1", "value": 4 },

{ "row": 6, "col": 4, "block": "2-1", "value": 2 },

{ "row": 6, "col": 5, "block": "2-1", "value": 3 },

{ "row": 6, "col": 6, "block": "2-2", "value": 7 },

{ "row": 6, "col": 7, "block": "2-2", "value": 9 },

{ "row": 6, "col": 8, "block": "2-2", "value": 1 },

{ "row": 7, "col": 0, "block": "2-0", "value": 4 },

{ "row": 7, "col": 1, "block": "2-0", "value": 2 },

{ "row": 7, "col": 2, "block": "2-0", "value": 9 },

{ "row": 7, "col": 3, "block": "2-1", "value": 5 },

{ "row": 7, "col": 4, "block": "2-1", "value": 7 },

{ "row": 7, "col": 5, "block": "2-1", "value": 1 },

{ "row": 7, "col": 6, "block": "2-2", "value": 3 },

{ "row": 7, "col": 7, "block": "2-2", "value": 6 },

{ "row": 7, "col": 8, "block": "2-2", "value": 8 },

{ "row": 8, "col": 0, "block": "2-0", "value": 3 },

{ "row": 8, "col": 1, "block": "2-0", "value": 7 },

{ "row": 8, "col": 2, "block": "2-0", "value": 1 },

{ "row": 8, "col": 3, "block": "2-1", "value": 6 },

{ "row": 8, "col": 4, "block": "2-1", "value": 9 },

{ "row": 8, "col": 5, "block": "2-1", "value": 8 },

{ "row": 8, "col": 6, "block": "2-2", "value": 2 },

{ "row": 8, "col": 7, "block": "2-2", "value": 4 },

{ "row": 8, "col": 8, "block": "2-2", "value": 5 }]

Sayıları Kaldırarak Sudoku Oyunu Oluşturma

Şimdi rastgele bazı sayıları kaldıralım ve yeni bir newGrid oluşturalım. Bu bizim sudoku tahtamız olacak.

Aşağıdan kaldırılacak hücre sayısını seçebilirsiniz. 10-50 hücre arasında kaldırabilirsiniz.

5
8
4
6
1
7
1
9
3
2
8
5
2
8
1
7
6
3
9
6
5
2
7
4
9
8
3
9
3
7
2
4
1
6
1
4
8
3
6
5
7
2
8
6
5
2
7
2
9
5
7
1
3
6
8
7
1
6
8
2
5

Hücreleri kaldırma kodu aşağıda bulunabilir:

let dropCount = 20;

function drop(dC) {
	let indicesToBeDropped = Array.from({ length: grid.length }, (_, index) => index)
		.map((value) => ({ value, sort: Math.random() }))
		.sort((a, b) => a.sort - b.sort)
		.map(({ value }) => value)
		.slice(0, dC);

	let nG = grid.map((number, index) => {
		let newNumber = { ...number };
		if (indicesToBeDropped.includes(index)) {
			newNumber.value = '';
			newNumber.empty = true;
		}
		return newNumber;
	});

	return nG;
}

let newGrid = drop(dropCount);

Sudoku Oyununu Çözme

İlginç kısım burada başlıyor çünkü tahtayı çözerek tamamlanmış haline geri getireceğiz, eğer yapabilirsek.

Ama oyunun gerçekten çözülebilir olup olmadığını kesin olarak bilmiyoruz, bu yüzden gidip onu çözelim. Veri yapımız, her sayının bir satır, sütun ve blok numarasıyla ilişkili olması nedeniyle bu oyunu çözmeyi son derece kolay hale getiriyor. Boş bir hücreye hangi sayının sığacağını görmek için aynı satır/sütun/blokla paylaşılan verileri filtrelememiz yeterli.

Aşağıda ızgarayı çözen kod bulunmaktadır. Mantık kodda açıklanmıştır, ancak herhangi bir sorunuz varsa yorumlarda bana bildirin.

// Önceki ızgarayı kopyalayın, böylece onu değiştirmeyiz
// $ işareti, svelte'de yeni ızgarayı önceki ızgaraya göre reaktif hale getirir
$: gameGrid = newGrid.map((n) => {
	return { ...n };
});

// Her sayı doldurulduğunda uyumak için
// böylece kullanıcı algoritmanın adım adım çalıştığını görebilir
let timeout;
function sleep(time) {
	return new Promise((resolve) => {
		timeout = setTimeout(resolve, time);
		return timeout;
	});
}

// 1000 denemeyi aşarsak, denemeyi bırakmak için bir sayım tutarız
let count = 0;

// Çözüm durumunu takip edin, böylece bir mesaj gösterebiliriz
let solved = false;

// Çözücü fonksiyon
async function solve() {
	solved = false;

	// value === "" (yani boş hücre) olan hücre kalmayana kadar iterasyona devam edin
	while (gameGrid.filter((n) => n.value === '').length !== 0 && count < 1000) {
		count++;
		// Tüm hücreler arasında döngü yap
		for (let cellIndex = 0; cellIndex < gameGrid.length; cellIndex++) {
			let cell = gameGrid[cellIndex];
			// Boş bir hücre için
			if (cell.value === '') {
				// Bu hücre ile aynı satır, sütun ve blokta bulunan sayıları bulun
				let rowNumbers = gameGrid.filter((i) => i.row === cell.row).map((i) => i.value);
				let colNumbers = gameGrid.filter((i) => i.col === cell.col).map((i) => i.value);
				let blockNumbers = gameGrid.filter((i) => i.block === cell.block).map((i) => i.value);

				// Satır, sütun ve blokta bulunmayan bu hücreye konabilecek sayıları bulun
				let rowPossibleNumbers = numbers.filter((i) => !rowNumbers.includes(i));
				let colPossibleNumbers = numbers.filter((i) => !colNumbers.includes(i));
				let blockPossibleNumbers = numbers.filter((i) => !blockNumbers.includes(i));

				// Bu hücre için tüm olası sayıların kesişimini bulun
				let possibleNumbers = [rowPossibleNumbers, colPossibleNumbers, blockPossibleNumbers];
				possibleNumbers = possibleNumbers.reduce((a, b) => a.filter((c) => b.includes(c)));

				// Eğer yalnızca 1 olası sayı varsa, doğru sayıyı bulduk!
				// Doldurun ve uyuyun
				if (possibleNumbers.length === 1) {
					cell.value = possibleNumbers[0];

					// HTML DOM'da görünür olacak şekilde gameGrid'i güncelleyin
					gameGrid = [...gameGrid];
					await sleep(100);
					break;
				}
			}
		}
	}
	clearTimeout(timeout);
	solved = true;
}

Şimdi, algoritmanın beklendiği gibi çalışıp çalışmadığını görmek için aşağıdaki düğmeye tıklayın:

5
8
4
6
1
7
1
9
3
2
8
5
2
8
1
7
6
3
9
6
5
2
7
4
9
8
3
9
3
7
2
4
1
6
1
4
8
3
6
5
7
2
8
6
5
2
7
2
9
5
7
1
3
6
8
7
1
6
8
2
5

0 kez denendi

Yukarıda tanıtılan ve kaldırılacak hücre sayısını kontrol edebileceğiniz giriş alanıyla oynamayı deneyin. 50 hücre kaldırmaya yaklaştıkça, tahtayı 1.000 deneme içinde çözmek giderek zorlaştığını göreceksiniz.

Sonuç

Bu blog yazısında, eksiksiz bir tahtadan sudoku oyunu oluşturmanın bir yolunu geliştirdik. Eksiksiz tahta oluşturma konusu daha önceki bir blogda ele alınmıştı.

Kullanıcı girdisine göre belirli sayıda hücreyi kaldırdıktan sonra, bu hücreleri doldurmak için satır, sütun ve blok koşullarına uygun olup olmadığını kontrol ederek brute-force yaklaşımı kullandık.

Herhangi bir sorunuz varsa, aşağıya bir yorum bırakarak bana bildirin.

Başka bir bildirime kadar, mutlu hacklemeler :)

Bu blog İngilizce'den ChatGPT ile çevrilmiştir. Herhangi bir belirsizlik durumunda İletişim sayfasından bana ulaşabilirsiniz.

Yorum bırak

Yorumlar

Diğer bloglara bak

Svelte ve JavaScript ile Basit ve Dinamik Bir Tooltip Yaratma Yöntemi

2024/06/19

Svelte ve JavaScript ile Basit ve Dinamik Bir Tooltip Yaratma Yöntemi

JavaScriptSvelteKolayBasitDinamikTooltipFront-end
JavaScript ile Tokyo'nun İnteraktif Haritasını Oluşturun

2024/06/17

JavaScript ile Tokyo'nun İnteraktif Haritasını Oluşturun

SvelteSVGJavaScriptTailwindInteraktif HaritaTokyoJaponya23 WardsTokyo Metropolitan Bölgesi
Matplotlib'de Japonca Karakter Sorununu Çözme Yöntemi

2024/06/14

Matplotlib'de Japonca Karakter Sorununu Çözme Yöntemi

MatplotlibGrafikÇizimPythonJaponca KarakterlerSorunBug
Kitap İncelemesi | Ötekiyle Konuşmak by Malcolm Gladwell

2024/06/13

Kitap İncelemesi | Ötekiyle Konuşmak by Malcolm Gladwell

Kitap İncelemesiÖtekiyle KonuşmakTalking to StrangersMalcolm Gladwell
Japonca'da En Sık Kullanılan 3.000 Kanji

2024/06/07

Japonca'da En Sık Kullanılan 3.000 Kanji

3000Kullanma YayginligiKanji KullanimiKanjiJaponcaKanji ListesiKanji YayginligiJLPTJaponca CalismaOgrenmeYaygin Japonca Kelimeler
VSCode'da Regex Kullanarak Replace Yapma Yöntemi

2024/06/07

VSCode'da Regex Kullanarak Replace Yapma Yöntemi

VSCodeRegexAramaDeğiştirmeKoşullu DeğiştirmeFindReplaceConditional Replace
Svelte'de Readable Store Kullanmayın

2024/06/06

Svelte'de Readable Store Kullanmayın

SvelteReadableWritableState ManagementStoreHızBellekDosya Boyutu
Dosyaları Gzip ve Pako ile Sıkıştırarak Web Sitesinin Yükleme Hızını Artırın

2024/06/05

Dosyaları Gzip ve Pako ile Sıkıştırarak Web Sitesinin Yükleme Hızını Artırın

GzipSıkıştırmaPakoWeb SitesiYükleme HızıSvelteKit
Web Sayfasında Farenin Uzerinde Oldugu Kelimeyi JavaScript ile Bulun

2024/05/31

Web Sayfasında Farenin Uzerinde Oldugu Kelimeyi JavaScript ile Bulun

JavascriptFarePointerHoverWeb Geliştirme
Svelte ve SVG ile Interaktif Harita Oluşturun

2024/05/29

Svelte ve SVG ile Interaktif Harita Oluşturun

SvelteSVGInteraktif HaritaFront-end
Kitap İncelemesi | Geleneklere Uymayanlar Dünyayı Nasıl İleri Taşıyor? by Adam Grant & Sheryl Sandberg

2024/05/28

Kitap İncelemesi | Geleneklere Uymayanlar Dünyayı Nasıl İleri Taşıyor? by Adam Grant & Sheryl Sandberg

Kitap İncelemesiGeleneklere Uymayanlar Dünyayı Nasıl İleri Taşıyor?Originals: How Non-Conformists Move the WorldAdam Grant & Sheryl Sandberg
Web Siteme Gelen Trafiği Bir Ayda Nasıl 10 Kat Artırdım?

2024/05/26

Web Siteme Gelen Trafiği Bir Ayda Nasıl 10 Kat Artırdım?

Website Trafik ArtırmaClick (Tıklama)Impression (Gösterim)Google Search Console
Hayat Bisiklet Sürmek Gibidir

2024/05/24

Hayat Bisiklet Sürmek Gibidir

BisikletHayatFilozofiBaşarı
JavaScript'te Backtracking Algoritması ile Tamamlanmış Sudoku Oluşturun

2024/05/19

JavaScript'te Backtracking Algoritması ile Tamamlanmış Sudoku Oluşturun

SudokuBacktracking AlgoritmasıTamamlanmış SudokuJavaScript
Tailwind Neden Harikadır ve Web Geliştirmeyi Nasıl Kolay Hale Getirir?

2024/05/16

Tailwind Neden Harikadır ve Web Geliştirmeyi Nasıl Kolay Hale Getirir?

TailwindHarikaFront-endWeb Geliştirme
Python ve Git Hooks ile Otomatik Olarak Site Haritası Oluşturma

2024/05/15

Python ve Git Hooks ile Otomatik Olarak Site Haritası Oluşturma

Git HooksPythonSite HaritasıSvelteKit
Kitap İncelemesi | Çok Yönlü - Başarı İçin Neden Çok Şeyle İlgilenmeliyiz? by David Epstein

2024/05/14

Kitap İncelemesi | Çok Yönlü - Başarı İçin Neden Çok Şeyle İlgilenmeliyiz? by David Epstein

Kitap İncelemesiRange（Çok Yönlü）David EpsteinBaşarı İçin Neden Çok Şeyle İlgilenmeliyiz?
Svelte ve SvelteKit nedir?

2024/05/13

Svelte ve SvelteKit nedir?

SvelteSvelteKitFront-endVite
SvelteKit ile Internationalization (Çoklu Dil Desteği)

2024/05/12

SvelteKit ile Internationalization (Çoklu Dil Desteği)

InternationalizationÇoklu Dil DestegiSvelteKitI18N
Svelte'de Caching ile Deploy Süresini Azaltın

2024/05/11

Svelte'de Caching ile Deploy Süresini Azaltın

SvelteEnhanced ImageCachingDeploy Suresi
Svelte ve Intersection Oberver ile Lazy-Load

2024/05/10

Svelte ve Intersection Oberver ile Lazy-Load

Lazy LoadingWebsite Hiz OptimizasyonuSvelteIntersection Observer
Genetik Algoritma İle Hisse Senedi Portföyü Optimizasyonu

2024/05/10

Genetik Algoritma İle Hisse Senedi Portföyü Optimizasyonu

Hisse SenediPortföy OptimizasyonuGenetik AlgoritmaPython
ShapeFile Formatini SVG Formatina Degistirme Yontemi

2024/05/09

ShapeFile Formatini SVG Formatina Degistirme Yontemi

ShapeFileSVGPythonGeoJSON
Svelte'de Reaktivite: Variables, Binding, ve Key Fonksiyonu

2024/05/08

Svelte'de Reaktivite: Variables, Binding, ve Key Fonksiyonu

SvelteSayfa GuncellemeBindingKey Fonksiyonu
Kitap İncelemesi | Savaş Sanatı - Sun Tzu

2024/05/07

Kitap İncelemesi | Savaş Sanatı - Sun Tzu

Kitap İncelemesiThe Art of War (Savaş Sanatı)Sun TzuThomas Cleary
Specialistlik Bitti. Yaşasın Generalistlik!

2024/05/06

Specialistlik Bitti. Yaşasın Generalistlik!

GenelUzmanParadigma DegisimiYazilim Muhendisligi
2018 Milletvekili Seçimlerinde Yaşa Göre Parti Eğilimi

2024/05/03

2018 Milletvekili Seçimlerinde Yaşa Göre Parti Eğilimi

PythonSecmen Profil Analizi2018 Milletvekili SecimleriSecmen Yas Analizi
Python Selenium Ile Secmen Veritabani Olusturma

2024/05/01

Python Selenium Ile Secmen Veritabani Olusturma

PythonSeleniumVeri KazimaMilletvekili Secimleri
Svelte ve Tailwind Ile Infinite Scroll Yapma Yontemi

2024/04/30

Svelte ve Tailwind Ile Infinite Scroll Yapma Yontemi

SvelteTailwindInfinite ScrollFront-end
1 Yıl İçerisinde Japonca Konuşabilmek

2024/04/29

1 Yıl İçerisinde Japonca Konuşabilmek

JaponcaDil yeterliligiJLPTKisa zamanda dil ogrenme
Svelte ve Tailwind ile Kullanıma Hazır Web Sitesi Şablonu

2024/04/25

Svelte ve Tailwind ile Kullanıma Hazır Web Sitesi Şablonu

Website SablonuFront-endSvelteTailwind
Tembel Muhendisler Kotu Urunler Yapar

2024/01/29

Tembel Muhendisler Kotu Urunler Yapar

Tembel MuhendisKotu UrunStarbucksSBI
Mukemmellik Uzerine

2024/01/28

Mukemmellik Uzerine

MukemmellikHayatin anlamiTatmin Edici HayatAmac
MacBook'ta PDF'i PNG'ye Cevirme Yontemi

2024/01/28

MacBook'ta PDF'i PNG'ye Cevirme Yontemi

PDFPNGMacBookAutomator
2023'u Kapatiyoruz: Bu Yil Okunan 24 Kitap

2023/12/31

2023'u Kapatiyoruz: Bu Yil Okunan 24 Kitap

KitapOkuma2023Geriye Bakma
Python PIL Kullarak Foto Kolaji Yapma Yontemi

2023/12/30

Python PIL Kullarak Foto Kolaji Yapma Yontemi

PythonPILGörüntü işlemeKolaj
Site Ziyaretcilerinin Alet ve Tarayicilarini Tespit Etme Yontemi

2024/01/09

Site Ziyaretcilerinin Alet ve Tarayicilarini Tespit Etme Yontemi

JavascriptAlet TespitiBrowser TespitiWebsite Analizi
ChatGPT Cevap Anatomisi

2024/01/19

ChatGPT Cevap Anatomisi

ChatGPTBuyuk Dil ModeliMakina OgrenimiYapay Zeka