Home » Machine Learning/Artificial Intelligence

N-Queens Problem- A type of Constraint Satisfactory Problem in Artificial Intelligence

In this article, we are going to study a famous Constraint Satisfactory Problem of Artificial Intelligence. We will study what the N-Queen problem is, what set of constraints it has and how the agent works while keeping all these constraints satisfied, and how the goal state is reached by the agent?
Submitted by Monika Sharma, on May 30, 2019

N-Queens problem is a well-known Constraint Satisfactory Problem of Artificial Intelligence. In this problem, we have an NxN square grid board and we have N queens which need to be placed on them. The queens should be placed on the board in such a way so that it satisfies the below-mentioned constraints:

  1. No row should contain more than one queen placed in it
  2. No column should contain more than one queen placed in it.
  3. Not more than one queen should be placed in the single diagonal.
  4. No row or column should be left without any queen placed in it.

On summing up all the constraints, we can conclude that each row and each column should contain exactly one queen in them, neither more nor less than that.

In this series of problems, mostly there are grids whose size is even in number, like 4, 6, 8 and so on. It should be noted that the minimum number of the grid that we can have in this problem is 4, not less than that.

Here the 4-Queen problem and the 8-Queen problem are the most popular in the N-Queen problem series. There can exist many solutions for solving this problem, which mean that the solution to these problems is not unique. Yet, one of those solutions to both these types are given below:

4-Queens problem

In the 4-Queens problem, we have a 4x4 grid and we have 4 queens to place on it. The layout for the 4-Queens problem while satisfying all the constraints is as follows:

4-queens problem in AI

8-Queens problem

In the 8-Queens problem, we have an 8x8 grid and we have 8-queens to place on it. The layout for the 8-Queens problem while satisfying all the constraints is as follows:

8-queens problem in AI






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL




Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.