Ben belirli bir Sudoku bulmaca çözmek için PHP bir algoritma yazıyorum. 9x9 tahtada her karo için Square sınıf ve {bir matris olan bir Sudoku sınıfı: ben iki sınıfları ile biraz nesne yönelimli uygulama kurdum [(0)]} kurulu temsil etmek var.
Ben kullanıyorum algoritmasının uygulanması üçlü katmanlı yaklaşımın bir tür. En temel bulmaca (ama en verimli) sadece çözecek ilk adım, sadece Forumun ilk kurulum dayalı tek bir değer alabilir ve dinlenme ona göre kısıtlamaları ayarlamak için herhangi kareleri doldurmak için faili meçhul kareler.
Genellikle, "sürekli yayılma" Bu süreç tamamen tahta çözmez, ama oldukça büyük bir yığın çözmek gelmez. Bu, her faili meçhul karenin "olası" değerler için her birimi (ya da tüm benzersiz numara atamaları olmalıdır 9 kareler, örneğin satır ya da sütun) ayrıştırmak in ikinci kademe sonra başlayacak. Olası değerler bu liste Square sınıfında bir dize olarak temsil edilir:
class Square {
private $name; // 00, 01, 02, ... , 86, 87, 88
private $peers; // All squares in same row, col, and box
private $number; // Assigned value (0 if not assigned)
private $possibles; // String of possible numbers (1-9)
public function __construct($name, $p = 0) {
$this->name = $name;
$this->setNumber($p);
if ($p == 0) {
$this->possibles = "123456789";
}
}
// ... other functions
Bir birim çözülmemiş kareler bir bütün dizi (yukarıda ikinci kademe açıklandığı gibi) göz önüne alındığında, ikinci kademe tek bir dize içine "olabileceklerin" bütün dizeleri birleştirmek olacaktır. Değerler kendilerini tekrar yok - o zaman herhangi bir benzersiz bir karakter değerleri için o tek dize yoluyla arayacaktır. Bu kareler birimi içinde, o belirli değer alabilir tek bir kare, orada olduğunu gösterecektir.
Benim soru: Bu ikinci kademe uygulanması için, nasıl bir birimindeki tüm olası değerleri bu dizeyi ayrıştırmak ve kolayca benzersiz bir değer (ler) tespit? Ben her endeks sayıları 1-9 ile temsil edilir bir dizi oluşturmak olabileceğini biliyorum, ve ben her tekrar dizi tarayın, sonra ben buluyorum bu sayının her olası-değeri için 1 ile ilgili dizin değerini artırmak olabilir 1 değerleri, ama bu her birim için bir dizinin iki lineer taramalar gerektiren, son derece verimsiz görünüyor, ve bir Sudoku bulmaca 27 adet vardır.
