Skip to main content

States, Initial state, Successor function, Action, Goal test, and Path cost to formulate 8-Queens problem.

asked by MU in Nov-2019 examination

The 8-Queens problem can be defined as follows : 

Place 8 queens on a (8 by 8) chess board such that none of the queen attack any of other.

States:

Any arrangement of 0 to 8 queens on the board.

Initial State:

No queen on the board.

Successor Function:

Add a queen to an empty field on the board.

Action:

Placing a queen on the board.

Goal Test:

8 queens on the board such that no queen attack another.

Path Cost:

0 (We are only interested in solution).

Theory:

  • This problem can be solved by searching for a solution.
  • This formulation as a search problem can be improved when we realize that, in any solution, there must be exactly one queen in each of the column.
  • Thus, the possible action can be restricted to placing a queen in the next column that does not yet contain a queen. This reduces the branching factor from (initially) 64 to 8.
  • Furthermost, we need to consider only those rows in the next column that are not already attacked by a queen that was previously on the board.
  • This is because placing of further queens on the board can never remove the mutual attack and turn the configuration into a solution.
Labels:
Location: Alibag, Maharashtra, India

Comments

Post a Comment

Popular posts from this blog

Utility-Based Agent

asked by MU in Nov-2019 & Apr-2019 examination     The agents which are developed having their end users as building blocks are called utility-based agents . When there are multiple possible alternatives, then to decide which one is best, utility-based agents are used. They choose actions based on performance (utility) for each state. These agents are similar to goal-based agents but provide an extra component of utility measurement which makes them different by providing a measure of success at a given state. Utility-based agents act based not only on goals but also the best way to achieve the goal. The utility function maps each state to a real number to check how efficiently each action achieves the goal. Agent's happiness should be taken into consideration. Utility describes how "happy" the agent is. 
Post a Comment
Read more

How can I keep my code in mind?

Many newcomers ask this query. Do programmers memorize everything? Do they memorize the entire documentation and programming language? Do I have to remember every detail to qualify as a professional developer? There is a resounding NO to each of these. The goal will never be achieved by memorization of the code. Today, almost every piece of information can be looked up directly from a computer or smartphone. The most crucial ideas will survive in your head because you apply them repeatedly, while the more enigmatic ideas will be permanently preserved online. Every time you need them, just a fast Google search. A developer's most frequently utilized resource is.... google.com Good programmers don't waste time trying to learn everything by heart. They do a good job of understanding the topics, reading the documentation, and correctly using Google to fill in the blanks. There will never be a time in programming where you can say, "I have learnt and mastered everything" i...
Post a Comment
Read more