Source-linked AI summary
Stochastic Optimization Approaches for Solving Sudoku
Meir Perez, Tshilidzi Marwala
TL;DR
The paper investigates stochastic optimization for solving Sudoku, where harder puzzles can make guess-dependent backtracking inefficient. It implements CGA, RPSO, QSA, and HGASA, finding that CGA, QSA, and HGASA solve the puzzle while HGASA is fastest and RPSO does not solve it.
Problem
Backtracking becomes less efficient as harder Sudoku puzzles require more guesses, motivating stochastic search methods for difficult solution spaces.
Method
The paper implements and compares Cultural Genetic Algorithm, Repulsive Particle Swarm Optimization, Quantum Simulated Annealing, and Hybrid Genetic Algorithm with Simulated Annealing.
Results
HGASA solved the puzzle in 1.447 seconds after 435 iterations, while CGA took 28 seconds and QSA 65 seconds; RPSO did not find a solution.
Takeaways & Limitations
HGASA was deemed the most efficient algorithm because it combines GA’s parallel searching with SA’s flexibility.
Takeaways & Limitations
RPSO and the first CGA approach could not solve the puzzle because their search operations were not naturally adapted to generating better candidate puzzles.
Abstract
from arXiv · showhide
In this paper the Sudoku problem is solved using stochastic search techniques and these are: Cultural Genetic Algorithm (CGA), Repulsive Particle Swarm Optimization (RPSO), Quantum Simulated Annealing (QSA) and the Hybrid method that combines Genetic Algorithm with Simulated Annealing (HGASA). The results obtained show that the CGA, QSA and HGASA are able to solve the Sudoku puzzle with CGA finding a solution in 28 seconds, while QSA finding a solution in 65 seconds and HGASA in 1.447 seconds. This is mainly because HGASA combines the parallel searching of GA with the flexibility of SA. The RPSO was found to be unable to solve the puzzle.
1. Introduction
Sudoku is a constrained 9x9 combinatorial puzzle whose difficulty can make backtracking inefficient. The paper evaluates four stochastic optimization techniques as alternatives for searching difficult solution spaces.
- A Sudoku grid has 81 cells arranged in nine 3x3 sub-grids, with each row, column, and sub-grid containing integers one through nine exactly once.
- 47 cells in the example puzzle are pre-defined or empty?
- Backtracking becomes less efficient as the number of guesses required to solve harder puzzles increases.
- Stochastic optimization searches the solution space even after local optima, supporting detection of a global optimum under Sudoku’s constraints.
- The paper implements and compares Cultural Genetic Algorithm, Repulsive Particle Swarm Optimization, Quantum Simulated Annealing, and Hybrid Genetic Algorithm with Simulated Annealing.
- All four techniques require solution-space initialization and a fitness function to enforce objectives and constraints.
2. Solution Space Representation
The paper considers three representations of Sudoku solution space and retains the two that permit interaction between candidate solutions or preserve a valid sub-grid constraint.
- Representing each of the 47 empty cells as a separate individual or particle creates 47 population groups and prevents interaction between them.
- Representing the 47 empty-cell values as one 47-dimensional individual creates a single population and reduces computational demand.
- Representing each individual as a fully filled puzzle preserves the constraint that every 3x3 grid contains numbers 1 to 9 exactly once.
- Only the second and third representations are used: CGA uses both, RPSO uses the second, and QSA and HGASA use the third.
3. Fitness Function
The paper rejects arithmetic-only fitness measures because they do not guarantee non-repetition, and instead scores candidate solutions by repeated or missing integers across Sudoku regions.
- A possible arithmetic fitness function uses row, column, and grid sums of 45 and products of 362880 to assess constraint satisfaction.
- A row containing nine 5s still sums to 45, so arithmetic checks do not guarantee that integers are non-repeated.
- The implemented fitness function assigns a value based on repeated or absent integers in candidate rows, columns, and, for one representation, grids.
4. Cultural Genetic Algorithm
CGA combines genetic evolution with a belief space and influence function that constrain Sudoku candidates. Its implementation uses standard population operations while encoding Sudoku-specific value and spatial restrictions.
- CGA is an evolutionary optimization technique in which individuals are influenced genetically and culturally.
- Genetic Algorithm Background: A genetic algorithm evolves a population of candidate individuals through initialization, selection, reproduction, and termination.
- Genetic Algorithm Background: Selection favors fitter individuals for mating but retains less-fit candidates because elitist selection may cause convergence to a local minimum.
- Genetic Algorithm Background: Reproduction combines parent genes through crossover and mutation, while mutation alters gene sequences to support convergence away from local minima.
- Cultural Genetic Algorithm Background: CGA adds a belief space containing normative, domain-specific, temporal, and spatial information, plus an influence function linking the population to those beliefs.
- CGA Applied to Sudoku: For Sudoku, CGA restricts candidate values and representations so generated individuals conform to puzzle-specific constraints, reducing the candidate space.
- CGA Applied to Sudoku: The Sudoku implementation uses crossover and mutation, with influence functions enforcing integer values and preventing repetitions or changes to fixed cells.
5. Repulsive Particle Swarm Optimization
RPSO adapts particle swarm optimization by repelling particles from one another to avoid local optima, then applies this search framework to Sudoku’s 47 unfixed cells.
- PSO background: Classical PSO updates each particle using its current position and velocity, personal best position, group best position, inertia, constants, and random values.The velocity and position updates are iterated until the global optimum is found or an iteration limit is reached.
- RPSO background: RPSO is a PSO variant designed for complex search spaces with many local minima.Its repulsive particle interactions are intended to prevent particles from gravitating toward local optima.
- RPSO background: RPSO adds repulsion through a negative c2 term linked to another randomly chosen particle’s best position.The method also uses another particle’s velocity and random coefficients when updating velocity.
- RPSO applied to Sudoku: For Sudoku, each RPSO particle represents the 47 non-fixed cells, with 50 randomly initialized individuals containing values from 1 to 9.Initial velocities are set to zero, and a randomly selected particle supplies the comparison position for the first velocity update.
- RPSO applied to Sudoku: Subsequent iterations update particle velocities and positions while tracking, but not using, the global best position for solution detection.The velocity update instead uses a randomly chosen particle’s velocity and best position.
6. Quantum Simulated Annealing
QSA extends simulated annealing with quantum tunnelling so that search can move across high-energy regions while progressively narrowing its neighbourhood in Sudoku’s discrete search space.
- Simulated annealing background: Simulated annealing evaluates neighbouring states by energy and sometimes accepts higher-energy moves according to an acceptance probability.A high initial temperature promotes exploration, while cooling encourages convergence toward lower-energy states.
- Quantum simulated annealing: QSA uses tunnelling through high-energy areas to move between states in search of lower-energy regions.Tunnelling field strength replaces temperature as the control over neighbourhood radius, while SA temperature controls transition probability.
- QSA applied to Sudoku: QSA is applied to Sudoku with a randomly filled starting state in which every 3x3 grid contains the integers 1 to 9 exactly once.Because QSA is not population based, it uses a single-state representation and evaluates repetitions in rows and columns.
- QSA applied to Sudoku: The neighbourhood function selects a grid and swaps two unfixed cells within it.This preserves the 3x3-grid constraint while changing the candidate state.
- QSA applied to Sudoku: 20 reductions multiply tunnelling strength by 0.8, while each Markov Chain runs for 2209 iterations.The 2209-iteration length is based on the square of the puzzle’s 47 unfilled cells.
- QSA applied to Sudoku: As tunnelling strength decreases, the neighbouring state is generated with fewer random swaps, ending with one swap in the final Markov Chain.Early chains therefore explore more varied neighbouring states than later chains.
7. Hybrid Genetic Algorithm and Simulated Annealing
HGASA combines GA’s population-based exploration with SA’s local flexibility, using GA first and then refining its best individual through a modified annealing process.
- HGASA approach: HGASA combines the parallel search capability of GA with SA’s flexibility to continue searching after a local minimum is reached.GA explores with multiple individuals, while SA can seek a better optimum from a locally favorable state.
- HGASA approach: The method initially runs GA to explore the search space and switches to random walks on the best individual when GA stops improving.The transition occurs after a low fitness is achieved and no better individuals are found for a set number of generations.
- HGASA implementation: HGASA initializes a population of ten puzzles using a representation in which each 3x3 grid contains the integers 1 to 9 exactly once.Its reproduction function uses mutation that swaps two unfixed cells in a randomly selected grid.
- HGASA implementation: The SA cycle begins when an individual with fitness 2 is found, using a moderated Monte Carlo chain without a temperature schedule.This follows the GA’s production of an individual with low energy and accepts states with energy lower than or equal to the current state.
- HGASA implementation: GA and SA use the same fitness and neighbourhood functions, with the SA neighbourhood applying one mutation per iteration.This aligns GA reproduction with the subsequent local search.
8. Results and Technique Comparison
The tested stochastic methods differed substantially: the second CGA approach, QSA, and HGASA solved the puzzle, while RPSO and the first CGA approach did not. HGASA was fastest, although CGA and HGASA showed stochastic variation across runs.
- The second CGA approach, QSA, and HGASA found the correct Sudoku solution, whereas RPSO and the first CGA approach did not.
- CGA Results: 28 seconds was the best CGA time, after 208 generations.
- CGA Results: CGA solved all 20 runs, but solution time ranged from 28 seconds to 10 minutes.Convergence depended on the initial population and random mutations.
- QSA Results: 65 seconds was the QSA runtime, with the solution found after 42,700 iterations; QSA succeeded in 15 of 20 runs.Its long convergence time was primarily attributed to initial random swaps.
- HGASA Results: 1.447 seconds was the best HGASA time, after 435 iterations, combining a GA cycle reaching fitness 2 with a 267-iteration Monte Carlo chain.HGASA's Monte Carlo phase operated on one individual and was less computationally demanding than a full GA generation.
- HGASA Results: HGASA solved all 20 runs, with solution times ranging from 1.447 seconds to 3 minutes.The authors deemed HGASA the optimal algorithm for this Sudoku problem and suggested applying the Monte Carlo chain to multiple higher-fitness individuals.
9. Conclusion
The paper shows that stochastic search can solve the Sudoku puzzle, with CGA, QSA, and HGASA succeeding while one CGA approach and RPSO do not. HGASA was the most efficient, solving the puzzle in 1.447 seconds by combining genetic-algorithm parallel search with simulated-annealing flexibility.
- Four stochastic optimization algorithms—CGA, RPSO, QSA, and HGASA—were applied to the Sudoku problem and discussed in the paper.The paper also discusses solution-space representation and a fitness function common to all algorithms.
- Only one CGA approach, QSA, and HGASA found the puzzle solution.RPSO and the other CGA approach did not find a solution in the reported experiment.
- 28 seconds: CGA found the solution after 208 generations, while QSA required 65 seconds and 42,700 iterations.
- 1.447 seconds: HGASA solved the puzzle after 435 iterations, making it the most efficient algorithm tested.
- HGASA combines the parallel searching power of a genetic algorithm with the flexibility of simulated annealing.The paper suggests improving HGASA by applying the simulated-annealing cycle to more than one individual.