Bugün, geçenlerde Square Tiling problemini çözmek için yazdığım problemi sizinle paylaşmak istiyorum. Bu problemi ilk olarak Kenneth H. Rosen'ın Discrete Mathematics and Its Applications kitabında görmüştüm. İşte problem şu şekilde:
 |
| Kenneth H. Rosen - Discrete Mathematics and Applications(6th Edition): Chapter 5.1 - Example 14 |
Özetleyecek olursak, amacımız L şeklinde trimonolar (right triomiones) kullanarak 2n x 2n boyutunda bir tahtayı, sadece 1 kare boş kalacak şekilde doldurmak. Yukarıda gördüğünüz sayfada n > 0 iken bunun mümkün olduğu tümevarım (induction) ile ispatlanmış. Ben ise bu ispattan yararlanarak bu problemi çözecek bir program yazmak istemiştim. İspatın kendisi inductive olduğunda bunu yapması aslen çok zor değildi. Genel olarak inductive ispatları recursive algoritmalara çevirmek çok zor değildir ancak tahtayı sürekli dörde bölme işlemini nasıl implement edeceğimden emin değildim. Bir süre sonra veri yapıları dersinde ağaçları işledikten sonra, nasıl yapacağımı buldum.
İlk önce her node'unun derecesi 0 ya da 4 olan bir ağaç oluşturmam gerekiyordu. Böylece 4 kareyi birleştirip 2 x 2 boyuntunda tahta oluşturabilirdim. Ardında bu işlemi tekrar ederek 2n x 2n biçiminde, istediğim büyüklükte bir tahta oluşturabilirdim. Bu işlemi ters yönde yaparak ise tahtaları 4'er 4'er ayırabilirdim.
Bir önceki kayıdımda paylaştığım GeneralTree.java sınıfı üzerine her node'un sahip olduğu çocuk sayısını bir sabit ile sınırlayan bir sınıf yazdım.
LimitedTree.java
package datastructures.trees; import datastructures.Position; public class LimitedTree<E> extends GeneralTree<E> { protected int lim; public LimitedTree(int lim) { this.lim = lim; } public LimitedTree(int lim, E ele) { this(lim); addRoot(ele); } @Override public void addChild(Position<E> p, E e) throws IllegalStateException { Node<E> parent = validate(p); Node<E> child = new Node<>(e, parent); if (numChildren(parent) == lim) throw new IllegalArgumentException("Full"); parent.add(child); size++; } }
Daha sonra bu sınıfın üzerini de limitin 4 olduğu bir sınıf yazdım.
QuadTree.java
package right_triominoes; import datastructures.trees.LimitedTree; public class QuadTree<E> extends LimitedTree<E>{ public QuadTree() { super(4); } }
Ve bu ağaçın leaflerinde bulunacak olan kareleri temsil etmesi için aşağıdaki sınıfı yazdım.
Square.java
package right_triominoes; public class Square { public char symbol; public boolean full; public Square(boolean full) { this.full = full; } public Square(boolean full, char symbol) { this.full = full; this.symbol = symbol; } public String toString() { if (full) return symbol + " "; else return ". "; } }
Daha sonra ise tahta üzerine yerleştireceğim triominoların sınıfını yazdım. Bu sınıfı yazarken daha önceki kayıdımda paylaştığım CircularList.java sınıfını kullandım. Basitçe açıklayacak olursak, 4 uzunluğunda içinde Square.java nesneleri bulunduran bir CircularList objesi bulundurmakta, bu 4 Square nesnesinden 3'ü dolu, 1'i boş. Bu CircularList objesini döndürek ise basitçe Triomino'yu döndürmüş oluyoruz. Döndürme işlemi CircularList'te headerin gösterdiği node'u değiştirerek yapılıyor böylece nodeları kaydırmaklar uğraşmamız oluyoruz. Triomino nesnesini oluştururken kaç kere döndüreleeğini belirtiyoruz ve kendisine rastegele bir karekter atıyor, böylece tahtayı ekrana basarken rahatça ayırt edilebiliyor.
Triomino.java
package right_triominoes; import java.util.ArrayList; import java.util.Iterator; import java.util.Random; import datastructures.Position; import datastructures.linkedlists.CircularList; public class Triomino implements Iterable<Square> { private CircularList<Square> circle; public Triomino(int r) { circle = new CircularList<>(new Square[] { new Square(false), new Square(true), new Square(true), new Square(true) }); circle.rotateRight(r); char symbol = (char)(48 + new Random().nextInt(75)); for (Position<Square> s : circle) s.getElement().symbol = symbol; } public static Triomino empty(int i, int j) { if (i == 0 && j == 0) return new Triomino(0); if (i == 0) return new Triomino(1); if (j == 0) return new Triomino(3); else return new Triomino(2); } public static Triomino empty(int p) { if (p == 0) return new Triomino(0); if (p == 1) return new Triomino(1); if (p == 2) return new Triomino(3); else return new Triomino(2); } @Override public Iterator<Square> iterator() { ArrayList<Square> list = new ArrayList<>(4); list.add(circle.get(0).getElement()); list.add(circle.get(1).getElement()); list.add(circle.get(3).getElement()); list.add(circle.get(2).getElement()); return list.iterator(); } }
Ve sıra sonunda geldi, problemin kendisini çözdüğümüz sınıfa. Sınıf adını 4 kişiyle yapılan bir dansdan alıyor, tam olarak doğru anlamda kullandığımda emin değilim ama ilk olarak John Conway'in bu terimi kullandığını görmüştüm ve çok hoşuma gitti. Bu sınıfla ilgili açıklamaları zamanında kendi üzerine ingilizce olarak yapmıştım. Eğer programın nasıl çalıştığını görmek istersiniz diye eclipse projesi olarak zipleniş halinin linkini aşağıya koyuyorum.
Quadrille.java
package right_triominoes; import java.util.Iterator; import datastructures.Position; /* * A quadrille is a regular tiling of the Euclidean plain with vertex * configuration 4.4.4.4. which means that it has 4 squares around every * vertex. This can be represented using a quad tree which has 4 another * quadrilles at every vertex except the leafs. * * Apart from the implementation details, it reperesents no more than a * checkerboard for this problem which is tiling a checkerboard with one * square left empty using only right triominoes. */ public class Quadrille { /* A quad tree that represents a checkerboard. */ private QuadTree<Quadrille> quadTree; /* * The height of the quad tree. * * (!) Notice that this is not the actual height of the quadTree and * all of the quadTree variables has the height 1. */ public int height; /* The side length of the checkerboard the quad tree represents. */ public int length; /* The middle of a side of the checkboard the quad tree represents. */ public int middle; /* * A square of the checkerboard the quad tree represent. The square has * two posible values, which are full and empty. Notice that the value * of the squares is meaningful only at the leafs of the quadTree. */ public Square square; /* * Constructs a quadrille which is essantially a checkerboard with the * side length of 2^n. As the problem states, it is only possible to * solve when the size of the checkerboard is 2^n x 2^n. Initially all * the squares are set to empty. */ public Quadrille(int n) { quadTree = new QuadTree<>(); quadTree.addRoot(this); height = n; length = (int) Math.pow(2, height); middle = length >> 1; square = new Square(false); // base case for the construction of quadrille if (height == 0) return; // adds a new quadrille to the root which is "this" for (int i = 0; i < 4; i++) extend(new Quadrille(height - 1)); } /* Syntactic sugar */ private void extend(Quadrille quad) { quadTree.addChild(quadTree.root(), quad); } /* Syntactic sugar */ private Position<Quadrille> divide(int i) { return quadTree.getChild(quadTree.root(), i); } /* * Divides the checkerboard into 4 checkerboards and returns the part * with the index i. The indexes are listed as below: * ____ ____ * | 1| 2| * |____|____| * | 3| 4| * |____|____| */ public Quadrille getPart(int i) { return divide(i).getElement(); } /* * Returns the quadrille at the coordinates (i, j). Notice the returned * quadrille is a leaf of the quadTree. * * This method determines the part of the checkerboard which (i, j) is * located. Then keeps doing it recursively until it reaches to (i, j). * * If we assume there are n squares on the checkerboard. The running * time of this method is O(log_4(n)). */ public Quadrille getCoor(int i, int j) { if (height == 0) return this; if (i - middle >= 0 && j - middle >= 0) return getPart(3).getCoor(i - middle, j - middle); else if (i - middle >= 0) return getPart(2).getCoor(i - middle, j); else if (j - middle >= 0) return getPart(1).getCoor(i, j - middle); else return getPart(0).getCoor(i, j); } /* * Returns the square at the coordinate (i, j). */ public Square getSquare(int i, int j) { return getCoor(i, j).square; } /* * Sets the square at the coordinate (i, j). * * If the current square is full and the new square is empty, current * square will stay as full. */ public void setSquare(int i, int j, Square square) { if (square.full) getCoor(i, j).square = square; } /* * Adds the triomino the the coordinate (i, j). * * When instatiating triomino, give an integer parameter to determine * how many rotation it wil make. */ public void add(int i, int j, Triomino triomino) { Iterator<Square> iter = triomino.iterator(); for (int ip = 0; ip < 2; ip++) for (int jp = 0; jp < 2; jp++) setSquare(i + ip, j + jp, iter.next()); } /* * Solves the problem with empty square at the coordinates (i, j). * * The checkerboard is divided into 4 pieces until 4 checkerboard with * 2 x 2 size is reached. It is trivial to solve the problem for 2 x 2 * sized checkerboards, therefore all of them can be solved easily. * Thereafter an triomino is put into the middle of them. * * More detailed explanaion of the algorithm is explained in the * relevent parts of the code below. */ public void solve(int i, int j) { // Base Case: It is solved trivially if (height == 1) { add(0, 0, Triomino.empty(i, j)); return; } boolean left = i < middle; // at the left side of checkerboard boolean up = j < middle; // at the right side of the checkerboard // determines where the empty square is int part = left && up ? 0 : left ? 1 : up ? 2 : 3; int counter = 0; // counts the parts int corners[] = {middle - 1, 0}; int offsets[] = {0, middle}; for (int x = 0; x < 2; x++) for (int y = 0; y < 2; y++) if (part != counter) // solves the other parts getPart(counter++) .solve(corners[x], corners[y]); else // solves the part with empty square getPart(counter++) .solve(i - offsets[x], j - offsets[y]); // puts a triomino into the part at the middle add(middle - 1, middle - 1, Triomino.empty(part)); } /* * Prints the checkerboard representation with random symbols. * * There is no guarantee that every triomino next to each other will * have distinct symbols. */ public void print() { for (int i = 0; i < length; i++) { for (int j = 0; j < length; j++) { System.out.print(getSquare(i, j)); } System.out.println(); } } // Example public static void main(String[] args) { Quadrille q = new Quadrille(3); q.solve(0,0); q.print(); } }
Bitirmeden öncede eklemek istediğim birkaç şey var. Triomino sınıfında indeksler saat yönünde, Quarille sınıfında ise her dörtlü grup için önce sağa sonra aşağı doğru sıraladığımdan dolayı Triomino sınıfında empty isimli aptal methodlar yazmak zorunda kaldım ama farkettiğimde iş işten çoktan geçmişti. Bir daha da dönüp uğraşmaya üşendim.
Teşekkürler.
Buraya tıklayarak programı indirebilir ve kendiniz deneyebilirsiniz.
Hiç yorum yok:
Yorum Gönder