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

Bu blog yazısında, JavaScript'te backtracking algoritması kullanarak aşağıdaki gibi tam bir sudoku grid'inin nasıl oluşturulacağını göreceğiz. Algoritmanın nasıl çalıştığını görmek için Grid'i Yeniden Başlat butonuna tıklayın!

Arka Plan

Bir sudoku grid'ini sayılarla tamamlamak kolay gelebilir. Ayrıca, bu işi yapmak saçma da görülebilir, çünkü nihayetinde önemli olan, eksik bir sudoku grid'ini çözmektir, sıfırdan tam bir grid oluşturmak değil.

Ancak bu argümanlar yanlış olacaktır çünkü:

1. Tam bir sudoku grid'i oluşturmak kolay değildir.

Bir egzersiz olarak, oyunun kurallarına uygun bir 9x9 sudoku grid'i oluşturmaya çalışın (yani, 1-9 arası tüm sayılar her satır, sütun ve blokta tekrar olmadan kullanılmalıdır). Bu koşulları ilk ~20 sayı için sağlamak kolay olsa da, grid'in sonuna yaklaştıkça zorlaştığını fark edeceksiniz.

Bu, önceki hücrelere koyduğunuz sayılar, daha sonraki hücrelerde tüm olası sayıları elimine ederek sorunlara yol açabileceğindendir. Bu durumda birkaç hücre geriye gitmeniz, o hücredeki sayıyı değiştirmeniz ve daha sonraki hücreleri doldurmanız gerekir.

2. Tam bir sudoku grid'i oluşturmak önemsiz değildir.

Tam grid oluşturma, aslında bir sudoku oyunu oluşturmanın ilk adımıdır. Tam bir grid ile başlarız ve o grid'den sayıları çıkarırız, böylece oyuncu bu sayıları doldurabilir. Ne kadar çok sayı silersek, oyun o kadar zorlaşır.

Bu nedenle, tamamlanmış bir grid oluşturmanın, bu oyunu hazırlamanın önemli bir parçası olduğunu görebiliriz. Oyuna dalmadan önce, grid oluşturma kurallarına bir göz atalım:

Sudoku'nun Temelleri

9x9 sudoku'nun temel kuralı, grid'deki her bir satır, sütun ve blok'un 1-9 arası sayıları içermesi gerektiğidir. Bir satır, sütun veya blokta 9 hücre bulunur, bu nedenle 1-9 arası sayılar tam bir şekilde sığar ve tekrarına izin verilmez.

1. Satırlar

Aşağıda her bir satır'ın hücrede satır adı yazılmış halini görebilirsiniz.

2. Sütunlar

Aşağıda her bir sütun'un hücrede sütun adı yazılmış halini görebilirsiniz.

3. Bloklar

Bloklar, grid'i oluşturan 3x3 karelerdir. Satır ve sütunlar gibi, her blok da 1-9 arası sayıları içermelidir ve tekrarına izin verilmez.

Aşağıda her bir blok'un hücrede blok adı yazılmış halini görebilirsiniz.

Metod

Yukarıdaki bölümde kısaca değindiğim gibi, tam bir grid oluşturmak el ile yapilamaz, çünkü bunu yapabilmek için, bir hücreye belirli bir sayıyı kullanmanın ortaya çıkarabileceği tüm olası sorunları öngörmeniz gerekir.

Eninde sonunda, satır, sütun ve blok koşullarının tüm olası sayıları elediği bir hücreye rastlarsınız. Bu durumda, backtracking yaparız.

Backtracking Algoritması

Bu algoritmanın ilke olarak nasıl çalıştığını aşağıda görebilirsiniz:

1. Üzerinde olduğunuz hücre için satır, sütun, blok kısıtlamalarını karşılayan ve daha önce denenmemiş 1-9 arası bir sayı olup olmadığını kontrol edin.
2. Böyle bir sayı varsa, hücrenizin değerini o sayı olarak ayarlayın. Bu sayıyı bu hücre için denenen sayılar listesine ekleyin. Bir hücre ileri gidin ve 1. adıma dönün.
3. Aksi takdirde, bu hücre için denenen sayılar listesini temizleyin. Bir hücre geri gidin. O hücrenin (önceki hücre) değerini temizleyin ve 1. adıma dönün.

Yukarıdaki işlemlerin kod hali aşağıdadır:

// Değişkenler
let grid = []; // Grid verilerini saklamak için
let numbers = []; // 1-9 arası sayılar
let cellIndex = 0; // Hücre numarası

