NYTimes Pips bulmacasını bir kısıtlama çözücüyle çözme

New York Times yakın zamanda yeni bir günlük bulmacayı tanıttı:Pips. Çeşitli koşulları karşılayan bir ızgaraya bir dizi domino yerleştirirsiniz. Örneğin aşağıdaki bulmacada, mor karelerdeki piplerin (noktaların) toplamı 8 olmalıdır, kırmızı karede 5 pipten az olmalı ve üç yeşil karedeki pipler eşit olmalıdır. (Bu "kolay" bulmacayı çözmek çok fazla düşünmeyi gerektirmez, ancak "orta" ve "zor" bulmacaları çözmek daha zorludur.)

Bu bulmacaları bilgisayarla nasıl çözeceğimi merak ediyordum. Geçenlerde şöyle bir yazı gördümHacker Haberleri—"Pek çok zor LeetCode problemi kolay kısıtlama problemidir"—bu, adı verilen bir sistemin faydalarını ve esnekliğini tanımlıyordu bir kısıtlama çözücü. Bir kısıtlama çözücü, bir dizi kısıtlamayı alır ve kısıtlamaları karşılayan çözümler bulur: tam olarak Pips'in gerektirdiği şey.

Pips'i bir kısıtlama çözücüyle çözmenin bunlar hakkında daha fazla bilgi edinmenin iyi bir yolu olacağını düşündüm. Çözücüler, ancak birkaç sorum vardı. Kısıtlama çözücüler anlaşılmaz matematik mi gerektiriyordu? Bir sorunu ifade etmek ne kadar zordu? Çözücü sorunu hızlı bir şekilde çözebilir mi, yoksa üstel bir aramaya yakalanır mı?

Kısıtlama çözücü kullanmanın basit olduğu ortaya çıktı; iki saatten az zamanımı aldı Sorunu çözmek için kısıtlama çözücüler hakkında hiçbir şey bilmemek. Çözücü, çözümleri milisaniyeler içinde buldu (çoğunlukla). Ancak yol boyunca birkaç tümsek vardı. Bu blog yazısında deneyimlerimi anlatacağım.MiniÇinko1kısıtlama modelleme sistemi ve Pipleri nasıl çözebileceğini gösterin.

Soruna yaklaşma

Kısıtlama çözücü için program yazmak, normal bir program yazmaktan çok farklıdır. Bilgisayara söylemek yerinehowsorunu çözmek için söylewhatistiyorsun: yerine getirilmesi gereken koşullar. Çözücü daha sonra "sihirli bir şekilde" sorunu gideren çözümleri bulur.

Sorunu çözmek için adında bir dizi oluşturdum.pipsher konumdaki domino pip sayısını tutan ızgarada. O halde yukarıdaki problemin üç kısıtı şu şekilde ifade edilebilir. Kısıtlamaların bulmacadaki koşulları nasıl doğrudan ifade ettiğini görebilirsiniz.

constraint pips[1,1] + pips[2,1] == 8;
constraint pips[2,3] < 5;
constraint all_equal([pips[3,1], pips[3,2], pips[3,3]]);

Daha sonra, bulmaca için domino taşlarının nereye yerleştirilebileceğini belirtmem gerekiyordu. Bunu yapmak için adında bir dizi tanımladım.gridizin verilen konumları belirten: 1, geçerli bir durumu belirtir konum ve 0 geçersiz bir konumu belirtir. (Yazının üst kısmındaki bulmacayla karşılaştırırsanız, aşağıdaki ızgaranın şekliyle eşleştiğini görebilirsiniz.)

grid = [|
1,1,0|
1,1,1|
1,1,1|];

Ayrıca yukarıdaki problem için her yarıdaki nokta sayısını belirterek domino setini de tanımladım:

spots = [|5,1| 1,4| 4,2| 1,3|];

