18 Months of Sudoku

I decided to learn Sudoku to relax my mind.

Early in 2019, I down­loaded a Sudoku app to test if this puzzle could be a relax­ing pastime.

The res­ults? Eighteen months later, I’ve fallen pretty deep into this numer­ic rab­bit hole.

From know­ing next to noth­ing about Sudoku, I now know more than most about this beau­ti­ful little puzzle.

Here we go:

What I Knew of Sudoku Before

As many of you, dear read­ers, may already know, the found­a­tion of a Sudoku con­sists of nine rows (r1-r9) and nine columns (c1-c9), form­ing a neatly struc­tured grid. This grid con­tains nine dis­tinct squares, each con­tain­ing nine indi­vidu­al cells.

This intel­lec­tu­al exer­cise aims to metic­u­lously pop­u­late each cell with a numer­ic­al value ran­ging from 1 to 9. The chal­lenge, how­ever, lies in ensur­ing that no integer is repeated with­in any single row, column, or 9‑cell square, thereby demand­ing care­ful thought and stra­tegic planning.

Consequently, upon suc­cess­ful com­ple­tion, the fully solved puzzle will fea­ture a well-bal­anced dis­tri­bu­tion of each digit from 1 to 9, with nine instances of every number.

However, one can­not rely on these con­straints to achieve the desired out­come. Each unique puzzle starts with pre­de­ter­mined numer­ic­al place­ments con­gru­ent with the even­tu­al solu­tion. These giv­en num­bers serve as a found­a­tion upon which the solv­er must build.

Utilising these ini­tial clues as a guid­ing com­pass, it becomes the solver’s task to nav­ig­ate the com­plex­it­ies of the puzzle, metic­u­lously pla­cing each digit in its right­ful pos­i­tion. Once all the num­bers have been expertly arranged, the puzzle is complete.

This is what I knew of Sudoku before down­load­ing my first Sudoku app some 18 months ago.

But there was more to learn.

The Origin Story of Sudoku

Sudoku puzzles have an ancient feel, much like chess or go. However, the numer­ic puzzle is a rel­at­ively recent phenomenon.

“The game first appeared in Japan in 1984 where it was giv­en the name “Sudoku,” which is short for a longer expres­sion in Japanese – “Sūji wa dok­ush­in ni kagiru” – which means, “the digits are lim­ited to one occur­rence.”
Source: The his­tory of Sudoku

Contrary to what I thought, the Sudoku puzzle wasn’t inven­ted in Japan — even though it got its name there. Unfortunately, the invent­or of the Sudoku puzzle died before get­ting to exper­i­ence his inven­tion became a glob­al phenomenon.

“The mod­ern Sudoku was most likely designed anonym­ously by Howard Garns, a 74-year-old retired archi­tect and freel­ance puzzle con­struct­or from Connersville, Indiana, and first pub­lished in 1979 by Dell Magazines as Number Place (the earli­est known examples of mod­ern Sudoku). Garns’s name was always present on the list of con­trib­ut­ors in issues of Dell Pencil Puzzles and Word Games that included Number Place, and was always absent from issues that did not. He died in 1989 before get­ting a chance to see his cre­ation as a world­wide phe­nomen­on. Whether or not Garns was famil­i­ar with any of the French news­pa­pers lis­ted above is unclear.”
Source: Wikipedia

“The Times of London began pub­lish­ing Sudoku puzzles in 2004, and the first US news­pa­per to fea­ture Sudoku was The Conway (New Hampshire) Daily Sun in 2004. Within the past 10 years, Sudoku has become a glob­al phe­nomen­on. The first World Sudoku Championship was hos­ted in Italy in 2006 and the 2013 World Sudoku Championship will be held in Beijing.”
Source: The his­tory of Sudoku

Fans of the fam­ous bio­lo­gist Richard Dawkins will be pleased to note that the Sudoku puzzle is a fas­cin­at­ing case study for memes!

