Wilson's Algorithm: Complete Guide, Differences with EOQ and the Theorem

Informatec Digital » Engineering » Wilson's Algorithm: Complete Guide, Differences with EOQ and the Theorem

On the internet, the term "Wilson" is used for many different things, which is quite confusing: there's Wilson's algorithm for generating mazes, the Wilson Inventory Model (or EOQ), and Wilson's theorem in number theory. In this article, we clarify everything, starting with its original use in mazes and carefully distinguishing the other meanings, because they are not the same thing and do not apply to the same field.

If you've seen a demo or applet where a maze "grows" on its own, you've probably already encountered Wilson's algorithm. You may also have heard of the Wilson Model for calculating the economic order quantity or even the theorem that characterizes prime numbers using factorials. Here you'll find a complete explanation with examples, so you can identify each concept and use it correctly.

What is Wilson's algorithm for mazes?

Wilson's algorithm is a maze generation method based on loop-erased random walks. Its main advantage is that it produces a uniform random spanning tree across the grid: simply put, every possible maze appears with the same probability , without bias towards specific directions or patterns.

The key idea is that paths are added to the existing network, but when a random path intersects itself, the loop is "erased," and the route continues from the point where it became free. This detail prevents the process from favoring redundant long paths or creating cycles, maintaining the structure as a tree that connects all the cells. The result is a "fair" maze: no path or turn has a statistical advantage over another.

There are community-created projects and applets that visually and entertainingly demonstrate the algorithm in action. Among them, some of Cruz Godar's applets stand out, where you can choose the grid size and run it to see how the maze emerges step by step. Watching it run helps you understand why loop erasing levels the probabilities at each extension of the graph.

Building and solving mazes, while seemingly like games, are closely linked to search and optimization problems. Designing them requires a balance between clarity and intrigue, avoiding trivial solutions or impossible dead ends; exploring a finite space with vast combinations. Therefore, both on paper and in digital simulations, they serve as excellent exercises in logic, probability, and patience.

How it works (in practical terms)

Below is a high-level description of the algorithm, without code but with the essential mechanics to understand its behavior. Remember that the goal is to build a tree (without cycles) that connects all the cells, so that there is only one simple path between any two points.

• It starts with an empty grid: a cell is chosen at random and marked as part of the tree.
• Another cell is chosen at random, a step-by-step random walk is started, and if the path crosses itself, the loops are immediately removed (loop-erasing).
• When the walk reaches the already generated tree, the entire refined path (without loops) is “glued” to the tree.
• It repeats: we choose a new unconnected cell, walk with loop deletion and join the tree.
• In the end, all cells are connected and the maze is a uniform random spanning tree, so there are no directional or topological biases.

Compared to other methods (such as Aldous-Broder, Prim , or Kruskal adapted to mazes), Wilson stands out for the uniformity of its spanning tree sampling. Its computational cost is reasonable on typical grids and, above all, it guarantees that each solution is equiprobable , something highly valued in academic and simulation contexts.

Other meanings: Wilson Model or EOQ (inventories)

In logistics, the Wilson model (also called EOQ, Economic Order Quantity) has nothing to do with mazes. It is a classic method for determining the optimal order quantity to minimize total inventory costs. It was popularized in 1934 by R.H. Wilson, although the initial concept was proposed by Ford Whitman Harris in 1913.

Its purpose is to find the lot size Q that balances the cost of placing orders and the cost of holding inventory. Based on the annual demand (D), the cost per order (K), and the storage cost per unit per period (G), a quantity is obtained that, within the framework of its assumptions, reduces the total inventory cost.

The most common formula is expressed as Q = √(2·D·K/G). This figure gives the size of each batch; from there, the number of annual orders will be D/Q, and with this you can derive the order cycle. It is also important to set the reorder point (taking into account the lead time) and the safety stock to avoid stockouts, although the basic formula does not explicitly incorporate uncertainty.

Typical applications: It is used with raw materials or any type of merchandise for which purchase and storage costs can be reliably determined. In practice, by knowing D, K, and G with sufficient reliability, the company can size its batches and schedule its procurement with greater control.

Assumptions, advantages and limitations of the Wilson Model

The assumptions are critical to the validity of the result. The EOQ model assumes that demand is constant and known, that the unit price remains stable, that storage costs are known and depend on the stock level, that lead times are constant, and, furthermore, does not consider volume discounts.

• Stable, independent demand, without seasonality or sudden peaks.
• Purchase price fixed or practically unchanged during the period analyzed.
• Known storage costs per unit and period.
• No quantity discounts and immediate or constant replenishment.

Key advantages: It's simple to implement, widely used, and helps minimize ordering and inventory costs under its terms. Benefits include reduced overstocking, decreased stockout risk (when combined with a reorder point and safety stock), and improved clarity for purchasing planning. Many organizations value it because it provides a straightforward numerical basis for determining order quantities.

Disadvantages: It doesn't work well with seasonal or irregular demand, ignores volume discounts, and assumes immediate (or fixed) replenishment, which is unrealistic in many supply chains. Therefore, in environments like the Toyota group, the EOQ formula has been superseded by more robust systems such as Kanban or Just-in-Time, which better handle actual variability and continuous flow.

Practical examples of the EOQ (Wilson)

Example 1 (typical): A company with an annual production of 10.000 units acquires 1.000 kg of raw material. If each order costs €200 and the total annual storage cost is €2.000, applying the formula Q = √(2·D·K/G) with D=1.000, K=200, and G=2.000 yields Q ≈ 14,14. This suggests batches of 14 kg and approximately 71 orders per year. It is an illustrative exercise where, with modest numbers, we can see how batch size balances orders and stock.