Şu ana kadar kısıtlamalar sorunla doğrudan örtüşüyor. Ancak bu parçaların nasıl etkileşime girdiğini belirtmek için biraz daha kod yazmam gerekiyordu. Ama Bu kodu açıklamadan önce bir çözüm göstereceğim. Ne bekleyeceğimden emin değildim: Kısıtlama çözücü bana bir çözüm mü verecek yoksa dönecek mi? sonsuza kadar mı? Benzersiz çözümü 109 milisaniyede bulduğu ortaya çıktı: çözüm dizileri. pipsdizi her konumdaki pip sayısını gösterirken,dominogriddizi hangisini gösterir domino (1'den 4'e kadar) her konumdadır.

pips = 
[| 4, 2, 0
 | 4, 5, 3
 | 1, 1, 1
 |];
dominogrid = 
[| 3, 3, 0
 | 2, 1, 4
 | 2, 1, 4
 |];

Yukarıdaki metin tabanlı çözüm biraz çirkin. Ancak grafiksel çıktı oluşturmak kolaydır. MiniZinc bir JavaScript API'si sağlar, böylece kolayca görüntüleyebilirsiniz. Çözümler bir web sayfasında. Aşağıda gösterildiği gibi çözümü çizmek için birkaç satır JavaScript yazdım. (Noktaları çizemeyecek kadar tembel olduğum için sadece sayıları gösteriyorum.) Bu bulmacayı çözmek çok etkileyici değil - sonuçta "kolay" bir bulmaca - ama aşağıda göstereceğim çözücü ayrıca çok daha zor bulmacaları da çözebilir.

Kodun ayrıntıları

Yukarıdaki kod belirli bir bulmacayı belirtirken, tanımlamak için biraz daha fazla kod gerekir. domino taşları ve ızgaranın nasıl etkileşime girdiği. Bu kod, kısıtlamalar olarak uygulandığı için garip görünebilir. Normal bir programdaki prosedürel işlemler.

Ana tasarım kararım domino taşlarının yerlerinin nasıl belirleneceğiydi. Izgara konumu ve yönü atamayı düşündüm her domino taşı için, ancak çoklu yönelimlerle uğraşmak sakıncalı görünüyordu. Bunun yerine domino taşının her yarısını bağımsız olarak konumlandırmaya karar verdim.x and ykoordine etmek ızgara.2Her domino taşının iki yarısının komşu hücrelerde olması gerektiğine dair bir kısıtlama ekledim. yani X ya da Y koordinatlarının 1 oranında farklı olması gerekiyordu.

constraint forall(i in DOMINO) (abs(x[i, 1] - x[i, 2]) + abs(y[i, 1] - y[i, 2]) == 1);

Doldurmak için biraz düşünmem gerektipipsHer domino taşı üzerindeki nokta sayısını içeren dizi. Normal bir programlama dilinde, domino taşları üzerinde döngü yapılır ve değerlerpips. Ancak burada bu bir kısıtlamayla yapılır, böylece çözücü değerlerin atandığından emin olur. Spesifik olarak, her yarım domino için,pipsdizi girişi domino'nun x/y koordinatı karşılık gelen değere eşit olmalıdırspotsdomino taşı üzerinde:

constraint forall(i in DOMINO, j in HALF) (pips[y[i,j], x[i, j]] == spots[i, j]);

Hangi domino taşının hangi konumda olduğunu takip etmek için başka bir dizi eklemeye karar verdim. Bu dizi çıktıdaki domino konumlarını görmek için kullanışlıdır, ancak aynı zamanda Domino taşlarının üst üste gelmesini önler. Her domino sayısını (1, 2, 3, vb.) işgal edilen konuma koymak için bir kısıtlama kullandım.dominogrid:

constraint forall(i in DOMINO, j in HALF) (dominogrid[y[i,j], x[i, j]] == i);

