Backtracking in Action: Sudoku and N-Queens

Having already learned the Core Framework of Backtracking Algorithm, this article will explore two classic algorithm problems: Sudoku and the N-Queens problem.

These problems have been selected because their solution approaches are very similar, and they are interesting applications of the backtracking algorithm in real life.

Game Introduction

Sudoku Game

Most people have probably played Sudoku, which involves a 9x9 grid with some numbers already filled in. The goal is to fill in the remaining empty squares with numbers from 1 to 9, ensuring that each row, column, and 3x3 subgrid contains no repeating numbers.

Here is an example of a Sudoku puzzle (source: Wikipedia):

When I was young, I tried playing Sudoku but struggled with the more difficult puzzles. It was only later that I realized there are techniques for solving Sudoku. Some professional Sudoku software can teach these techniques, but I found them too complicated and lost interest.

Now that I have learned backtracking algorithms, no Sudoku problem is too challenging for me. As long as there are rules, a brute-force approach can always find a solution that meets the criteria, right?

Below is an example of solving Sudoku using a backtracking algorithm:

I will explain the solution to this problem in detail later.

N-Queens Problem

In chess, a queen can attack any piece in the same row, column, or diagonal. The N-Queens problem involves placing N queens on an N×N chessboard so that no two queens can attack each other.

In other words, you need to place N queens on an N×N chessboard such that there is only one queen per row, column, and diagonal.

For example, here is a solution to the 8-Queens problem (source: Wikipedia):

As you can see, for any given queen, there are no other queens in its row, column, or diagonals (top-left, top-right, bottom-left, bottom-right), making this a valid solution.

Before discussing the problem above, I need to first explain a simpler backtracking algorithm problem. By using this problem as a foundation, it will be easier to understand the solutions for Sudoku and the N-Queens problem.

All Possibilities of n-bit Binary Numbers

Let me present you with a simple problem. Please implement a function that does the following:

List<String> generateBinaryNumber(int n);

vector<string> generateBinaryNumber(int n);

def generateBinaryNumber(n: int) -> List[str]:

func generateBinaryNumber(n int) []string {}

var generateBinaryNumber = function(n) {};

The input of the function is a positive integer n. Please return all binary numbers (composed of 0s and 1s) of length n. You may return the answers in any order.

For example, if n = 3, you need to return the following $2^3=8$ different binary numbers as strings:

000
001
010
011
100
101
110
111

This problem can be considered a simplified version of the Sudoku game and the N-Queens problem:

This problem essentially requires you to perform a brute-force search on every position of a one-dimensional array of length n, where each position can be filled with 0 or 1.

The Sudoku game involves performing a brute-force search on every position of a 9x9 two-dimensional array, where each position can be a number from 1 to 9. Additionally, numbers cannot repeat in the same row, column, or within any 3x3 subgrid.

The N-Queens problem requires you to perform a brute-force search on every position of an N x N two-dimensional array, where each position can either be empty or have a queen (equivalent to 0 or 1). Moreover, no two queens can be placed in the same row, column, or diagonal.

Therefore, once you understand the brute-force process for this simplified problem, other problems become manageable. They merely involve additional rules.