nqueens.py

# Look ma, no modules!

# bottlenecks around 12, when the problem size starts to mushroom
board_size = 11

solutions = []
queens = []
occupied = board_size*[0,]



def explore(depth):
    # base case
    if(depth==board_size):
        # stringify/serialize the solution
        solutions.append("%s"%(queens))
        return

    else:
        attacked = 2*board_size*[0,]
        for i in range(0,len(queens)):
            ix1 = queens[i] + depth - i
            attacked[ix1] = 1

            ix2 = queens[i] - depth + i
            attacked[ix2] = 1

        for row in range(0,board_size):
            if(occupied[row] or attacked[row]):
                continue

            # make a choice
            queens.append(row)
            occupied[row] = 1

            # explore the consequences
            explore(depth+1)

            # unmake the choice
            queens.pop()
            occupied[row] = 0



explore(0)
print "Found %d solutions"%(len(solutions))
#print solutions

prof_python_cprof.sh

#!/bin/sh
#
# Profile the N queens problem using cProfile

export RIGHTNOW="`date +"%Y%m%d_%H%M%S"`"
export OUT="outfile_prof_nqueens_python_${RIGHTNOW}.out"

for N in 8 9 10 11
do

    echo "**************************************" >> ${OUT}
    echo "Profiling $N queens problem with Python..." >> ${OUT}

    # Update N
    /usr/local/bin/sed -i "s/board_size = [0-9]\{1,\}/board_size = ${N}/g" nqueens.py

    rm -f *.pyc

    echo "Running..."
    python pycprof_nqueens.py >> ${OUT}
    echo "Done."

done

prof_python_lineprof.sh

#!/bin/sh
#
# Profile the N queens problem using cProfile

export RIGHTNOW="`date +"%Y%m%d_%H%M%S"`"
export OUT="outfile_prof_nqueens_python_${RIGHTNOW}.out"

# Add function decorator
/usr/local/bin/sed -i "s/def explore/@profile\ndef explore/g" nqueens.py

for N in 8 9 10 11
do

    echo "**************************************" >> ${OUT}
    echo "Profiling $N queens problem with Python..." >> ${OUT}

    # Update N
    /usr/local/bin/sed -i "s/board_size = [0-9]\{1,\}/board_size = ${N}/g" nqueens.py

    rm -f *.pyc

    echo "Running program via kernprof..."

    # runs the program
    kernprof -l nqueens.py >> ${OUT}

    # results are in nqueens.py.lprof
    python -m line_profiler nqueens.py.lprof >> ${OUT}

    echo "Done."

done

# Remove function decorator
/usr/local/bin/sed -i "s/@profile//g" nqueens.py

pycprof_nqueens.py

print "*******************************"
print "cProfile:"
print "*******************************"

import pstats, StringIO
import cProfile
pr = cProfile.Profile()
pr.enable()
import nqueens
pr.disable()

# from https://docs.python.org/2/library/profile.html
s = StringIO.StringIO()
sortby = 'time'
ps = pstats.Stats(pr, stream=s).sort_stats(sortby)
ps.print_stats()
print s.getvalue()

time_nqueens.py

import time
start = time.time()
import nqueens
finish = time.time()
duration = finish - start
print "Duration: %0.3f s"%(duration)

time_python.sh

#!/bin/sh

export RIGHTNOW="`date +"%Y%m%d_%H%M%S"`"
export OUT="timeout_nqueens_python_${RIGHTNOW}.out"
touch ${OUT}
cat /dev/null > ${OUT}

for N in 8 9 10 11 #12 13 14 15
do
    echo "**************************************" >> ${OUT}
    echo "Running $N queens problem with Python..." >> ${OUT}

    # Update N
    /usr/local/bin/sed -i "s/board_size = [0-9]\{1,\}/board_size = ${N}/g" nqueens.py

    rm -f *.pyc

    # Semicolon is important here
    echo "Running..."
    { time python time_nqueens.py >> ${OUT}; } 2>> ${OUT}
    echo "Done."

    echo "" >> ${OUT}

done