// Grid ve sayılar
for (let i = 0; i < 9; i++) {
	// Sayılara ekle
	numbers.push(i + 1);

	// Her hücre için, satırını, sütununu, bloğunu, başlangıç değerini ve denenmiş değerlerini kaydedin
	// Başlangıç değeri ve denenmiş değerler sırasıyla '' ve [] olarak başlatılır
	for (let j = 0; j < 9; j++) {
		let cell = {};
		cell.row = i;
		cell.col = j;
		cell.block = `${Math.floor(i / 3)}-${Math.floor(j / 3)}`;
		cell.value = '';
		cell.tried = [];
		grid.push(cell);
	}
}

// Backtracking algoritması ile grid'i dolduran fonksiyon
function fillGrid() {
	// Doldurulacak hücreler kaldığı sürece devam edin
	while (cellIndex < grid.length) {
		// İlgili hücreyi alın
		let cell = grid[cellIndex];

		// Bir hücre için tüm sayıları denemişsek, denenenleri [] olarak ayarlayın
		// Aksi takdirde algoritma tıkanır
		if (cell.tried.length == 9) {
			cell.tried = [];
		}

		// Bu hücre için, aynı satır, sütun ve bloğa ait hücreleri alın
		let row = grid.filter((d) => d.row === cell.row).map((d) => d.value);
		let col = grid.filter((d) => d.col === cell.col).map((d) => d.value);
		let block = grid.filter((d) => d.block === cell.block).map((d) => d.value);

		// Sayıları karıştırın çünkü her seferinde farklı bir grid yaratmak istiyoruz
		// Aksi takdirde gri'iniz her zaman aynı çıktıyı üretir
		numbers = numbers
			.map((value) => ({ value, sort: Math.random() }))
			.sort((a, b) => a.sort - b.sort)
			.map(({ value }) => value);

		// Bir hücre için uygun bir sayı bulunup bulunmadığını tutan değişken
		let found = false;

		// Rastgele sayılar arasında loop
		for (let n = 0; n < 9; n++) {
			// Rastgele bir sayı alın
			let number = numbers[n];

			// Bu sayının koşulları sağlayıp sağlamadığını kontrol edin
			// Yani 1. henüz denenmemiş olması
			// 2. hücre ile aynı satırda görünmemesi
			// 3. hücre ile aynı sütunda görünmemesi
			// 4. hücre ile aynı blokta görünmemesi
			if (
				!cell.tried.includes(number) &&
				!row.includes(number) &&
				!col.includes(number) &&
				!block.includes(number)
			) {
				// Eğer sayı koşulları sağlarsa hücre değerini o sayı olarak ayarlayın
				cell.value = number;

				// Sayıyı bu hücre için denenmiş sayılara ekleyin
				cell.tried.push(number);

				// Bir sonraki hücreye geçin
				cellIndex++;

				// Çözüm bulunduğu için found değerini true olarak ayarlayın
				found = true;
				break;
			}
		}

		// Hücre için bir sayı bulunamazsa
		// Yani yukarıdaki 4 koşulu sağlayan bir sayı yoksa
		if (!found) {
			// Bu hücre için denenen sayılar dizisini [] olarak ayarlayın
			grid[cellIndex].tried = [];

			// Bir hücre geri gidin
			cellIndex--;

			// Önceki hücrenin değerini diğer sayıları denemek için "" olarak ayarlayın
			grid[cellIndex].value = '';
		}
	}
}

fillGrid();

Sonuç

Şimdi yukarıdaki kodun Grid'i Doldur butonunu kullanarak aşağıdaki grid'de çalışıp çalışmadığını görelim:

Backtracking algoritması, çoğu zaman bu soruna bir çözüm bulmakta oldukça etkilidir, genellikle 1 saniyeden kısa sürede çözüm bulur.

Sonuç

Bu blog yazısında, tam bir sudoku grid'inin oluşturulmasının el ile yapılamadığı için basite indirgenemeyen bir görev olduğunu ve sudoku oyunu yapımının önemli bir parçası olduğunu gördük.

Bu görev için, tam bir sudoku grid'i oluşturmak amacıyla basit ama etkili bir algoritma geliştirdik. Backtracking algoritması olarak adlandırılan bu algoritma ile genellikle 81 hücrelik tam bir sudoku grid'ini 200 adım içinde, bir saniyeden daha kısa sürede oluşturabiliriz.

Yakında bu blog yazısını 2 yazı ile takip edeceğim:

1. Tam grid'den sayıları çıkararak zorluk dereceleri farklı sudoku oyunlarını algoritmik olarak oluşturmak
2. Sudoku oyununu algoritmik olarak çözmek

İyi eğlenceler!