Search

Problem potpunog prekrivanja razmatramo u kontekstu računalne konstrukcije (v, k, 1)-dizajna. Potrebno je pronaći k-člane blokove dizajna koji ujedno tvore egzaktno pokrivanje nad skupom parova svih točaka. Za traženje pokrivača koristimo algoritam X, algoritam kojeg je osmislio Donald Knuth. Knuthova implementacija oslanja se na metodu "dancing links". Program implementation of Donald Knuth's algorithm X is used to solve an exact cover problem for (v, k, 1)-designs. Algorithm finds k-sized subsets called blocks which cover a set of point pairs. Algorithm X is implemented using "dancing links" method.

Problem potpunog prekrivanja razmatramo u kontekstu računalne konstrukcije (v, k, 1)- dizajna. Potrebno je pronaći k-člane blokove dizajna koji ujedno tvore egzaktno pokrivanje nad skupom parova svih točaka. Za traženje pokrivača koristimo algoritam X, algoritam kojeg je osmislio Donald Knuth. Knuthova implementacija oslanja se na metodu "dancing links".

Multiple patterning lithography has been recognized as one of the most promising solutions, in addition to extreme ultraviolet lithography, directed self-assembly, nanoimprint lithography, and electron beam lithography, for advancing the resolution limit of conventional optical lithography. Multiple patterning layout decomposition (MPLD) becomes more challenging as advanced technology introduces complex coloring rules. Existing works model MPLD as a graph coloring problem; nevertheless, when complex coloring rules are considered, layout decomposition can no longer be modeled accurately by graph coloring. Therefore, in this paper, for capturing the essence of layout decomposition with complex coloring rules, we model the MPLD problem as an exact cover problem. We then propose a fast and exact MPLD framework based on augmented dancing links. Our method is flexible and general: it can consider the basic and complex coloring rules simultaneously, can maintain density balancing, and can handle quadruple patterning and beyond. Experimental results show that our approach outperforms state-of-the-art works on reported conflicts and stitches and is promising for handling complex coloring rules and density balancing as well.

Irregular subarray technology is presented in this paper for wide-angle scanning phased arrays. Based on the exact set cover theory and dancing links algorithm, a solution of the exact partition is developed using different kinds of irregular subarrays. Simulation results show that the irregular subarray architecture exhibits good radiation performances as well as no-sub array architecture.

