I love to play with puzzles. When I was in grade school I would spend hours at a time figuring out ways to solve from things like Tetris, Mindsweeper, Solitare, and Freecell. Later I was introduced to puzzles involving numbers like Sudoku and Nonograms.

These puzzles are often interesting in part because there is generally a very large way that things can be arranged, but only a few of these arrangements are correct. Generally a person solving a puzzle will figure out certain things that must be true or cannot be true, which helps in solving the puzzle and reducing the number of possible cases. Initially, though, we are often left with a situation where we have a new puzzle and our only method is to keep trying every possible solution until we start to notice a pattern (or reach a solution).

For example, consider a Sudoku puzzle. We are given a partially filled in grid and our job is to fill in the remaining cells with the rules that every row, column and marked subgrid must have the numbers 1 – 9 exactly once. One initial attempt at solving such a puzzle could be to attempt to permute the string 1, 2, 3, 4, 5, 6, 7, 8, 9 until we find a solution that fits the first row, then do the same with the second row, and so on and so forth.

One immediate question is how many ways are there to permute the numbers 1, …, 9? We can answer this by realizing that each permutation is a new string. So for each string that we construct, we have 9 choices for the first element in the string. Then once that element has been chosen, we are not allowed for that element to appear anywhere else. So there are only 8 possible choices for what can go in the second string. Continuing this process, we see that the number of possible permutations we can construct from the string 1, …, 9 is

__ 9 __ * __ 8 __ * __ 7 __ * __ 6 __ * __ 5 __ * __ 4 __ * __ 3 __ * __ 2 __ * __ 1 __ = 362880

This is a large number of possible strings to generate just to get one row of a Sudoku, so hopefully you’ll be able to notice the pattern before going through this whole set (because once you’ve generated the first row you still have to do the other 8 rows).

Nonetheless because there is often great value that can be gained by knowing how to permute through all possible solutions, I have written three functions that help with this process: Next_Permutation, Previous_Permutation, and Random_Permutation.

Before I give these algorithms, I want to highlight two notations on ordering string. A string (a_{1}, a_{2}, …, a_{n}) is said to be in lexicographical order (or alphabetical order) if for each i [in] 1, …, n-1, a_{i} [<=] a_{i+1}. Likewise, a string is said to be in reverse lexicographical order if for each i [in] 1, …, n-1, a_{i} [>=] a_{i+1}.

**Next Permutation**

If the given string is not in reverse lexicographic order, then there exists two elements j_{1} and j_{2} such that j_{1} [<] j_{2} and a_{j1} [<] a_{j2}.

1. The Next_Permutation algorithm first searches for the largest element *j _{1}* such that a

_{j1}[<] a

_{j1 + 1}. Since we said the string is not in reverse lexicographic order, this j

_{1}must exist.

2. Once this j

_{1}is found, we search for the smallest element a

_{j2}such that a

_{j2}[>] a

_{j1}. Again, since we know that this is true for j

_{1}+ 1, we know that such a j

_{2}must exist.

3. We swap the elements a

_{j1}and a

_{j}2.

4. The elements after j

_{1}+ 1 are then placed in lexicographic order (i.e. in order such that a

_{i}[>=] a

_{i+1}

If the given string is in reverse lexicographic order, then we simply reverse the string.

**Previous Permutation**

If the given string is not in lexicographic order, then there exists two elements j_{1} and j_{2} such that j_{1} [<] j_{2} and a_{j1} [>] a_{j2}.

1. The Previous_Permutation algorithm first searches for the largest element *j _{1}* such that a

_{j1}[>] a

_{j1 + 1}. Since we said the string is not in reverse lexicographic order, this j

_{1}must exist.

2. Once this j

_{1}is found, we search for the smallest element a

_{j2}such that a

_{j1}[>] a

_{j2}. Again, since we know that this is true for j

_{1}+ 1, we know that such a j

_{2}must exist.

3. We swap the elements a

_{j1}and a

_{j}2.

4. The elements after j

_{1}+ 1 are then placed in reverse lexicographic order (i.e. in order such that a

_{i}[<=] a

_{i+1}

If the given string is in lexicographic order, then we simply reverse the string.

**Random Permutation**

This generates a random string permutation.

This script can be seen here, set to work on permutations of colors.

- Nim Games (0.379)
- Triangle Sum Puzzle (0.379)
- Examples Page (0.287)
- Learn Math Through Set Relations (0.255)
- Sudoku Program Updates (0.228)