Artificial Intelligence: Beyond Classical AI

CASE STUDY 1

N Queen Problem with Backtracking

N Queens problem is one of the most common examples of backtracking.

Goal: To place N Queens on an N×N chessboard in such a way that no two queens attack each other.

Input: The size of a chess board. Generally, it is 8 as a normal chess board has size = 8 X 8.

Output: A binary matrix that has 1s for the blocks where queens are placed. For example, the 4 X 4 matrix given below has 1 for positions, where 4 Queens can be safely placed - no queen attacking the other one.

{0, 1, 0, 0}

{0, 0, 0, 1}

{1, 0, 0, 0}

{0, 0, 1, 0}

Note that the matrix represents in which row and column the N Queens can be placed. The 0s in the matrix denotes the blank spaces on the chess board. If the solution does not exist, ...