Solving the n-queen puzzle
Solution 1
The backtracking algorithm to the N-Queens problem is a factorial algorithm in the worst case. So for N=8, 8! number of solutions are checked in the worst case, N=9 makes it 9!, etc. As can be seen, 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 correct solutions, there's really not much that can be done about speeding up the program. You've already done a good job in 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.
Solution 2
Just saw this question. I'd like to contribute 2 solutions.
Feedback is appreciated. Cheers
Solution 3
I would suggest you peek at the test_generators.py
from the 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]
Solution 4
The number of solutions can be estimated using Donald Knuth's randomised estimation method.
Starting from no queens placed the number of allowed positions for the next row is n. Randomly pick one of the positions and calculate the number of allowed positions (p) for the next row and multiple this by n and store it as the total number of solutions (total = n * p) , then randomly choose one of the allowed positions.
For this row calculate the number of allowed positions (p) for the next row and mutiple the total number of solutions by this (total *= p). Repeat this until either the board cannot be solved, in which case the number of solutions equals zero, or until the board is solved.
Repeat this many times and calculate the average number of solutions (including any zeros). This should give you a quick and pretty accurate approximation of the number of solutions with the approximation improving the more runs you do.
I hope this makes sense ;)
Admin
Updated on August 18, 2022Comments
-
Admin over 1 year
I have just solved the nqueen 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 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()