In this paper a novel optimized graph referencing method is proposed to tackle combinatorial problems with greater ease. The proposed algorithm is a modification of the existing backtracking algorithm. It takes into account the advantage of backtrack algorithm while eliminating its disadvantages. Special care has been taken to reduce the time complexity in avoiding frequent unsuccessful searches and in providing accurate and fast solution to the targeted sub problem. The theoretical analysis and experimental results presented reveal the superiority of proposed algorithm over the conventional algorithms. I. Introduction A special branch of mathematics known as Combinatorics deals with the study of finite structure including counting the structure of a given kind and size, depending upon criteria to be met and analysis and constructs objectives meeting such criteria. Combinatorial problems find extensive application in fields of mathematics, machine learning, AI, Auction Theory, Software Engineering etc. Backtracking is a general algorithm for finding all or some solution to some combinatorial problems. However, Backtracking suffers inherent disadvantages in terms of conjunction of a large processing time and memory space. It is here that the proposed novel optimized graph referencing method established its superiority. The algorithm as proposed by the authors, which is a modification of conventional Backtracking algorithm, not only solves efficiently different combinatorial problems but does so in the least possible time. Tackling various combinatorial problems is a subject of research worldwide. Different efficient algorithms are being developed to this purpose. Xiao et. al. (1) designed a stepwise enumerative algorithm while another algorithm based on GA was developed by Liu et. al. (2). The Backtracking algorithm is reported to be used to solve Sudoku, a combinatorial problem, by Xu (3). The solution to the Sudoku problem was proposed by Zhang (4) who intend to use the application development language AutoLISP embedded in AutoCAD for this purpose. An altogether different algorithm to solve Sudoku was proposed by Zhao et. al. (5) while the same was tackled with the help of cultural algorithm and GA optimization as reported by Mantere and Kolijonen (6

Exact cover problem is a well-known NP-complete decision problem to determine if the exact cover really exists. In this paper, we show how to solve a modified version of the famous Hexomino puzzle (being a noteworthy example of an exact cover problem) using a Dancing-links based algorithm. In this modified problem, a limited number of gaps in the rectangular box may be left uncovered (this is a common scenario in a variety of spatial planning problems). Additionally, we present the benchmark generator which allows for elaborating very demanding yet solvable problem instances. These instances were used during the qualifying round of Deadline24—an international 24-h programming marathon. Finally, we confront our baseline solutions with those submitted by the contestants, and elaborated using our two solvers.

Multiple patterning lithography has been recognized as one of the most promising solutions, in addition to extreme ultraviolet lithography, directed self-assembly, nanoimprint lithography, and electron beam lithography, for advancing the resolution limit of conventional optical lithography. Multiple patterning layout decomposition (MPLD) becomes more challenging as advanced technology introduces complex coloring rules. Existing works model MPLD as a graph coloring problem; nevertheless, when complex coloring rules are considered, layout decomposition can no longer be modeled accurately by graph coloring. Therefore, in this paper, for capturing the essence of layout decomposition with complex coloring rules, we model the MPLD problem as an exact cover problem. We then propose a fast and exact MPLD framework based on augmented dancing links. Our method is flexible and general: It can consider the basic and complex coloring rules simultaneously, and it can handle quadruple patterning and beyond. Experimental results show that our approach outperforms state-of-the-art works on reported conflicts and stitches and is promising for handling complex coloring rules as well.

The N-Queens problem has been studied for over a century. The N-Queens problem may be solved using a variety of methods including backtracking algorithms and mathematical equations such as magic squares. We propose a more efficient approach to the most used technique, backtracking, by removing the threatened cells in order to decrease the number of trial and error steps.

This paper presents a fast algorithm for solving the n-queens problem. The basic idea of this algorithm is to use pre-computed solutions in 75% of the cases, while the remaining cases are solved by calling the Sosic's algorithm. The novelty of this algorithm is in the observation that these pre-computable cases exhibit a modular nature. In addition, the pre-computed solutions run 100 times faster than Sosic's algorithm in most cases.

There are several possible algorithms to automatically solve Sudoku boards; the most notable is the backtracking algorithm, that takes a brute-force approach to finding solutions for each board configuration. The performance of the backtracking algorithm is usually said to depend mainly on two implementation aspects: finding the next available empty cell in the board and finding the options of available legal number that are relevant to the given cell. While these pieces of the backtracking algorithm can vary in efficiency based on their implementation, tests show that the algorithm itself also relies on the statistical distribution of the guesses that it attempts to “plug in” to the board in every given cell. The backtracking algorithm uses an array of the legal numbers in the cell to attempt a solution before it moves on to the next cell. If a solution cannot be found, it backtracks and attempts to solve the board again with a different guess choice. The more errors the solver makes, the more backtracks it must perform, which decreases its overall efficiency and increases its effective runtime. Tests of the solving algorithm were performed using 195 base solutions with multiple initial board configurations were performed to analyze the difference in the algorithm performance by comparing the number of recursive backtracks between sequential and randomly distributed guesses. Analysis show that using values that are given in a shuffled array significantly reduces the number of backtracks done by the solver and, as a result, improve the total effective efficiency of the algorithm as a whole.

Backtracking algorithms are used to methodically and exhaustively search a solution space for an optimal solution to a given problem. A classic example of a backtracking algorithm is illustrated by finding all solutions to the problem of placing N-queens on an N × N chess board such that no two queens attack each other. This paper demonstrates a methodology for rewriting this backtracking algorithm to take advantage of multi-core computing resources. We accelerated a sequential version of the N-queens problem on ×86 and PPC64 architectures. Using problem sizes between 13 and 17, we observed an average speedup of 3.24 for ×86 and 9.24 for the PPC64.

Many tasks in combinatorial computation admit a natural formulation as instances of the exact cover problem. We observe that the exact cover problem can in turn be compactly translated to the satisfiability (SAT) problem, allowing the basic Davis-Putnam-Logemann-Loveland procedure with no clause learning to linearly simulate backtrack search for exact cover. This SAT-based approach is empirically compared with a widely applied backtrack search algorithm, Knuth's "Dancing Links X" algorithm, on a set of benchmark problems arising in combinatorial enumeration. The experimental results indicate that the current model-counting SAT solvers are in general superior in pruning the search space, but still need to be optimized for running time.

We discuss weighted deductive parsing and consider the problem of finding the derivation with the lowest weight. We show that Knuth's generalization of Dijkstra's algorithm for the shortest-path problem offers a general method to solve this problem. Our approach is modular in the sense that Knuth's algorithm is formulated independently from the weighted deduction system.

The n - queens problem is a classical combinatorial search problem. In this paper we give a linear time algorithm for this problem. The algorithm is an extension of one of our previous local search algorithms [3, 4, 6]. On an IBM RS 6000 computer, this algorithm is capable of solving problems with 3,000,000 queens in approximately 55 seconds.

The n -queens problem is often used as a benchmark problem for AI research and in combinatorial optimization. An example is the recent article [1] in this magazine that presented a polynomial time algorithm for finding a solution. Several CPU-hours were spent finding solutions for some n up to 500,000.

Previous algorithms presented to solve the eight queens problem have generated the set of all solutions. Many of these solutions are identical after applying sequences of rotations and reflections. In this paper we present a simple, clear, efficient algorithm to generate a set of fundamental (or distinct) solutions to the problem.

Configuring N mutually nonattacking queens on an N -by- N chessboard is a classical problem that was first posed over a century ago. Over the past few decades, this problem has become important to computer scientists by serving as the standard example of a globally constrained problem which is solvable using backtracking search methods. A related problem, placing the N queens on a toroidal board, has been discussed in detail by Poyla and Chandra. Their work focused on characterizing the solvable cases and finding solutions which arrange the queens in a regular pattern. This paper describes a new divide-and-conquer algorithm that solves both problems and investigates the relationship between them. The connection between the solutions of the two problems illustrates an important, but frequently overlooked, method of algorithm design: detailed combinatorial analysis of an overconstrained variation can reveal solutions to the corresponding original problem. The solution is an example of solving a globally constrained problem using the divide-and-conquer technique, rather than the usual backtracking algorithm. The former is much faster in both sequential and parallel environments.

AN EXTENSION of Knuth's algorithm for parsing context-free languages is considered. The algorithm proposed is not a left-sided parsing algorithm. It is shown how, by slightly changing the grammar, it is in many cases possible to attain unique parsing by means of an extension of Knuth's algorithm.

In this paper we will take a detailed look at a larger example of program analysis by transformation. We will be considering Algorithm 2.3.3.A from Knuth's «Fundamental Algorithms» Knuth (1968) (p. 357) which is an algorithm for the addition of polynomials represented using four-directional links. Knuth (1974) describes this as having «a complicated structure with excessively unrestrained goto statements» and goes on to say «I hope someday to see the algorithm cleaned up without loss of its efficiency». Our aim is to manipulate the program, using semantics-preserving operations, into an equivalent, high-level specification. The transformations are carried out in the WSL language, a «wide spectrum language» which includes both low-level program operations and high level specifications, and which has been specifically designed to be easy to transform