“Scientists have iden­ti­fied Sudoku as a clas­sic meme — a men­tal vir­us which spreads from per­son to per­son and sweeps across nation­al bound­ar­ies. Dr Susan Blackmore, author of The Meme Machine, said: ‘This puzzle is a fant­ast­ic study in memet­ics. It is using our brains to propag­ate itself across the world like an infec­tious vir­us.’”
Source: So you thought Sudoku came from the Land of the Rising Sun

Notation, Notation, Notation

The first thing I learned about Sudoku was — nota­tion. Denoting the cells for poten­tial num­bers becomes essen­tial due to the inab­il­ity to place most digits immediately.

Consider, for example, pla­cing the num­ber two with­in box 1 (the left upper-corner 9‑digit square). Suppose the num­ber two can be posi­tioned in only two loc­a­tions, prompt­ing me to annot­ate those as pro­spect­ive candidates.

Suppose we encounter a sim­il­ar con­straint with­in box 1 con­cern­ing the num­ber five — and it hap­pens to be the same two cells! 

Given that both num­bers share only two cells in box 1, it becomes evid­ent that these cells must accom­mod­ate a 2 or a 5. Consequently, I can con­fid­ently ascer­tain that no oth­er digit besides 2 or 5 can occupy these cells.

This tech­nique is known as a “naked pair.”

As a res­ult, even though I can­not defin­it­ively assign the num­bers 2 and 5 with­in box 1, the nota­tion leads to sev­er­al oth­er con­straints that may prove instru­ment­al in annot­at­ing (or elim­in­at­ing annota­tions) for vari­ous digits in cor­res­pond­ing grid cells.

In most Sudoku puzzles, meth­od­ic­al nota­tion is the only way to solve the puzzle.

Other Sudoku Notations

Perhaps due to the par­tic­u­lar cir­cum­stances of the pan­dem­ic, the YouTube chan­nel Cracking the Cryptic gained lots of trac­tion. And it ended up in my feed, too.

I imme­di­ately under­stood the power of using dif­fer­ent nota­tion tech­niques via the YouTube show. For instance, noted digits in the centre of the cell will mean that the cell will con­tain one of those digits and no oth­er numbers.

Noted digits along the edges of the cell mean that those digits are can­did­ates, but there might still be unnoted digits that might go into that cell.

A vari­ant of the edge nota­tion is called Snyder nota­tion:

Snyder nota­tion, named after the renowned Sudoku expert Thomas Snyder, is a refined and sys­tem­at­ic tech­nique Sudoku enthu­si­asts use to improve their puzzle-solv­ing pro­fi­ciency. This meth­od entails stra­tegic­ally annot­at­ing small pen­cil marks with­in each cell to sig­ni­fy the pos­sible can­did­ates for that spe­cif­ic loc­a­tion. By doing so, solv­ers can bet­ter visu­al­ize pat­terns and restric­tions, ulti­mately enhan­cing their abil­ity to ascer­tain the cor­rect place­ment of digits.

The Snyder nota­tion approach involves denot­ing only pairs of poten­tial can­did­ates with­in 3×3 boxes when the can­did­ates can occupy exactly two cells with­in that box. 

The tech­nique hinges on the premise that identi­fy­ing these pairs of can­did­ates will reveal crit­ic­al inform­a­tion about the grid’s con­straints and, in turn, the place­ment of oth­er digits. This focused and stream­lined nota­tion prac­tice reduces clut­ter and con­fu­sion, enabling solv­ers to more effect­ively recog­nize oppor­tun­it­ies for pro­gress and solve the puzzle with great­er ease and efficiency.

Knowing how to use dif­fer­ent types of nota­tion will quickly take the new­bie solv­er to solve more advanced puzzles rapidly.

More Basic Sudoku Techniques

Solvers util­ise sev­er­al oth­er Sudoku tech­niques to pro­gress through and ulti­mately solve puzzles. 

Some of these meth­ods include:

More Advanced Sudoku Techniques

However, I quickly learnt that really good Sudoku puzzles require more advanced tech­niques to be solved.

Some of these meth­ods include:

