The Sudoku Phenomenon
The perfect analogy for a Sudoku puzzle would be the geeky brother to the sophisticated crossword and the bubbly comic strip; tucked into a corner by their morbid parents , ‘The News’. Sudoku is a global phenomenon with players of all ages and undoubtedly, any newspaper or magazine is incomplete without a Sudoku in it. But how did this magnificent puzzle come into being?
The history of Sudoku dates back to the eighteenth century mathematician Leonhard Euler’s game called “Latin Squares” which is based on the idea of arranging numbers in such a way that any number would occur only once in each row or column. The modern Sudoku was designed by Howard Garns, a freelance puzzle constructor from Connersville, Indiana which was published in 1979. In Japan, the puzzle was introduced by Nikoli in the paper Monthly ‘Nikolist’ in April 1984 as ‘Sūji wa dokushin ni kagiru’(thankfully, it is shortened to Sudoku) which means ,’the digits must be single’. In March 1997, a New Zealand judge named Wayne Gould saw a partially solved Sudoku in a bookstore in Tokyo. He developed a liking for Sudoku and spent the next six years developing a computer program that could rapidly generate Sudoku puzzles. ‘The Times’ in Britain began publishing these from 2004. And as they say, the rest is history.
A Sudoku puzzle is considered completed if all entries (which typically range from 1-9) in any row, column or box are distinct. The most standard form of sudoku which is omnipresent in print media is the 9 by 9 sudoku grid. But what’s life without change? To combat the monotonicity of staring at a 9 by 9 grid every day, multiple variants were invented.
In most cases, the standard conditions of sudoku hold (distinct elements in a row, column, and box) and with them, a couple of additional constraints are added. These restrictions make it possible for the puzzle to host a greater number of unknowns. Some of the variants include:
a) Killer Sudoku
b) Hyper Sudoku
c) Twin Sudoku
A Rubik’s cube version of the standard sudoku puzzle exists too!
Let’s get down to the nitty-gritty details; how exactly do you solve a sudoku? These types of problems can only be solved using a restricted class of brute force search algorithms.
· The general problem of solving a sudoku puzzle is NP-complete. It simply means that the time taken to solve a sudoku puzzle increases as a polynomial function of its size. This polynomial cannot be determined.
· Backtracking is a Depth-First Search algorithm. A DFS examines all nodes along a branch up to the very last level in a graph and then selects the next branch.
· The pointer first solves a cell by placing digits 0-9 and checking if they solve the criteria for solving the puzzle.
· The pointer moves on after an appropriate digit is found. If it is not found, the pointer returns to an earlier cell to change its value so as to free the current cell from its restriction.
· The difficulty of the puzzle plays no role in this problem.
We, as intelligent homo-sapiens, tend to apply backtracking in a smarter way. We look for spaces that may be easier to solve so as to find a few constants before applying backtracking. By elimination, one may solve a majority of the puzzle before applying the algorithm to a few squares.
Isn’t Sudoku the best casual puzzle to ever exist? It’s easy to pick up and if you become a regular player, you can flaunt it around and people would think you are smart (even though you are only using primal human logic!). Also, sudoku toilet paper exists.
An Article By: Coding and Logic Team
DISCLAIMER
Shaastra TechShots’ publications contain information, opinions and data that Shaastra TechShots considers to be accurate based on the date of their creation and verified sources available at that time. It does not constitute either a personalized opinion or a general opinion of Shaastra or IIT Madras. The information provided comes from the best sources, however, Shaastra TechShots cannot be held responsible for any errors or omissions that may emerge.