Example 2: Sillas Grandes World SL distributes 6.000 chairs (D), each order costs €300 (K), and the annual storage cost per unit is €5 (G). Applying the equation, Q ≈ 848,52, meaning the company would place approximately 7,07 orders annually. With this lot size, the firm tends toward a more efficient inventory level , reducing storage costs without significantly increasing order preparation costs.

Beyond the formula itself, it's advisable to calculate the reorder point considering the lead time and maintain safety stock, because the pure model doesn't account for uncertainty. It also doesn't estimate the impact of volume discounts, which could sometimes offset inventory costs if larger batches are used.

Not to be confused with Wilson's theorem (number theory)

Wilson's theorem belongs to modular arithmetic and essentially states that an integer n > 1 is prime if and only if (n − 1)! ≡ −1 (mod n). The implication "if n is prime then (n − 1)! ≡ −1 (mod n)" is usually strictly called "Wilson's theorem," and the converse implication is also true. Historically, Edward Waring attributed the result to John Wilson (1770), although the first known proof was given by Lagrange (1771), and the formulation actually dates back to Alhazen in the 11th century.

Concrete example: for p = 11, by grouping each element with its multiplicative inverse in the set {1, 2, …, p − 1}, the total product is ≡ −1 (mod p). All factors cancel out pairwise as g·g^{-1} ≡ 1, except for 1 and p − 1, and therefore 10! ≡ −1 (mod 11) . This approach uses the fact that, with p prime, (Z/pZ)^× is a multiplicative group and each element (except 1 and p − 1) has a distinct inverse.

There are several proofs. One polynomial technique considers g(x) = (x − 1)(x − 2)···(x − (p − 1)) and f(x) = g(x) − (x^{p−1} − 1). Modulo p, f(x) would have at most p − 2 roots if it were not the zero polynomial, but all 1, 2, …, p − 1 make f(x) zero by Fermat's Little Theorem. Therefore, f(x) is identically 0 mod p; the constant term leads to (p − 1)! ≡ −1 (mod p).

It is not used as a practical test of primality because calculating (n − 1)! mod n for large n is costly, and faster tests exist (such as Miller–Rabin or deterministic tests for specific ranks). Even so, it can be used to deduce useful properties: for example, if p = 2n + 1 is prime, we obtain ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). And, as a partial corollary, −1 is a quadratic residue modulo p if p ≡ 1 (mod 4), since it can be written as the square of the product 1·2···2k when p = 4k + 1, which shows when −1 is squared in Z/pZ.

There is also a practical "inverse": for any composite number n > 5, n divides (n − 1)!. The case n = 4 is the classic exception (3! is not a multiple of 4). One way to see this is to count the powers of a prime q that divides n: in (n − 1)! there are enough multiples of q to cover the power that appears in n, except for the noted exception, which leads to the result except for n = 4.

Gauss generalized the theorem: the product of all units modulo n, ∏_{1≤a<n, (a,n)=1} a, is ≡ −1 (mod n) if n ∈ {4, p^k, 2p^k} with p odd prime, and ≡ 1 (mod n) in all other cases. From the perspective of finite abelian groups, the product of all their elements is the identity unless there exists exactly one element of order 2, in which case the product is that element of order 2.

Illustrative table of (n − 1)! mod n for n = 2…30

The following table shows specific values ​​for n between 2 and 30. For prime numbers, the remainder of (n − 1)! when divided by n is equal to n − 1 (which is ≡ −1 mod n). For composite numbers, the remainder is often 0. −1 mod n is also included for comparison. This data clearly illustrates how Wilson's theorem behaves in small cases and helps solidify the intuition.

n> 1	(n − 1)!	(n − 1)! mod n	−1 mod n
2	1	1	1
3	2	2	2
4	6	2	3
5	24	4	4
6	120	0	5
7	720	6	6
8	5040	0	7
9	40320	0	8
10	362880	0	9
11	3628800	10	10
12	39916800	0	11
13	479001600	12	12
14	6227020800	0	13
15	87178291200	0	14
16	1307674368000	0	15
17	20922789888000	16	16
18	355687428096000	0	17
19	6402373705728000	18	18
20	121645100408832000	0	19
21	2432902008176640000	0	20
22	51090942171709440000	0	21
23	1124000727777607680000	22	22
24	25852016738884976640000	0	23
25	620448401733239439360000	0	24
26	15511210043330985984000000	0	25
27	403291461126605635584000000	0	26
28	10888869450418352160768000000	0	27
29	304888344611713860501504000000	28	28
30	8841761993739701954543616000000	0	29

Applications, limits and recommendations

If you're looking to generate unbiased mazes, use Wilson's algorithm: its foundation in random walks with loop erasure ensures uniform trees. For inventory management, the Wilson model is useful when demand, prices, and costs are stable and precisely known; in volatile environments, methodologies like Kanban, Just-in-Time, or advanced planning software may be more suitable. And in mathematics, Wilson's theorem is a theoretical gem with interesting derivations (such as quadratic residuals), but it's not practical as a primality test for large numbers.

There's no single formula for calculating ordering and storage costs: each company must break down hours, processes, transportation, receiving, personnel, rent, energy, insurance, and financial costs. Many professionals estimate hours per operation and apply an hourly rate for monetization. This customization is key to ensuring the calculated order quantity (Q) is useful and, along with a good reorder point and safety stock, helps avoid stockouts or excess inventory.

It's worth remembering that the term "Wilson's algorithm" in searches usually points to the maze generator, while "Wilson model" or "EOQ" refers to inventories, and "Wilson's theorem" to number theory. Distinguishing them from the outset avoids confusion and allows you to make better use of each approach: unbiased mazes, optimal batches under realistic assumptions, and an elegant characterization of primes that, while not a practical primality proof, remains a valuable piece of the mathematical puzzle.