Know a bit about the Queen piece in a game of Chess

A solution for the “8 queens” problem

Numberphile video:

You can have access to all the Lynda.com resources with your own Princeton Public Library card.

The problem: Design and implement a recursive program that solves the Non- Attacking Queens problem. That is, write a program to determine how eight queens can be positioned on an eight-by-eight chessboard so that none of them are in the same row, column, or diagonal as any other queen. There are no other chess pieces on the board.

Assignment:
If you already implemented the solution to the problem, answer the following questions:

1. How does your implementation compare to the one below?
2. Is your implementation better than this one?
3. What is the time complexity (for now we can say the big-O notation)?

If you have not implemented yet, do the following:

1. Trace the code for 4 queens. It only has 2 solutions but 1 unique.
2. Explain how the implementation works
3. What is the time complexity (for now we can say the big-O notation)?

//********************************************************************
//
//  A recursive program that solves the Non-attacking Queens problem.
//********************************************************************

public class NonAttackingQueens {

    int[] queens;   // Queen i is always placed in row i.  The
                    // column is variable.
                    // queens[i] represents the column of the ith row 
                    // where the ith queen is
    
    final int NUM_QUEENS = 8;
 
    public NonAttackingQueens()
    {
        queens = new int[NUM_QUEENS];
    }

    //-----------------------------------------------------------------
    //  Returns true if a queen queenNumber can be placed in column 
    //----------------------------------------------------------------- 
    boolean canPlace(int queenNumber, int column)
    {
        for (int row = 0; row < queenNumber; row++) // check all rows above queenNumber row
        {

            if (queens[row] == column) // in the same column
                return false;
            if (Math.abs(queens[row] - column) == Math.abs(row - queenNumber)) // same diagonal
                return false;
        }
        return true;
    }
    
    //-----------------------------------------------------------------
    //  Starting with the row represented by queenNumber, find all correct 
    //  placements in the row and below the row.
    //-----------------------------------------------------------------
    public void solve(int queenNumber)
    {
        for (int column = 0; column < NUM_QUEENS; column++)  // iterate through all columns
        {
            if (canPlace(queenNumber, column)) // queen can be placed in current column
            {
                queens[queenNumber] = column;  // place queen in current column

                if (queenNumber + 1 >= NUM_QUEENS) // solved
                    printSolution();
                else    // keep looking
                    solve(queenNumber + 1);
            }
        }
    }

    //-----------------------------------------------------------------
    //  Computes and displays all solutions to the problem
    //-----------------------------------------------------------------    
    public void showSolutions()
    {
        solve(0);  // start with the first row
    }
    
    //-----------------------------------------------------------------
    //  Prints a grid showing the position of the queens on the chessboard.  
    //  Queen = X
    //  Empty space = O
    //-----------------------------------------------------------------    
    private void printSolution()
    {
        int column;
        for (int row=0; row<num_queens; row++)="" {="" for="" (column="0;" column<num_queens;="" column++)="" if="" (queens[row]="=" column)="" system.out.print("="" x");="" else="" 0");="" system.out.print("\n");="" }="" system.out.println("\n-----------------------");="" public="" static="" void="" main="" (string="" args[])="" new="" nonattackingqueens().showsolutions();="" <="" pre=""></num_queens;>