A Non-Recursive Space-Efficient Blind Approach to Find All Possible Solutions to the N-Queens Problem
N-Queen’s problem is the problem of placing N number of chess queens on an NxN chessboard such that none of them attack each other. A chess queen can move horizontally, vertically, and diagonally. So, the neighbours of a queen have to be placed in such a way so that there is no clash in these three directions. Scientists accepts the fact that the branching factor increases in a nearly linear fashion. With the use of artificial intelligence search patterns like Breadth First Search (BFS), Depth First Search (DFS) and backtracking algorithms, many academics have identified the problem and found out a number of techniques to compute possible solutions to n-queen’s problem. The solutions using a blind approach, that is, uninformed searches like BFS and DFS, use recursion. Also, backtracking uses recursion for the solution of this problem. All these recursive algorithms use a system stack which is limited. So, for a small value of N, it exhausts the memory quickly though it depends on machine. This paper deals with the above problem and proposes a non-recursive DFS search-based approach to solve the problem to save system memory. In this work, Depth First Search (DFS) is used as a blind approach or uninformed search. This experimental study yields a noteworthy result in terms of time and space.
Code (1)
Tasks
AllN-Queens Problem - All Possible SolutionsSimilar Papers 제목 키워드 기반
Tiny Recursive Reasoning with Mamba-2 Attention Hybrid
Recent work on recursive reasoning models like TRM demonstrates that tiny networks (7M parameters) can achieve strong performance on abstract reasoning tasks through latent recursion -- iterative refinement in hidden rep…
From Causal Models To Counterfactual Structures
Galles and Pearl claimed that "for recursive models, the causal model framework does not add any restrictions to counterfactuals, beyond those imposed by Lewis's [possible-worlds] framework." This claim is examined caref…
counterfactualEvaluating the relationship between regularity and learnability in recursive numeral systems using Reinforcement Learning
Human recursive numeral systems (i.e., counting systems such as English base-10 numerals), like many other grammatical systems, are highly regular. Following prior work that relates cross-linguistic tendencies to biases …
Reinforcement LearningA Formulation of Recursive Self-Improvement and Its Possible Efficiency
Recursive self-improving (RSI) systems have been dreamed of since the early days of computer science and artificial intelligence. However, many existing studies on RSI systems remain philosophical, and lacks clear formul…
Global Neural CCG Parsing with Optimality Guarantees
We introduce the first global recursive neural parsing model with optimality guarantees during decoding. To support global features, we give up dynamic programs and instead search directly in the space of all possible su…
Sentence