—Sudoku puzzles are easily solved using backtracking algorithms. Yet, literature is scattered with various shy and often opaque attempts at using evolutionary algorithms and hybridizing them with known strategies of solving the puzzle. Evolutionary methods are serendipitous in nature, and this paper demonstrates the behaviour of such serendipity under constraints, using visuals that depict the sheer magnitude of the problem space and the nature in which intertwined constraints affect the scope for locating a solution, with the hope that it could inspire a new way of looking at the problem. We propose a method of visualizing the sudoku ﬁtness landscape, the vastness and complexity of even partially brute forcing the puzzle, and a unique method of mutating puzzle states using circular swaps. These insights could potentially serve as a link to comprehend the problem space when designing solutions for vast, multidimensional problems. Additionally, ﬁnding the optimal solution for some puzzles was notably harder, compared to puzzles in the same category of given clues. A short investigation was conducted into this phenomenon, which revealed hints that compel us to propose that the direction of research that should be taken, is in discovering more about puzzle states and deﬁnitive mathematical properties of the puzzle, rather than merely designing brute-force, stochastic or hybrid approaches of ﬁnding solutions. Index Terms —Combinatorics, Constraint Satisfaction Prob- lems, Sudoku I. I NTRODUCTION Sudoku is a number puzzle, originally consisting of a square grid of 99cells, where each cluster of contiguous 33cells (a sub-grid) contain unique numbers ranging from 1 to 9, such that each row and column of the 99grid also contain unique numbers ranging from 1 to 9. The puzzle is pre-ﬁlled with numbers called “clues”, where the number of clues given may range from 17 to 77 [1] [2]. Sudoku resembles a puzzle created in the middle ages, studied in 1782 by the mathematician Euler who christened it the “Latin Square” [3]. Sudoku in its modern form was introduced in 1979 by Howard Garns as a game named “Number Place”. Prior to this, in 1802, puzzle creators in France had attempted removing numbers from magic squares with the same number of squares as the modern sudoku, but with double digit numbers [4]. When modern sudoku got introduced in Japan in 1984, [5], it was christened “ suji wa dokushin ni kagiru ”, meaning “the digits must remain single”, and was shortened to “ sudoku ”, meaning “single number”. Sudoku is an exact-cover type problem that Authors acknowledge the support received from M S Ramaiah University of Applied Sciences, Bengaluru, India. N. K. Ipe is with the Department of Computer Science and Engineering, M S Ramaiah University of Applied Sciences, Bengaluru, India (e-mail: navinipe@gmail.com). R. V . Kulkarni is with the Department of Electronics and Communication Engineering, M S Ramaiah University of Applied Sciences, Bengaluru, India (e-mail: arvie@ieee.org).can be modeled as a constraint satisfaction problem (CSP), and is NP complete. Even the most difﬁcult puzzles can be solved by exhaustive backtracking and pivot-based heuristics. The purpose of this paper is not about providing an efﬁcient method of deﬁnitively solving sudoku puzzles and being better than other algorithms presented in literature. Solving sudoku is easily done via recursive backtracking algorithms or the dancing links algorithm [6] which can solve even 17-clue puzzles in a fraction of a second. This paper does not claim to present an “evolutionary” algorithm either. Evolutionary algorithms are considered good enough if they can provide a near-optimal solution, but sudoku requires an optimal solution. This paper presents the realities of utilizing stochastic approaches in a vast domain. This is achieved by providing a fresh perspective that visualizes the density of puzzle states, the proximity of non-optimal states to the solution and examining how a judicious use of techniques similar to minimum-conﬂicts [7] CSP, can narrow down and channel the search toward a solution, even when complex heuristics are not used. These visualizations have the potential to assist future work on sudoku algorithms or CSP algorithms where properties of the search space are not well known. The remainder of the paper is organized as follows: Evolutionary algorithms that attempt solving sudoku and concepts that utilize similar techniques for CSP are referenced in Sect. II. Deﬁnitions used, concept introductions and algorithm design are presented in Sect. III. Visualization of the ﬁtness landscape is presented in Sect. III-B4. Trial runs and results of solving the puzzle are presented in Sect. IV. The paper concludes with Sect. V. II. R ELATED WORK The Soft Computing (SC) paradigm, having the human mind as its role-model has also been referred to as Computational Intelligence (CI) and although it does not have a precise deﬁnition, it has been deﬁned in general by Fuzzy Logic, Evolutionary Computation (EC), Machine Learning and Probabilistic Reasoning. These are a class of algorithms that operate on constraints by utilizing a soft stochastic approach that converges to a desired solution. Despite evolutionary algorithms not being appropriate for solving sudoku, various evolutionary and logical inference techniques have been attempted. These range from SAT [8] and simulated annealing [9], to various Evolutionary Computing (EC) techniques like Particle Swarm Optimization (PSO) [10]–[13], genetic algorithms [14] and variants of harmony-search [15]. However, most algorithms do not attempt solving 17-clue puzzles due to the vastness of ﬁtness landscapes containing approximately 31034points (the number of permutations of a 17-clue puzzle). Among the most promising approaches that solved Sudoku via CI, was the hybridization that used human heuristics and genetic algorithms (GA) [16]. Some authors also utilized logical deduction to augment GA and solved even 21-clue puzzles with 100% success in a matter of seconds [17]. However, it is important to note that even among tough 21-clue or 17-clue puzzles, some puzzles are easier to solve than others. Therefore, it is important to verify the algorithm for various categories of puzzles before making conclusions about its efﬁcacy. In the constraint satisfaction domain, the minimum conﬂicts heuristic which solved the eight queens problem, could solve even a one million queens problem in an average of less than ﬁfty steps [7]. However, it was prone to getting stuck at a local optima and required execution of all possible iterations if all queens were initially positioned on the ﬁrst row. Perhaps a more intelligent approach would be to exploit features of the problem domain, as encouraged by [18] and [9], who also emphasized the importance of initialization, to reduce the search space. An important observation to note was the manner in which random perturbations [19] were capable of solving sudoku puzzles, sometimes offering quicker solutions than evolutionary approaches. The paper questioned the relevance of EC, when a purely random approach could solve even 21-clue puzzles. The utility of uniform randomness to locate optima in vast ﬁtness landscapes was further validated in [20], for a ﬁtness landscape that was similar in vastness to sudoku. Various authors [17] have already remarked on the futility of utilizing evolutionary approaches for solving sudoku, when simpler, quicker techniques like backtracking are sufﬁcient. Despite this, efforts at utilizing hybrid techniques to improve on evolutionary approaches to solve sudoku continue, while tending to avoid difﬁcult puzzles and offering minimal information on how the solution was obtained or how complex the algorithm was. Additionally, the mathematics and computation of sudoku is often presented in a complex symbolic form that provides insufﬁcient perceptual information about the problem space, to anyone who freshly attempts solving the puzzle. Although this paper began as a challenge to ﬁnd a new evolutionary method of solving sudoku, the vast literature we came across and our own observations while attempting to solve puzzles, exposed a research gap in the need to be able to visualize the magnitude of the problem space being tackled, the proximity of the optimal solution state to non-optimal states, puzzle densities, categories of solution difﬁculty and the hard truth that even puzzles that may appear to be simple (due to having a large number of given clues) may in-fact be difﬁcult to solve. III. D ESIGN A dataset was created, comprising of 99puzzles categorized by the given number of clues. A few famous puzzles like the “easter monster”, “2012’s World’s hardest puzzle by Arto Inkala” and “golden nugget” were manually added to the dataset. Puzzles were auto-selected in the orderthey were listed in the one million puzzle dataset [21] and the supersudokulib dataset [22]. A maximum of thirty puzzles were selected for each category. In a few categories, fewer than thirty puzzles were found, so the dataset comprised of a total of 438 puzzles. Figure 9 depicts number of puzzles per category. Results presented in this paper are obtained by attempting to solve puzzles from this assimilated dataset. A. Deﬁnitions (a) Cells of one individual ( 33 sub-grid) (b) Individuals of a puzzle in a 9 9grid (c) Circular swap Fig. 1: Some deﬁnitions Puzzle (S,SEorSF): The given “empty” Sudoku puzzle (SE) in which some cells are pre-ﬁlled with numbers called “clues”. When SEis completely ﬁlled with non-zero numbers, it is denoted as SF. The puzzle is referred to as Sin contexts where the state of the matrix is known. Individual (Ii): Each non-intersecting 33group of cells is an individual (Fig. 1a). The puzzle has n= 9 individuals, each containing unique numbers ranging from 1 to 9. Individuals I1toInare depicted in Fig. 1b. Team (Ti): Although any “leader” individual Iiand the individuals toward the left, right, top and bottom of Ii form a team, any reference to a team in this paper encompasses the individuals other than the leader. For example, in a team with I1as the leader, I1’s team members are T1=fI2;I3;I4;I7g. Similarly, T5= fI2;I8;I4;I6gandT6=fI3;I9;I5;I4g. Frozen cell (Fi): Any cell in Iicontaining a value that is temporarily or permanently ﬁxed in position. Cells with clues given at the start of the puzzle are always kept frozen. Algorithms can temporarily freeze any other cell when required. Frozen cells of a team are depicted with FT. Non-frozen cell (:Fi): Any cell in Iithat is not frozen. No conﬂict cell (:C): A cell containing a number that does not match any frozen number in its row and column, spanning the entire puzzle. Conﬂicting cell (C): A cell containing a number that matches the number in any frozen cell along the same row or column of the cell, spanning the entire puzzle (thus violating the rule of requiring unique numbers in every row and column). Obvious cell ( ): If any of the non-frozen numbers of anIican be inserted into only one :Fi(due to being the only cell in which the number would not conﬂict with anyFT). AnSEmatrix ﬁlled with ’s but is not yet SF, will be considered as the new SE. Obvious cells are often referred to as “naked single”, in literature. Cardinality : The number of elements in a set is the cardinality of the set. For example, the phrase “the number ofFicells is two” is denoted mathematically as:jFij= 2. Fitness of an individual (fi): The cardinality of Ccells inIi. Total ﬁtness (Pi=n i=1fi): The sum of ﬁtness values of all individuals. A fully solved puzzle will havePi=n i=1fi= 0. Circular swap/mutation (c4i): If a number in :Fi makes it a conﬂicting cell, the number is swapped with the number in another :Fi, but only if after the swap, the swapped cells would be :C. Figure 1c shows the pattern in which three cell values are swapped. The operation is represented as 34i, whereiis the individual id and c= 3(the maximum number of cells undergoing swaps). Whenc= 3, either three cells can be circular swapped or the numbers of two cells can be swapped. If c= 4, the number of cells involved in a circular swap can be 2, 3 or 4. The range of cis2c9. Swaps can also be referred to as “2-way swaps” or “3-way swaps”. Entropy (e): The number of times Iiperforms c4i. Permutations (p2mPr): Permutations of a set of m numbers taken rat a time. Any one of those permutations can be referred to as p. Bruted puzzles (B, with indicating the number of bruted individuals in any puzzle in B): Bruted matrices are created when permutations of :Fi(generated as j:FijPj:Fij) are inserted into number of individuals. This is explained in Sect. III-B5.