N-queen puzzle solution

Question

I just solved the nkeen problem in python. The solution displays the total number of solutions for placing n queens on the nXn chessboard, but when trying to use n = 15, it takes more than an hour to get an answer. Can someone take a look at the code and give me advice on speeding up this program ...... Newbie programmer in python.

#!/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 same column index, a position is checked for any threating 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 which 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 chess board 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

The N-Queens backtracking algorithm is the worst case factorial algorithm. So, for N = 8, 8! the number of decisions is checked in the worst case, N = 9 makes it 9 !, etc. As you can see, the number of possible solutions is growing very large, very fast. If you don’t believe me, just go to the calculator and start multiplying consecutive numbers starting with 1. Let me know how quickly the calculator ran out of memory.

Fortunately, you do not need to check all possible solutions. Unfortunately, the number of correct decisions still follows an approximately factorial picture of growth. Thus, the running time of the algorithm grows with factorial.

Since you need to find all the right solutions, really not much can be done to speed up the program. You have already done a good job trimming impossible branches from the search tree. I do not think that there is anything else that will have a big effect. This is just a slow algorithm.

Answer 2

Just saw this question. I would like to make 2 decisions.

• This one returns all the different solutions.

• This returns the correct solution found

Feedback is welcome. Greetings

Answer 3

The number of decisions can be estimated using the Donald Knuth randomized estimation method.

Starting with no queens, the number of allowed positions for the next line is n. We randomly select one of the positions and calculate the number of allowed positions (p) for the next row, and this is a few by n and save it as the total number of solutions (total = n * p), then randomly select one of the allowed positions.

For this row, calculate the number of allowed positions (p) for the next row and multiply the total number of solutions by this (total * = p). Repeat this until the board has been resolved, in which case the number of decisions will be zero or until the board is resolved.

Repeat this many times and calculate the average number of solutions (including any zeros). This should give you a quick and fairly accurate approximation of the number of solutions with an approximation that improves the pace you are performing.

Hope this makes sense;)

Answer 4

I suggest you look into test_generators.py from a Python source for an alternative implementation of the N-Queens problem.

 Python 2.6.5 (release26-maint, Sep 12 2010, 21:32:47) [GCC 4.4.3] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> from test import test_generators as tg >>> n= tg.Queens(15) >>> s= n.solve() >>> next(s) [0, 2, 4, 1, 9, 11, 13, 3, 12, 8, 5, 14, 6, 10, 7] >>> next(s) [0, 2, 4, 6, 8, 13, 11, 1, 14, 7, 5, 3, 9, 12, 10] 

Answer 5

Below is my implementation of PYTHON. You can use PYPY for more speed.

Its speed helps with the O (1) time method to check whether the next queen is attacked by those already on the board.

Assuming the program is "nqueen.py", an example of its launch is "python nqueen.py 6", where 6 is the size of the 6x6 board.

 #!/bin/python # # TH @stackoverflow, 2016-01-20, "N Queens" with an O(1) time method to check whether the next queen is attacked # import sys board_size = int(sys.argv[1]) Attacked_H = { i:0 for i in range(0, board_size) } Attacked_DU = { i:0 for i in range(0, board_size*2) } Attacked_DD = { i:0 for i in range(-board_size, board_size) } def nqueen(B, N, row, col): if(row >= N): return 1 if(col >= N): print "board:\n" + str.join("\n", ["_|"*q + "Q|" + "_|"*(board_size - q - 1) for q in B]) return 0 B[col] = row if(0==(Attacked_H[row] + Attacked_DU[row+col] + Attacked_DD[row-col])): [Attacked_H[row], Attacked_DU[row+col], Attacked_DD[row-col]] = [ 1,1,1 ] nqueen(B, N, 0, col + 1) [Attacked_H[row], Attacked_DU[row+col], Attacked_DD[row-col]] = [ 0,0,0 ] nqueen(B, N, row + 1, col) nqueen(list(range(0, board_size)), board_size, 0, 0) 

Answer 6

We can solve n-queens with genetic algorithms. This is described here https://youtu.be/l6qll5OldHQ , in one of the lectures of the edX ColumbiaX course: CSMM.101x Artificial Intelligence (AI).

The objective function tries to optimize the number of non-attacking queens. The animation below shows an approximate solution in R with n = 20. More detailed information on how to solve n-queens with genetic algorithms can be found here: https://sandipanweb.wordpress.com/2017/03/09/solving -the-n-queen-puzzle-with-genetic-algorithm-in-r /? frame-nonce = 76cf9b156a .