The N-Queens Problem Quiz

The N-Queens Problem

• The goal of the N-Queens problem is to place N chess queens on an N x N chessboard so that no two queens threaten each other.
• Queens can attack horizontally, vertically, and diagonally.
• A predicate p(i, j) is used to represent the presence of a queen in row i and column j of the chessboard.
• The problem can be solved using logic and propositional equivalences.

Problem Representation

• To express the N-Queens problem logically, a set of propositions is used.
• Proposition Q1 ensures that every row contains at least one queen.
• Proposition Q2 ensures that every row contains at most one queen (by using the negation of the predicate).
• Proposition Q3 guarantees that every column contains at most one queen.
• Propositions Q4 and Q5 check for the presence of more than one queen on diagonals.
• The solution to the N-Queens problem is provided by the assignments of truth values to the variables p(i, j) to make the combined proposition Q true, which is the conjunction of propositions Q1, Q2, Q3, Q4, and Q5.

Problem Complexity

• The number of possible ways to place N queens on a chessboard has been computed for values of N up to 27.
• There are 92 solutions for N = 8.
• For N = 16, the number of solutions grows to a significant 14,772,512.

Sudoku

• Sudoku puzzles are played on a 9 x 9 grid divided into nine 3 x 3 subgrids.
• Some cells are assigned numbers (givens) and others are blank.
• The goal is to fill in the blanks so that every row, column, and 3 x 3 subgrid contains all numbers from 1 to 9.
• The puzzle can be generalized to larger grids of size n^2 x n^2, including n x n subgrids.