Sonra, domino taşlarının yalnızca izin verilen pozisyonlara girdiğinden nasıl emin olabiliriz?grid? Bir karenin olduğu bir kısıtlama kullandımdominogridboş olmalı veya karşılık gelengridbir domino taşına izin vermeli.3Bu, şu şekilde ifade edilen "veya" koşulunu kullanır:\/alışılmadık bir üslup seçim. (Aynı şekilde "ve" de şu şekilde ifade edilir:/\. Bunlar mantıksal sembollere karşılık gelir ∨ ve ∧.)

constraint forall(i in 1..H, j in 1..W) (dominogrid[i, j] == 0 \/ grid[i, j] != 0);

Dürüst olmak gerekirse, çok fazla dizim olduğundan ve çözücünün dizilerin tutarlı olmasını sağlayan bir fare deliğine düşeceğinden endişeliydim. Ama bu kaba kuvvet yaklaşımını deneyip işe yarayıp yaramadığını görmem gerektiğini düşündüm. Çoğunlukla işe yaradığı ortaya çıktı, bu yüzden daha akıllıca bir şey yapmam gerekmedi.

Son olarak program bazı sabitleri ve değişkenleri tanımlamak için birkaç satıra ihtiyaç duyar. Aşağıdaki sabitler, belirli bir problem için domino sayısını ve ızgaranın boyutunu tanımlar:

int: NDOMINO = 4; % Number of dominoes in the puzzle
int: W = 3; % Width of the grid in this puzzle
int: H = 3; % Height of the grid in this puzzle

Daha sonra izin verilen değerleri belirtmek için veri türleri tanımlanır. Bu, çözen için çok önemlidir; "sonlu alan" çözücüsüdür, dolayısıyla boyutunu sınırlar Etki alanları sorunun boyutunu azaltır. Bu problem için değerler belirli bir aralıktaki tamsayılardır.set:

set of int: DOMINO = 1..NDOMINO; % Dominoes are numbered 1 to NDOMINO
set of int: HALF = 1..2; % The domino half is 1 or 2
set of int: xcoord = 1..W; % Coordinate into the grid
set of int: ycoord = 1..H;

Son olarak kullandığım çeşitli dizilerin boyutlarını ve türlerini tanımlıyorum. Çok önemli bir sözdizimivar, çözücünün belirlemesi gereken değişkenleri gösterir. İlk iki diziye dikkat edin,grid and spotssahip değilimvarsabit oldukları için Sorunu belirtmek için başlatıldı.

array[1..H,1..W] of 0..1: grid; % The grid defining where dominoes can go
array[DOMINO, HALF] of int: spots; % The number of spots on each half of each domino
array[DOMINO, HALF] of var xcoord: x; % X coordinate of each domino half
array[DOMINO, HALF] of var ycoord: y; % Y coordinate of each domino half
array[1..H,1..W] of var 0..6: pips; % The number of pips (0 to 6) at each location.
array[1..H,1..W] of var 0..NDOMINO: dominogrid; % The domino sequence number at each location

Kodun tamamını şurada bulabilirsinizGitHub. Garip olan şey, kodun prosedürel olmaması nedeniyle satırların herhangi bir sırada olabilmesidir. Dizileri veya sabitleri kullanmadan önce kullanabilirsiniz. Hareket bile edebilirsinincludeİsterseniz dosyanın sonuna kadar ifadeler!

Komplikasyonlar

Genel olarak, çözücünün kullanımı beklediğimden çok daha kolaydı. Ancak birkaç komplikasyon vardı.

Çözücü, bir ayarı değiştirerek ilk çözümden sonra durmak yerine birden fazla çözüm bulabilir. Ancak bunu denediğimde çözücü binlerce anlamsız çözüm üretti. Daha yakından bakıldığında sorunun, çözücünün "boş" kutuya rastgele sayılar koyması olduğu görüldü. geçerli ancak anlamsız derecede farklı çözümler yaratıyor. Bunu açıkça yasaklamadığım ortaya çıktı, bu yüzden sinsi kısıtlama çözücü devam etti ve istemediğim tonlarca çözüm ürettim. Başka bir kısıtlama eklemek sorunu çözdü. Çıkarılan ders şu: Kısıtlamalarınızın açık olduğunu düşünseniz bile, çözümleyiciler istenmeyenleri bulma konusunda çok iyidirler. Kısıtlamaları teknik olarak karşılayan çözümler.4

