Search

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

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.

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.