Download as DOCX, PDF, TXT or read online from Scribd
Download as docx, pdf, or txt
You are on page 1/ 6
DEPARTMENT OF COMPUTER SCIENCE & TECHNOLOGY
(SCHOOL OF ENGINEERING) Department of CST (Artificial Intelligence – CSH205B-P)
ARTIFICAL INTELLEGENCE (MINI PROJECT) N-Queens Problem
Submitted to: Mr. Narender Submitted by: Course: B-tech CSE CSTI4 G Keerthana (2K22CSUN01231) Ch Akshaya (2K22CSUN01226) Vishal (2K22CSUN01253)
Turbo Language Features
Turbo C and Turbo Pascal were popular integrated development environments (IDEs) developed by Borland in the late 1980s and early 1990s. They were known for their fast compile speed, low price, and comprehensive manuals
Turbo C was an IDE for programming in the C language. It shared many
features with Turbo Pascal, including the look-and-feel of the interface and various programming and debugging tools
Turbo Pascal, on the other hand, introduced object-oriented programming
features for the Pascal language, such as classes, static and dynamic objects, constructors and destructors, and inheritance.
Problem Description:
The N-Queens problem is a chess puzzle that involves placing N queens on an NxN chessboard in such a way that no two queens threaten each other. The goal is to find a configuration where no two queens share the same row, column, or diagonal. The problem has received extensive research in computer science and mathematics and is frequently used as a standard for evaluating algorithms and heuristics. The significance of the N-Queens problem in AI and computer science lies in its complexity and its applications in various fields. Here are a few key points:
1. Algorithm Evaluation: The N-Queens problem serves as a benchmark for
evaluating the efficiency and effectiveness of algorithms and heuristics. Researchers and developers use it to compare different approaches and measure their performance in solving combinatorial problems. 2. Backtracking and Search: The N-Queens problem is often used to illustrate the concept of backtracking, a technique for systematically exploring all possible solutions. Backtracking algorithms, such as depth-first search, can be applied to find valid configurations of queens on the chessboard. 3. Constraint Satisfaction Problems: The N-Queens problem is a classic example of a constraint satisfaction problem (CSP). CSPs involve finding solutions that satisfy a set of constraints. The N-Queens problem demonstrates how constraints can be defined and used to solve real-world problems. 4. Applications in Computer Vision: The N-Queens problem has practical applications in computer vision, where it can be used to solve problems like object recognition and tracking. The problem's constraints and solution space can be adapted to address similar challenges in image analysis and pattern recognition. 5. Educational Purposes: The N-Queens problem is often used as an educational tool to teach problem-solving techniques, algorithm design, and logic programming. It helps students develop critical thinking skills and understand fundamental concepts in AI and computer science.
Approach:
The N-Queens problem can be solved using the backtracking algorithm in Turbo Prolog. Here is a general description of the approach: 1. Start by placing the first queen in the first row and the first column of the chessboard. 2. Move to the next row and try to place a queen in each column of that row, one by one. 3. Check for clashes: For each column, check if placing a queen in that position would lead to a clash with any previously placed queens. Clashes can occur if two queens are in the same row, column, or diagonal. 4. Backtrack if clash occurs: If placing a queen in a particular column of the current row leads to a clash, backtrack to the previous row and try placing the queen in the next column of that row. 5. Repeat steps 3-4: Repeat the process of checking for clashes and backtracking until a valid configuration is found or all possibilities have been exhausted. 6. Print or store solutions: Once a valid configuration is found, either print it or store it as a solution. Continue the backtracking process to find all possible solutions. The backtracking algorithm explores all possible configurations by systematically placing queens on the chessboard and checking their validity. If a queen cannot be placed in a particular position without threatening another queen, the algorithm backtracks and explores other possibilities.
Implementation:
Code: % Place N queens on an NxN chessboard so that no two queens attack each other.
% This is done by representing the board as a list of integers where each
integer
% represents the column position of a queen in the corresponding row.
% A queen can be placed in the first row (Row 1) at Column if no other queen is already placed
% in Column and if no other queen is placed in the same diagonal as (Row,
Column).
% The column positions are represented by integers from 1 to N.
% Facts
% queen(Row, Column) represents a queen placed at (Row, Column)
% no attack between two queens in the same row
safe_queen(_, []).
safe_queen(Row, [Column|Queens]) :-
no_attack(Row, Column, Queens, 1),
NextRow is Row + 1,
safe_queen(NextRow, Queens).
% no_attack(Row, Column, Queens, Offset) checks if a queen at (Row, Column)
can attack
% any queen in Queens. Offset is the current row offset from Row being checked.
Based on the search results, there are limited specific findings or insights related to solving the N-Queens problem in Turbo Prolog. The N-Queens problem can be solved in Turbo Prolog using various techniques, including backtracking and constraint logic programming (CLP).
o Backtracking involves systematically placing queens on the chessboard
and checking their validity, backtracking when necessary.
o CLP allows for the use of constraints to model and solve the problem.
2. The backtracking algorithm is a popular and intuitive approach for solving the N-Queens problem.
o It involves placing queens row by row and backtracking when an invalid
configuration is encountered.
o The algorithm explores all possible configurations until a valid solution
is found or all possibilities have been exhausted.
3. Constraint logic programming (CLP) can be used in Turbo Prolog to solve the N-Queens problem.
o CLP allows for the expression of constraints and automatic solution
finding. o CLP constraints are commonly used for combinatorial tasks like the N- Queens problem.
4. While specific Turbo Prolog code examples or reports are not readily available, there are resources and examples available for solving the N-Queens problem in other Prolog systems like SWI-Prolog.
o These examples can provide insights into the implementation of the
