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, people use the term "Wilson" for very different purposes, and this is quite confusing: there's the Wilson algorithm for generating mazes, the Wilson Model (or EOQ) for inventories, and Wilson's theorem in number theory. In this article, we clarify everything, starting with the original use in mazes and carefully distinguishing the other meanings, because They are not the same nor do they apply to the same area.

If you've seen a demo or applet where a maze "grows" by itself, you've probably already encountered Wilson's algorithm. You've also 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 you can identify each concept and use it properly.

What is Wilson's algorithm for mazes?

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

The key idea is that paths are added to the already constructed set, but when a random walk intersects itself, the loop is "deleted" and the route continues from where it left off. This detail prevents the process from creating long, redundant paths or loops, maintaining the structure as a tree connecting all the cells. The result is a "fair" maze: no corridor or turn has a statistical advantage over another.

There are community-created projects and applets that show the algorithm in action in a visual and highly entertaining way. Among them, some applets by Cruz Godar stand out, where you can choose the grid size and set it to work to see how the maze emerges step by step. Watching it run helps you understand why. Loop erasure evens the odds in each extension of the graph.

Building and solving mazes are tasks that, although they may seem like games, are closely linked to search and optimization problems. Designing them requires a balance between clarity and interest, avoiding trivial solutions or dead ends; explore a finite space with enormous combinations. Therefore, both on paper and in digital simulations, they work as Great 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, such that there is only one simple path between any pair of 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, prime or Kruskal adapted to labyrinths), Wilson stands out for the uniformity of the sampling of the generating tree. Its computational cost is reasonable on typical grids and, above all, ensures that each solution is equally probable, something highly appreciated in academic and simulation contexts.

Other meanings: Wilson Model or EOQ (inventories)

In logistics, the “Wilson Model” (also called EOQ, Economic Order Quantity; or CEP, Economic Order Quantity) has nothing to do with mazes. It is a classic method for determining the optimal order quantity with the goal of minimizing total inventory costs. It was popularized in 1934 by R.H. Wilson, although The first proposal was by Ford Whitman Harris in 1913.

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

The most common formula is Q = √(2 D K/G). This gives the batch size; from there, the number of annual orders will be D/Q, and from this you can derive the time cadence. 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 incorporate uncertainty explicitly.

Typical applications: used with raw materials or any type of merchandise for which purchasing and storage costs can be determined reliably. In practice, if D, K, and G are known with sufficient reliability, The company can size its batches and schedule their supply with greater control.

Assumptions, advantages and limitations of the Wilson Model

Assumptions are critical to the validity of the results. 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 inventory level, that supply times are constant, and, furthermore, does not contemplate 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.

Main advantages: It is simple to implement, widely used, and helps minimize ordering and inventory costs under your conditions. Its benefits include reduced overstocking, reduced risk of stockouts (if accompanied by a reorder point and safety stock), and clarity in purchasing planning. Many organizations value it because offers a simple numerical basis for deciding how much to order.

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 displaced by more robust systems like Kanban or Just in Time, which They handle real variability better and the continuous flow.

Practical examples of the EOQ (Wilson)

Example 1 (typical): A company with an annual production of 10.000 units purchases 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, G = 2.000 gives Q ≈ 14,14. This suggests batches of 14 kg and approximately 71 orders per year. This is an illustrative exercise where, with modest numbers, we can see How lot size balances orders and stock.

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

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

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

Wilson's theorem belongs to the modular arithmetic and essentially says 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 often 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 in fact, The formulation dates back to Alhacen in the 11th century.

Concrete example: for p = 11, when grouping each element with its multiplicative inverse in the set {1, 2, …, p − 1}, the total product becomes ≡ −1 (mod p). All factors cancel out evenly as g g^{-1} ≡ 1, except 1 and p − 1, and so 10! ≡ −1 (mod 11)This approach uses that, with p prime, (Z/pZ)^× is a multiplicative group and every 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). Modulus p, f(x) would have at most p − 2 roots if it were not the null polynomial, but all 1, 2, …, p − 1 vanish f(x) by Fermat's little theorem. Hence f(x) is identically 0 mod p and the independent term leads to (p − 1)! ≡ −1 (mod p).

It is not used as a practical primality test, because computing (n − 1)! mod n for large n is expensive and faster tests exist (such as Miller–Rabin or deterministic tests for specific ranges). Even so, it is useful to deduce useful properties: for example, if p = 2n + 1 is prime, then we have ∏_{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 square in Z/pZ.

There is also a practical “inverse”: for any composite n > 5, it is true that 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 divide n: in (n − 1)! there are enough multiples of q to cover the power that appears in n, except for the exception indicated, which leads to the result except for n = 4.

Gauss generalized the theorem: the product of all units modulo n, ∏_{1≤a It is that element of order 2.

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

In the following table you can see specific values ​​for n between 2 and 30. For n that is prime, the remainder of (n − 1)! when divided by n is equal to n − 1 (which is ≡ −1 mod n). In composites, the remainder is often 0. −1 mod n is also included for comparison. This data illustrates very well how Wilson's theorem behaves in small cases and helps to fix 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 basis in random walks with loop deletion ensures uniform trees. For inventories, the Wilson Model is useful when demand, prices, and costs are stable and precisely known; in volatile environments, methodologies such as Kanban, JIT, or advanced planning software may be more appropriate. And in mathematics, Wilson's theorem is a theoretical gem with interesting derivations (such as quadratic residues), but It is not practical as a primality test for large numbers.

There's no "one-size-fits-all" 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 to monetize. This customization is key to making the calculated Q useful and, along with a good reorder point and safety stock, avoid stockouts or excess inventory.

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