need help with this code because I am struggling and I don't know what to do : question: you will develop a solver for the n-queens problem: n queens are to be placed on an n x n chessboard so that no pair of queens can attack each other. Recall that in chess, a queen can attack any piece that lies in the same row, column, or diagonal as itself. A brief treatment of this problem for the case where n = 8 is given below (from the 3rd edition of AIMA). N-queens is a useful test problem for search, with two main kinds of formulation. An incremental formulation involves operators that augment the state description, starting with an empty state; for the 8-queens problem, this means that each action adds a queen to the state. A complete-state formulation starts with all 8 queens on the board and moves them around. (In either case, the path cost is of no interest because only the final state counts.) The first incremental formulation one might try is the following, but (!) there are a very large number of states: States: Any arrangement of 0 to 8 queens on the board is a state. Initial state: No queens on the board. Actions: Add a queen to any empty square. Transition model: Returns the board with a queen added to the specified square. Goal test: 8 queens are on the board, none attacked. This formulation is based on 64 locations for the first piece, 63 for the second, and so on; thus 64 × 63 . . . × 57, or roughly 1.8 × 10^14 possible sequences to investigate. A better incremental formulation prohibits placing a queen where it would already be attacked: States: All possible arrangements of n queens (n ∈ [0,8]), one per column in the leftmost n columns, with no queen attacking another. Actions: Add a queen to any square in the leftmost empty column such that it is not attacked by any other queen. This formulation reduces the 8-queens state space by a factor of 10^10 to 2,057 tasks:Rather than performing a search over all possible placements of queens on the board, it is sufficient to consider only those configurations for which each row contains exactly one queen. Without taking any of the chess-specific constraints between queens into account, implement the pair of functions num_placements_all(n) and num_placements_one_per_row(n) that return the number of possible placements of n queens on an n x n board without or with this additional restriction. You should assume that all queens are indistinguishable for the purposes of your calculations. With the answer to the previous question in mind, a sensible representation for a board configuration is a list of numbers between 0 and n - 1, where the ith number designates the column of the queen in row i for 0 ≤ i < n. A complete configuration is then specified by a list containing n numbers, and a partial configuration is specified by a list containing fewer than n numbers. Write a function n_queens_valid(board) that accepts such a list and returns True if no queen can attack another, or False otherwise. Note that the board size need not be included as an additional argument to decide whether a particular list is valid. Your solution should handle a board up to size 6 to get full points here, and up to size 8 for use in the next problem. >> n_queens_valid([0, 0]) False >>> n_queens_valid([0, 2]) True >>> n_queens_valid([0, 1]) False >>> n_queens_valid([0, 3, 1]) True Write a function n_queens_solutions(n) that yields all valid placements of n queens on an n x n board, using the representation discussed above. The output may be generated in any order you see fit. Your solution should be implemented as a depth-first search, where queens are successively placed in empty rows until all rows have been filled. >>> solutions = n_queens_solutions(4) >>> next(solutions) [1, 3, 0, 2] >>> next(solutions) [2, 0, 3, 1] >>> list(n_queens_solutions(6)) [[1, 3, 5, 0, 2, 4], [2, 5, 1, 4, 0, 3], [3, 0, 4, 1, 5, 2], [4, 2, 0, 5, 3, 1]] >>> len(list(n_queens_solutions(8))) 92

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

I need help with this code because I am struggling and I don't know what to do :

question:

you will develop a solver for the n-queens problem: n queens are to be placed on an n x n chessboard so that no pair of queens can attack each other. Recall that in chess, a queen can attack any piece that lies in the same row, column, or diagonal as itself.

A brief treatment of this problem for the case where n = 8 is given below (from the 3rd edition of AIMA).

N-queens is a useful test problem for search, with two main kinds of formulation. An incremental formulation involves operators that augment the state description, starting with an empty state; for the 8-queens problem, this means that each action adds a queen to the state. A complete-state formulation starts with all 8 queens on the board and moves them around. (In either case, the path cost is of no interest because only the final state counts.) The first incremental formulation one might try is the following, but (!) there are a very large number of states:

  • States: Any arrangement of 0 to 8 queens on the board is a state.
  • Initial state: No queens on the board.
  • Actions: Add a queen to any empty square.
  • Transition model: Returns the board with a queen added to the specified square.
  • Goal test: 8 queens are on the board, none attacked.

This formulation is based on 64 locations for the first piece, 63 for the second, and so on; thus 64 × 63 . . . × 57, or roughly 1.8 × 10^14 possible sequences to investigate. A better incremental formulation prohibits placing a queen where it would already be attacked:

  • States: All possible arrangements of n queens (n ∈ [0,8]), one per column in the leftmost n
    columns, with no queen attacking another.
  • Actions: Add a queen to any square in the leftmost empty column such that it is not attacked by any other queen.

This formulation reduces the 8-queens state space by a factor of 10^10 to 2,057

tasks:Rather than performing a search over all possible placements of queens on the board, it is sufficient to consider only those configurations for which each row contains exactly one queen. Without taking any of the chess-specific constraints between queens into account, implement the pair of functions num_placements_all(n) and num_placements_one_per_row(n) that return the number of possible placements of n queens on an n x n board without or with this additional restriction. You should assume that all queens are indistinguishable for the purposes of your calculations.

With the answer to the previous question in mind, a sensible representation for a board configuration is a list of numbers between 0 and n - 1, where the ith number designates the column of the queen in row i for 0 ≤ i < n. A complete configuration is then specified by a list containing n numbers, and a partial configuration is specified by a list containing fewer than n numbers. Write a function n_queens_valid(board) that accepts such a list and returns True if no queen can attack another, or False otherwise. Note that the board size need not be included as an additional argument to decide whether a particular list is valid. Your solution should handle a board up to size 6 to get full points here, and up to size 8 for use in the next problem.

>> n_queens_valid([0, 0])
False

>>> n_queens_valid([0, 2])
True

>>> n_queens_valid([0, 1])
False

>>> n_queens_valid([0, 3, 1])
True

Write a function n_queens_solutions(n) that yields all valid placements of n queens on an n x n board, using the representation discussed above. The output may be generated in any order you see fit. Your solution should be implemented as a depth-first search, where queens are successively placed in empty rows until all rows have been filled.

>>> solutions = n_queens_solutions(4)

>>> next(solutions)
[1, 3, 0, 2]

>>> next(solutions)
[2, 0, 3, 1]

>>> list(n_queens_solutions(6))
[[1, 3, 5, 0, 2, 4], [2, 5, 1, 4, 0, 3],
[3, 0, 4, 1, 5, 2], [4, 2, 0, 5, 3, 1]]

>>> len(list(n_queens_solutions(8)))
92

Expert Solution
steps

Step by step

Solved in 3 steps with 1 images

Blurred answer
Knowledge Booster
Computational Systems
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education