And Then There’s Bifurcation …

Bifurcation, com­monly called “tri­al and error” or “guess­ing,” is a tech­nique some Sudoku solv­ers employ, par­tic­u­larly when con­front­ing com­plex and chal­len­ging puzzles. 

This meth­od involves select­ing a cell with a lim­ited num­ber of can­did­ates (ideally a bi-value cell with only two pos­sib­il­it­ies) and tent­at­ively assign­ing one of the can­did­ates as the cor­rect value. 

The solv­er then solves the puzzle based on this assump­tion, care­fully observing the res­ult­ing implications. 

If the ini­tial guess leads to a con­tra­dic­tion or inval­id solu­tion, the solv­er back­tracks to the ori­gin­al bifurc­a­tion point and pro­ceeds with the altern­at­ive candidate. 

Although bifurc­a­tion can be an effect­ive approach to solv­ing dif­fi­cult puzzles, many Sudoku enthu­si­asts con­sider it less eleg­ant and less intel­lec­tu­ally sat­is­fy­ing com­pared to the sys­tem­at­ic applic­a­tion of logic-based techniques.

In short: Don’t resort to bifurcation.

Examples of Sudoku Variations

Once you start solv­ing more advanced puzzles, you can’t help but dis­cov­er the adja­cent uni­verse of Sudoku variations.

The Sudoku vari­ations invite a wide array of highly sat­is­fy­ing logic applic­a­tions. None of the advanced solv­ing tech­niques is typ­ic­ally lost, but with a vari­ation, you can play around with addi­tion­al and some­times even more sat­is­fy­ing techniques.

Also, these vari­ations allow for more cre­at­ive free­dom for puzzle setters.

The Genius of Master Setters

It’s not the solv­ers who are the super­stars in Sudoku; it’s the setters.

Whether they are clas­sics or vari­ations, beau­ti­ful puzzles are typ­ic­ally cre­ated by a mas­ter set­ter — by hand. Make no mis­take about it: set­ting up a Sudoku puzzle is hard work.

The mas­ter Sudoku set­ter will reverse-engin­eer the puzzle to chal­lenge you and lead you through the puzzle in a cre­at­ive way. And a whole glob­al com­munity of highly tal­en­ted solv­ers holds these fam­ous mas­ter set­ters in extremely high regard.

These set­ters some­times have unique styles; in cer­tain Sudokus, you can recog­nise the setter’s approach to set­ting puzzles, espe­cially in vari­ations where the cre­at­ive free­dom for the set­ter is much greater.

A few not­able examples include:

Setting a beau­ti­ful puzzle is the work of a mas­ter. And set­ting a beau­ti­ful yet highly unique puzzle is a genius’s work.

The Complexity of Sudoku

One rule of Sudoku is that each puzzle must only have one unique solu­tion. A Sudoku puzzle is lit­er­ally “broken” if there are mul­tiple solutions.

How many start­ing clues must be provided to ensure a puzzle has only one final solu­tion? The com­munity has found sev­er­al solv­able puzzles with 17 start­ing digits and a unique solu­tion. But no one has been able to con­struct a Sudoku where the same is true with only 16 giv­en num­bers at the start. 

Researchers in Dublin decided to test all pos­sible 16-digit puzzles.

“Nevertheless, the res­ult­ing cal­cu­la­tion is still a mon­ster. The Dublin team say it took 7.1 mil­lion core-hours of pro­cessing time on a machine with 640 Intel Xeon hex-core pro­cessors. They star­ted in January 2011 and fin­ished in December.”
Source: Mathematicians Solve Minimum Sudoku Problem

The answer?

There are no unique solu­tions to puzzles with 16 or few­er start­ing digits. But we still don’t know why; we only know there aren’t.

How To Get Started

I can’t think of a bet­ter way to start than to explore the YouTube chan­nel Cracking the Cryptic. The show’s hosts, Mark Goodliffe and Simon Anthony have rep­res­en­ted the UK in the World Puzzle and World Sudoku Championships.

What should you study next?