İkinci sorun ise, eğer yanlış bir şey yaparsanız, çözücünün sadece sorunun olduğunu söylemesidir. tatmin edici değil. Belki hata ayıklamanın akıllıca bir yolu vardır ama sonunda kısıtlamaları kaldırdım. sorun tatmin edilebilir ve sonra bu kısıtlamayla neyi yanlış yaptığımı görebilirim. (Örneğin, dizi indekslerini bir noktada geriye doğru aldım, bu da sorunu çözümsüz hale getirdi.)

En endişe verici konu, çözücünün öngörülemezliğidir: belki milisaniyeler sürecek, belki saatler sürecek. Örneğin, 5 Ekim'deki zorlu Pips bulmacası (aşağıda), çözücünün görünürde hiçbir sebep yokken dakikalar almasına neden oldu. Ancak MiniZinc IDE farklı çözücü arka uçlarını destekler. VarsayılanGecodeçözücüden şuna geçtim: Şaşırdımve hemen çok sayıda çözüm buldu, 384'ten kesin ol. (Bazen Pips bulmacalarının birden fazla çözümü olabilir ve oyuncular bunutartışmalıbulurlar.) Birden fazla çözümün Gecode çözücüyü bir şekilde bozduğundan şüpheleniyorum, belki de bunun nedeni arama ağacında "iyi" bir dalı daraltamadı. Farklı çözücülerin karşılaştırmalı değerlendirmesi için dipnota bakın.5

Kısıtlama çözücü nasıl çalışır?

Pip'leri sıfırdan çözecek bir program yazıyor olsaydınız, muhtemelen deneyebileceğiniz bir döngü olurdu Domino taşlarını konumlara atamak. Sorun, sorunun katlanarak büyümesidir. 16 domino taşınız varsa 16 seçeneğiniz vardır ilk domino için 15 seçenek, ikincisi için 15 seçenek ve bu böyle devam ederek yaklaşık 16 seçenek! toplam kombinasyonlar, ve bu yönelimleri göz ardı etmektir. Bunu bir arama ağacı gibi düşünebilirsiniz: İlk adımda 16 dalınız var. Bir sonraki adım için, her dalın 15 alt dalı vardır. Her alt dalın 14 alt alt dalı vardır ve bu böyle devam eder.

Kolay bir optimizasyon, her domino eklendikten sonra kısıtlamaları kontrol etmektir. Örneğin, en kısa sürede olarak "5'ten az" kısıtlaması ihlal edilirse,geri izlemeyiyapabilir ve tümünü atlayabilirsiniz ağacın bölümü. Bu şekilde ağacın yalnızca bir alt kümesinin aranması gerekir; Şube sayısı fazla olacak ama umarım yönetilebilir.

Kısıtlama çözücü benzer şekilde çalışır ancak daha soyut bir şekilde çalışır. Kısıtlama çözücü, değişkenlere değerler atar ve bir çakışma tespit edildiğinde geri izleme yapar. Temel problem tipik olarak NP-tamamlanmış olduğundan, çözücü, buluşsal yöntemi kullanarak çözüme ulaşmaya çalışır. performansı artırın. Örneğin değişkenler farklı sıralarda atanabilir. Çözücü oluşturmaya çalışır Arama ağacının büyük parçalarının daha sonra değil, daha erken budanabilmesi için çatışmalar mümkün olan en kısa sürede çözülebilir. (Domino örneğinde bu, dominoların en sıkı kısıtlamalara sahip yerlere yerleştirilmesine karşılık gelir. onları bulmacanın etrafına "kolay" şekilde dağıtmaktansa...