Table of Contents:

• A Gentle Introduction to Recursion

• Recursive Backtracking

• Paring Down the Decision Tree

• The Pseudocode

• Accounting for Diagonal Attacks

• Why the N Queens Problem?

A Gentle Introduction to Recursion

Recursion, particularly recursive backtracking, is far and away the most challenging topic I cover when I teach the CSE 143 (Java Programming II) course at South Seattle College. Teaching the concept of recursion, on its own, is challenging: the concept is a hard one to encounter in everyday life, making it unfamiliar, and that creates a lot of friction when students try to understand how to apply recursion.

The …

Table of Contents

• Background
• N Queens Revisited
• Perl Solution
• Python Solution
• Python vs. Perl: Walltime vs. Number of Queens
• Perl Profiling and Results
• Python Profiling
• Python Profiling Results
• Comparing Python to Perl
• Python vs. Perl: Walltime vs. Number of Solutions Tested
• The Winner: Perl for Small Problems, Python for Big Ones
• Sources

Background

Revisiting the N queens problem, this time implementing the solution in Python.

Verb-oriented solution, functional, and based on Perl solution

More fair comparison - both are interpreted languages, not compiled languages

Compare Python and Perl, ease of implementation, speed, flexibility

N Queens Problem

As a recap from the …

Table of Contents

• Background: Huh?
• N Queens Problem
• N Queens Solution
  • Perl Solution
  • Java Solution
• Head to Head: Walltime vs. Number of Queens
• Perl Profiling
• Perl Profiling Results
• Java Profiling
• Java Profiling Results
• Head to Head: Walltime vs. Number of Solutions Tested
• Apples and Oranges
• Sources

Summary

In this post, we describe an implementation of the N Queens Problem, which is a puzzle related to optimization, combinatorics, and recursive backtracking. The puzzle asks: how many configurations are there for placing 8 queens on a chessboard such that no queen can attack any othr queen?

This problem was implemented in Perl …