2022-06-28, 15:30–15:50, Hall 3
A short walk through the challenge of finding the fastest NumPy algorithm/way for solving the 8 Queens puzzle. During this walkthrough I will explain the different solutions, the NumPy APIs I’ve been using and their underlying implementation.
NumPy is a powerful library. Understanding its underlying implementation and its APIs is key for achieving fast code.
The 8 Queens puzzle requires placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. When solving the puzzle, it is possible to use shortcuts that reduce computational requirements. For example, by applying a simple rule that constrains each queen to a single column (or row). Generating permutations further reduces the possibilities to just 40,320 (that is, 8!), which then can be checked only for diagonal attacks.
The talk will explore 5 different ways to use NumPy to sum all the diagonals in a 2 dimensional array — from brute force, i.e. looping over all diagonals, to more advanced APIs (e.g. as_strides.)
During this walkthrough I will explain the different solutions, the NumPy APIs I’ve been using, their underlying implementation, and a few basic NumPy principles like array data structure, broadcasting, fancy indexing and more.
The optimal solution might surprise you.
We will learn that:
- loops in NumPy are a performance enemy.
- There are (almost) always multiple ways to solve a problem in NumPy — you may just need to expand your box of tricks.