Solving the n-queen puzzle

Question

I have just solved the n queens problem in python. The solution outputs the total number of solutions for placing n queens on an nXn chessboard but trying it with n=15 takes more than an hour to get an answer. Can anyone take a look at the code and give me tips on speeding up this program...... A novice python programmer.

 #!/usr/bin/env python2.7

##############################################################################

# a script to solve the n queen problem in which n queens are to be placed on

# an nxn chess board in a way that none of the n queens is in check by any other

#Queen using backtracking'''

##############################################################################

import sys

import time

import array

solution_count = 0

def queen(current_row, num_row, solution_list):

    if current_row == num_row:

        global solution_count 

        solution_count = solution_count + 1

    else:

        current_row += 1

        next_moves = gen_nextpos(current_row, solution_list, num_row + 1)

        if next_moves:

            for move in next_moves:

                '''make a move on first legal move of next moves'''

                solution_list[current_row] = move

                queen(current_row, num_row, solution_list)

                '''undo move made'''

                solution_list[current_row] = 0

        else:

            return None

def gen_nextpos(a_row, solution_list, arr_size):

    '''function that takes a chess row number, a list of partially completed 

    placements and the number of rows of the chessboard. It returns a list of

    columns in the row which are not under attack from any previously placed

    queen.

    '''

    cand_moves = []

    '''check for each column of a_row which is not in check from a previously

    placed queen'''

    for column in range(1, arr_size):

        under_attack =  False

        for row in range(1, a_row):

            '''solution_list holds the column index for each row of which a queen has been placed  and using the fact that the slope of diagonals to which a previously placed queen can get to is 1 and that the vertical positions to which a queen can get to have the same column index, a position is checked for any threatening queen '''

            if (abs(a_row - row) == abs(column - solution_list[row]) 

                    or solution_list[row] == column):

                under_attack = True

                break

        if not under_attack:

            cand_moves.append(column)

    return cand_moves

def main():

    '''

    main is the application that sets up the program for running. It takes an integer input, N, from the user representing the size of the chessboard and passes as input,0, N representing the chessboard size and a solution list to hold solutions as they are created. It outputs the number of ways N queens can be placed on a board of size NxN.

    '''

    #board_size =  [int(x) for x in sys.stdin.readline().split()]

    board_size = [15]

    board_size = board_size[0]

    solution_list = array.array('i', [0]* (board_size + 1))

    #solution_list =  [0]* (board_size + 1)

    queen(0, board_size, solution_list)

    print(solution_count)

if __name__ == '__main__':

    start_time = time.time()

    main()

    print(time.time() 

Answer 1

In Backtracking Algo, the idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we examine for clashes with already placed queens. In the current column, if we encounter a row for which there is no clash, we mark this row and column as part of the solution. If we are not able to find such a row due to clashes then we backtrack and return false. The backtracking algorithm to the N-Queens problem is factorial in the worst case. So, for N=8, 8! the number of solutions is checked in the worst case, N=9 makes it 9! etc. As we can observe, the number of possible solutions grows very large, very fast. If you don't believe me, just go to a calculator and start multiplying consecutive numbers, starting at 1. Let me know how fast the calculator runs out of memory.

Fortunately, not every possible solution must be checked. Unfortunately, the number of correct solutions still follows a roughly factorial growth pattern. Thus the running time of the algorithm grows at a factorial pace.

Since you need to find all the correct solutions, there's not much that can be done about speeding up the program. You've already done a good job of pruning impossible branches from the search tree. I don't think there's anything else that will have a major effect. It's simply a slow algorithm.

If you wish to learn about Python then visit this Python Course designed by Industrial Experts.