12
\$\begingroup\$

I want to increase the efficiency and reduce the time complexity for the n-queen problem in n*n matrix chess. I am able to run only still (11*11) in normal time otherwise for the big number it is taking much more time. How can I improve performance?

import time

start_time = time.time()

def queensproblem(rows, columns):
    solutions = [[]]
    for row in range(rows):
        solutions = add_one_queen(row, columns, solutions)
    return solutions

def add_one_queen(new_row, columns, prev_solutions):
    return [solution + [new_column]
            for solution in prev_solutions
            for new_column in range(columns)
            if no_conflict(new_row, new_column, solution)]

def no_conflict(new_row, new_column, solution):
    return all(solution[row]       != new_column           and
               solution[row] + row != new_column + new_row and
               solution[row] - row != new_column - new_row
               for row in range(new_row))

count = 0
r = input("Enter number of ROWS for Chess/Matrix: ")
c = input("Enter number of COLUMNS for Chess/Matrix: ")

for solution in queensproblem(int(r), int(c)):
    count += 1
    print(solution)

print("\n Total number of solution is: ", count)

print("--- Time: %s seconds ---" % (time.time() - start_time))

Output

For a 4x4 matrix

Enter number of ROWS for Chess/Matrix: 4
Enter number of COLUMNS for Chess/Matrix: 4
[1, 3, 0, 2]
[2, 0, 3, 1]

 Total number of solution is:  2
--- Time: 2.3161020278930664 seconds ---

For a 12x12 matrix

Enter number of ROWS for Chess/Matrix: 12
Enter number of COLUMNS for Chess/Matrix: 12
[0, 2, 4, 7, 9, 11, 5, 10, 1, 6, 8, 3]
[0, 2, 4, 9, 7, 10, 1, 11, 5, 8, 6, 3]
<more output>

 Total number of solution is:  14200
--- Time: 29.522358894348145 seconds ---
\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to Code Review! Good job on your first question. \$\endgroup\$ – Phrancis Mar 12 '16 at 18:13
  • \$\begingroup\$ I just noticed that you measure the inputs as well. Just by excluding them, the "run time" reduced from 2.52 seconds to 0.00024 on my machine! \$\endgroup\$ – Nobody Mar 16 '16 at 21:33
3
\$\begingroup\$

Expanding on the answer of vnp I found this little tweak:

def no_conflict(new_row, new_col, solution):
    if new_col in solution:
        return False
    for row, col in enumerate(solution):
        if row + col == new_row + new_col or row - col == new_row - new_col:
            return False
    return True

Using new_col in solution I was able to solve the 12*12 board in 6.1 seconds.

By the way, I profiled the script, and the speed is completely dependent on the no_conflict function. In the version using this no_conflict the profiling resulted in:

1.972 seconds in add_one_queen

4.862 seconds in no_conflict

and basically 0 everywhere else.

(By the way, if anyone is wondering why these add up to more than 6.1; it's because the profiling slows down the execution, so I tested it again using time.time())

Edit:

You should also be able to double your speed by using the symmetry of the Problem. For example, you need only consider the Solutions where the queen in the first row is in one of the upper half columns, since you can construct the rest by mirroring.

(e.g. calling [[8-i for i in solution] for solution in solutions])

Edit2:

Also I think this is the best you can do with your approach. If you want to solve even bigger n-queens you will have to do it differently.

(Since the world record is calculating 23 queens, I'd say this is pretty good)

\$\endgroup\$
  • \$\begingroup\$ I think taking advantage of the symmetry will be the biggest gain. I optimized further by discarding the no_conflict function altogether and use the set of yet non threatened columns in the new row. Additionally, by working depth first instead of breadth first the cache locality is improved. These two optimizations shaved of a second each for the 12^2 case. \$\endgroup\$ – Nobody Mar 16 '16 at 22:43
  • \$\begingroup\$ I think the World Record is now 27 (nqueens.de/sub/WorldRecord.en.html) :) \$\endgroup\$ – alecxe Apr 5 '17 at 16:16
4
\$\begingroup\$

To my surprise, rewriting no_conflict as

def no_conflict(new_row, new_col, solution):
    for row, col in enumerate(solution):
        if col == new_col or row + col == new_row + new_col or row - col == new_row - new_col:       
            return False
    return True

resulted in a factor of 2 speedup. I have no explanation.

Other tweaks I tried gave very marginal performance changes.

As for the general review, the code is quite straightforward and readable. The only recommendation is to compute start_time after taking inputs. As written, you are timing not only the algorithm but also user's typing skills.

\$\endgroup\$
  • 1
    \$\begingroup\$ One reason for the speed up might be that indexing into the list is avoided. That, together with the fact that this is probably the hottest function in the code, might account well for doubled speed. \$\endgroup\$ – Nobody Mar 16 '16 at 15:39
  • \$\begingroup\$ You can do even faster by adding if new_col in solution: return False before the for loop, and removing col==new_col \$\endgroup\$ – JeD Mar 16 '16 at 19:06
3
\$\begingroup\$

This might be considered as "cheating" (since this does not change your code), but nobody mentioned using Pypy. You are using pure python and your program runs perfectly with Pypy.

For a 10x10 board (as suggested by @vnp, I moved the timing so keys pressing are not timed):

pypy nqueens.py
('\n Total number of solution is: ', 724)
--- Time: 0.224999904633 seconds ---

python nqueens.py
('\n Total number of solution is: ', 724)
--- Time: 1.37299990654 seconds ---
\$\endgroup\$
3
\$\begingroup\$

While this does not pertain to your review goals, let me note that you should make your measurements as tightly as possible.

Your code actually measures the printing of the solutions which can add substantial overhead. Even worse: you measure the time it takes to read the input from the user, thereby measuring the user's response time. Instead you should do something like

start_time = time.time()
solutions = queensproblem(int(r), int(c))
duration = time.time() - start_time)
for solution in solutions:
    count += 1
    print(solution)

print("\n Total number of solution is: ", count)

print("--- Time: %s seconds ---" % (duration))

Finally, measuring the time consumption reliable would require some repetitions. Python actually has the timeit module that can help you in timing code.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.