published on 10.06.2018

8x8 lik satranç tahtasına en az kaç at yerleştirilmeli ki tüm kareler korunsun?

Bakış Açısı

Eğer aklınıza hemen küme kaplama problemi geldiyse ve çözümü merak ediyorsunuz bu kısmı atlayıp sayfayı aşağı kaydırabilirsiniz ama varsayalım ki aklınıza küme kaplama problemi gelmedi. İlk başta benim aklıma gelmemişti ama yine de düşünelim nasıl çözeceğiz?

$$i, j \in {1,2,3,4,5,6,7,8}$$

Öncelikle probleme ait uzayı tanımlamak lazım. 2 boyutlu uzayda herbir i ve j için herbir kareyi K(i, j) tanımlasak yeterli olacaktır.

At, bir eksende 2 kare, diğer eksende 1 kare giderek ‘L’ şeklinde hareket eder. (2,1) (1,2) (-2,1)…

Buna göre $K(i,j)$ karesindeki atın koruyacağı (gidebileceği) kareler:

K(i + 2, j - 1), | K(i + 1, j + 2) K(i + 2, j + 1), | K(i + 1, j - 2) K(i - 2, j + 1), | K(i - 1, j + 2) K(i - 2, j - 1), | K(i - 1, j - 2)

olacaktır. Örnek bir kare için K(4,5) görselleştirelim:

visualization of the problem
visualization of the problem

K(i, j)‘yi eğer at atandıysa 1,

aksi halde 0 alacak binary değişken olarak tanımlayalım. Amaç fonksiyonu toplam at sayısını minimize etmek üzere tanımlayalım.

$$\min Z = \sum_i\sum_j K(i,j)$$

Geldik zor kısmına, öyle kısıtlar yazmalıyız ki tüm karelerin korunmasını sağlasın. Vaktinde (bir iki yıl önce) birkaç saat uğraşmıştım bu bakış açısı ile kısıtları oluşturmaya. Epey de ilerledikten sonra boşa kürek çektiğimi farketmiştim. Tekrar burada o modeli anlatmayacağım ama ikinci bir binary değişken (karenin korunup korunmadığına dair) daha tanımlayıp işleri karmaşıklaştırmıştım.

Şimdi doğru bakış açısıyla probleme tekrar bakalım.

set covering approach
set covering approach

Sözlü ifade etmek gerekirse; bir ‘X’ noktasını korumak için, yukarıdaki 8 alternatif konuma ‘AT’ yerleştirebilir. Diğer bir deyişle, Bir atın koruduğu karelere değil, bir kareyi koruyan atlara bakıyoruz. Buradan sonrası küme kaplama problemi ve çözümü belli.

Burada biraz felsefe yapacağım, hayattaki problemler karşısında önce problemi iyi anlamak, tanımlamak gerektiği ile ilgili. Bir konuya farklı bakış açılarıyla yaklaşabilmeliyiz; çünkü çözüme her zaman birden fazla yoldan ulaşabilir. Genellikle o yollardan bir ya da birkaç tanesi diğerlerine göre daha zahmetsiz olur.

Matematiksel Model

$$\min \sum_i\sum_j X_{i,j}$$

subject to;

$$ X_{i+2,\ j+1} + X_{i+2,\ j-1} + X_{i-2,\ j+1} + X_{i-2,\ j-1} + X_{i+1,\ j+2}+ X_{i+1,\ j-2} + X_{i-1,\ j+2}+X_{i-1,\ j-2} + X_{i,\ j}\ge 1 \qquad \forall {i,j} $$

$$X_{i,j} \in {0,1} \qquad \forall {i,j}$$

Bir at, yukarıdaki resimlerden de anlaşıldığı üzere çevresindeki 8 noktayı koruyabiliyor. Ek olarak kendi bulunduğu hücreyi de koruyor. X(i,j) hücresini atladığımızda modelimiz eksik ve sonucumuz da yanlış olur.

GAMS

GAMS syntaxında aşağıdaki gibi yazılabilir:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
SETS
I /1*8/;
ALIAS (I,J);
VARIABLE Z;
BINARY VARIABLE X(I,J);

EQUATION OBJECTIVE, CONSTRAINT;

OBJECTIVE.. Z =E= SUM(i, SUM(j, X(i,j)));

CONSTRAINT(i,j)..     X(i+2,j-1) + X(i+2, j+1) +
                 X(i-2,j+1) + X(i-2, j-1) +
                 X(i+1, j+2) + X(i+1, j-2) +
                 X(i-1, j+2) + X(i-1,j-2)+ X(i,j) =G= 1;


MODEL set_covering /all/;
SOLVE set_covering USING MIP MINIMIZE Z;
option optcr = 0.0;
DISPLAY X.L;

Optimal Çözüm

Model, CPLEX ile çözdürüldüğünde optimal çözümde amaç fonksiyonu değeri 12 olarak bulunmuştur, çözüm aşağıdadır.

Optimal Solution
Optimal Solution

Ek olarak, burada herbir (i,j) için gelen kısıtlarda, eşitsizliğin sol tarafı herbir karenin kaç at tarafından korunduğu bilgisini verir. Ne kadar ‘güçlü’ korunduğu şeklinde de açıklanabilir.

GAMS kodunda bir Positive Variable P(I,J) tanımlayıp sol tarafı P(i, j)‘ye eşitleyerek aşağıdaki matrise ulaşabiliriz:

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

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

Beklendiği gibi her kare en az 1 at tarafından korunuyor. Merkeze yakın kareler daha güçlü korunuyor. P(1,4), P(2,4), P(5,1), P(5,2), P(5,3) gibi…

Published on 10.06.2018 by Mert Bakır with commit 017b782.
linear-programming
#linear-programming #set-covering
published on 24.01.2021
edited on 11.06.2021

Some time ago, I wanted to display image galleries on my Hugo website and searched for Hugo themes for photography and gallery. I can’t say I find much. Then, I met with a javascript library called nanogallery2 which is using another javascript library as an image viewer lightbox2. In this …

published on 23.01.2021
edited on 11.06.2021

Image processing may seem complicated at first but it’s actually easy and definitely worth implementing since it’ll help you decrease page load times. As you probably know, we don’t want to load raw images with huge sizes for small thumbnails or blog-posts. We want to load a small …

published on 31.12.2020
edited on 26.06.2021

I’ve, recently, published a blog post called Perfect Workflow for Publishing Python Notebooks. I talked about some of the benefits of using Rmarkdown and reticulate. In this post, I’ll try HTML widgets and explain how we can embed those in our blog post using nothing but R. […] 1 …

published on 05.12.2020

Resume A4 is a side project of mine. It’s one page Hugo Theme that allows you to write your resume in YAML format and keep track of it using git. Also, you can publish it online as a static site using GitLab, GitHub Pages, Netlify, or some other service you are familiar with. A few months …

published on 30.11.2020

I’ve been searching for a good workflow for publishing Jupyter or RMarkdown Notebooks as static blog posts. I think I’ve found the optimal solution for my use case. In this post, I’ll explain my workflow and why chose this way with examples. […] In reality my main purpose to …

published on 29.11.2020
edited on 05.12.2020

Plotly is a visualization library that allows us to write code in Python, R, or Julia and generates interactive graphs using Javascript. So, we don’t have to deal with Javascript. You can checkout Plotly gallery, there are interesting works. Anyway, last week, I’ve started learning …