http___projecteulercozum.blogspot.com.tr_2014_02_problem-96-su-doku.html_1.xml
1.1 1.2 2.1 3.1 3.2 3.3 3.4 3.5 4.1 4.2 4.3 4.4 5.1 6.1 7.1 8.1 9.1 9.2 10.1 11.1 11.2 12.1 13.1 14.1 14.2 14.3 14.4 15.1 16.1 17.1 18.1 19.1 19.2 20.1 21.1 21.2 21.3 22.1 22.2
Floyd-Warshall algorithm is a procedure, which is used to find the shorthest (longest) paths among all pairs of nodes in a graph, which does not contain any cycles of negative lenght. The main advantage of Floyd-Warshall algorithm is its simplicity. Description Floyd-Warshall algorithm uses a matrix of lengths as its input. If there is an edge between nodes and , than the matrix contains its length at the corresponding coordinates. The diagonal of the matrix contains only zeros. If there is no edge between edges and , than the position contains positive infinity. In other words, the matrix represents lengths of all paths between nodes that does not contain any intermediate node. In each iteration of Floyd-Warshall algorithm is this matrix recalculated, so it contains lengths of paths among all pairs of nodes using gradually enlarging set of intermediate nodes. The matrix , which is created by the first iteration of the procedure, contains paths among all nodes using exactly one (predefined) intermediate node. contains lengths using two predefined intermediate nodes. Finally the matrix uses intermediate nodes. This transformation can be described using the following recurrent formula: Because this transformation never rewrites elements, which are to be used to calculate the new matrix, we can use the same matrix for both and . Code procedure [array] FloydWarshall(D, P) for k in 1 to n do for i in 1 to n do for j in 1 to n do if D[i][j] > D[i][k] + D[k][j] then D[i][j] = D[i][k] + D[k][j] P[i][j] = P[k][j] return P /** * Floyd-Warshall algorithm. Finds all shortest paths among all pairs of nodes * @param d matrix of distances (Integer.MAX_VALUE represents positive infinity) * @return matrix of predecessors */ public static int[][] floydWarshall(int[][] d) { int[][] p = constructInitialMatixOfPredecessors(d); for (int k = 0; k   d[i][k] + d[k][j]) { d[i][j] = d[i][k] + d[k][j]; p[i][j] = p[k][j]; } } } } return p; } /** * Constructs matrix P0 * @param d matrix of lengths * @return P0 */ private static int[][] constructInitialMatixOfPredecessors(int[][] d) { int[][] p = new int[d.length][d.length]; for (int i = 0; i < d.length; i++) { for (int j = 0; j < d.length; j++) { if (d[i][j] != 0 && d[i][j] != Integer.MAX_VALUE) { p[i][j] = i; } else { p[i][j] = -1; } } } return p; } Asymptotic complexity The algorithm consists of three loops over all nodes, and the most inner loop contains only operations of a constant complexity. Hence the asymptotic complexity of the whole Floyd-Warshall algorithm is , where is number of nodes of the graph. Example Matrix of predecessors In order to return shortest (longest) paths among all pairs of nodes, we construct during transformations of matrix also output matrix (matrix of predecessors). The matrix can be read as follows: if we want to reconstruct the (shortest) path between nodes and , than we look at the element at corresponding coordinates. If its value is , than there is no path between these nodes, otherwise the value of the element denotes predecessor of on the path from to . So we repeat this procedure, while the preceding node is not equal to . Code function getPath(P, i, j) if i == j then write(i) else if P[i][j] = 0 then write("Path does not exist") else getPath(P, i, P[i][j]) write(j) Example Detection of cycles of (non)negative length Floyd-Warshall algorithm can be easily modified to detect cycles. If we fill negative infinity value at the diagonal of the matrix and run the algorithm, than the matrix of predecessors will contain also all cycles in the graph (the diagonal will not contain only zeros, if there is a cycle in the graph). Sources - KOLÁŘ, Josef. Teoretická informatika. Praha : Česká informatická společnost, 2004. - HANZÁLEK, Zdeněk. Kombinatorická optimalice, Nejkratší cesty - slides k přednáškám.
1.1 2.1 3.1 4.1 5.1 6.1 7.1 8.1 9.1 10.1 11.1 12.1 13.1 14.1 15.1 16.1 17.1 18.1 19.1 20.1 21.1 23.1 24.1 26.1 27.1 28.1 29.1 30.1 31.1 33.1 34.1 35.1 37.1 38.1 39.1 40.1 41.1 43.1 44.1 45.1 47.1 48.1 49.1 50.1 51.1 52.1 53.1 55.1 56.1 57.1 58.1 59.1 60.1 61.1 62.1 63.1
30 Ocak 2014 Perşembe Problem 96 - Su Doku Soru Japonca anlamı sayı yerleştirme olan Sudoku problemiyle karşı karşıyayız. Her bir satırı ve sütunu 1-9 arası sayıların tamamını birer kere içeren, 9x9'luk karelerden oluşuyor. Aynı zamanda 9 parçaya ayrılmış 3x3'lük kareleri de 1-9'a kadar olan sayıların hepsini barındırmalı. Soruda istenilen, .txt dosyası ile verilen 50 adet Sudoku'nun çözülmesi ve her Sudoku'nun ilk üç karesinin toplamlarının bulunması. Bu sayı örnekte 483. http://projecteuler.net/problem=96 http://projecteuler.net/project/sudoku.txt Çözüm Elbette her Sudoku'yu tek tek çözmeyeceğiz. Bunun için Sudoku çözen bir program yapmamız lazım. Bunun için öncelikle kuralları iyi belirlemeliyiz. 1) Her satırda 1-9 arası tüm sayılar bulunmalı 2) Her sütunda 1-9 arası tüm sayılar bulunmalı 3) Her üçlüde 1-9 arası tüm sayılar bulunmalı Çeşitli yollarla çözmek mümkün. Ben iki boyutlu tek bir bool dizi kullanarak çözme yolunu tercih ettim. Her bir sayı için matriste dolaşıp o sayıyı bulunduğunda, mevcut olduğu satır ve sütunları eleyen bir dizi. Çünkü her sayı bir satır, sütun ve üçlüde yalnızca bir kere bulunabilir. Öyleyse sayının bulunduğu satır, sütun ve üçlüleri elersek geriye kalan kareler bize sayının olası konumlarını verir. Bunu muhakkak bir kağıda çizerek denemelisiniz, zaten bu elemeleri yaptığınızda sistemin nasıl işlediği kolayca belli oluyor. Bundan sonra o satır, sütun ve üçlülerin özel olup olmadığını test edeceğiz. Buradan özelden kastım, o sayı mecburen orada mı olmalıdır, yani başka koyulacak bir yer yok mudur sorusunun cevabıdır. Fakat tüm bunlar yine yetersiz kalabilir ve başka bir yola başvurmak zorunda kalabiliriz. O durumda da mevcut olasılıkları deneyerek sonucun doğru çıktığı yolu bulmaya çalışacağız. Bu işin zor kısmı, ne de olsa zor sudokular için. Kodlama İlk başta basit kısmı ele alalım. Programın tüm işini yürüten parça bu kod. İşaretleme kısmı static void CheckingProcess(char Number) for (int a = 0; a < 9; a++) // Checking all true(possible) for (int b = 0; b < 9; b++) PossibleSquares[a, b] = true; for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) if (Board[i, j] == Number) EliminateSquares(i, j); ListingProcess(Number); Üstteki kodun ilk iki for döngüsü tüm kareleri true değerle işaretliyor. Sonrasındaki iki for döngüsü ise, EliminateSquares(KareleriEle) metotunu kullanarak belirlenen bir sayının matristeki i ve j konumunu göndererek o konumdaki üçlüyü, satır ve sütunu false olarak işaretliyor. Son olarak da ListingProcess(Listelemeİşlemi) yeni listeyi oluşturuyor. Eleme İşlemi static void EliminateSquares(int i, int j) for (int a = 0; a < 9; a++) // Eliminate row PossibleSquares[i, a] = false; for (int a = 0; a < 9; a++) // Eliminate column PossibleSquares[a, j] = false; EliminateTriad(i, j); Burada EliminateTriad(ÜçlüyüEle) fonksiyonunu ayrıca yazıp çağırdım. İlk for döngüsü satırı ikincisi ise sütunu karalıyor(false yapıyor). Satır Özel mi? static bool isRowUnique(int i, int j) byte count = 0; for (int a = 0; a < 9; a++) if (PossibleSquares[i, a] == true) count++; if (count > 1) return false; return true; Yukarıdaki kod ise, o satırda eğer sadece bir kareye bu sayı yerleştirilebiliyorsa true, eğer başka kareye de gelme olasılığı varsa false değerini döndürüyor. Eğer true dönerse, o sayı mecbur o kareye gelecektir ve biz de onu tahmine gerek kalmaksızın oraya koyabiliriz. Sayıyı kareye yerleştirme if (PossibleSquares[i, j] == true && (isRowUnique(i,j) || isColumnUnique(i,j) || isTriadUnique(i,j) )) Board[i, j] = Number; Üstteki kodda dikkat edilmesi gereken paranteze alınmış "veya" - "||" işlemleri. Sayının muhtemelen o kareye gelme ihtimalinin doğru olması ve o üç kuraldan sadece birinin geçerli olması oraya yerleştirmemiz için yeterli koşulu sağlıyor. Bu haliyle işleme aldığınızda 50 Sudoku'dan alınan sonuç aşağıdaki gibi oluyor. Dolayısıyla zor Sudoku'ları çözmek için tahmin yoluna da gideceğiz. Bunu da sonra ekleyeceğim. Gönderen Ögetay Kayalı zaman: 06:41 Etiketler: C#, Çözüm, Project Euler 96 Çözüm, Sudoku, Sudoku Çözücü Kaydol: Kayıt Yorumları (Atom)