AN IRISH MATHEMATICIAN has discovered there is a limit to how hard a Sudoku puzzle can get.
A true Sudoku only has one solution and to achieve this there must be a minimum of 17 clues (or numbers provided), Professor Gary McGuire of University College Dublin has discovered.
Sudokuists have always thought that 17 was the magic number but were never completely sure…until now.
The UCD professor’s algorithm named checker was ran through a “supercomputer” to search all possible Sudoku solution grids for a 16-clue puzzle.
But no 16-clue puzzle was found.
“A brute force exhaustive search would not have been feasible, so we developed a novel algorithm that made the search possible,” said McGuire.
Using the original version of the checker algorithm we developed in 2006, it would have taken over 300,000 years on one standard computer to complete the search of all Sudoku solution grids…But with our new checker algorithm and access to a ‘high-end supercomputer’, we were able to complete the search in about 12 months or 7 million CPU hours.”
The 9×9 grid puzzles are believed to have originated from Latin squares but regained popularity in 2004 following their appearance in The Times in London.
They soon became the math lovers’ crossword and appear in daily newspapers across the world.
Professor McGuire’s computation was carried out at the Irish Centre for High-End Computing (ICHEC). The algorithm also has applications in software testing, bioinformatics and mobile phone networks.
For Professor McGuire’s study, follow this link>
Read: Want to live out that childhood dream of being an astronaut?>
Already a fan? Complete your signup...
Get breaking news from The Journal.ie via Facebook. Just click 'Like'.Contribute to this story
43 days ago #
“But with our new checker algorithm and access to a ‘high-end supercomputer’, we were able to complete the search in about 12 months or 7 million CPU hours”
I enoy cryptic crosswords and Sudoko but I have to ask, is this the best use that could be made of a supercomputer – 12 months to check the least clues that can be used in Sudoko??? Seriously???????
43 days ago #
“The algorithm also has applications in software testing, bioinformatics and mobile phone networks.”
43 days ago #
“They soon became the math lovers crossword”
There’s no math involved in solving a Sudoko, unless I’ve been doing it wrong all these years.
43 days ago #
Some people haven’t figured out that numbers and mathematics are two different things.
Sudoko is a number-based logic puzzle, as Julian said, no calculations involved.
Plenty of logical thinking though.
43 days ago #
Hey guys,
Used the phrase to indicate that Sudoku became as popular as crosswords on the puzzle page very quickly.
Maybe a bit of a generalisation to assume that those who like math also like number puzzles but sure can’t we all just get along?
Thanks for pointing it out though – have never attempted a Sudoku (crossword girl) and I have now had my first lesson in the office.
Cheers,
Sinead43 days ago #
Well it said it was by maths lovers, not that it was maths. Besides which, is logic not a part of maths?
43 days ago #
Of course a Sudoku involves maths, if you think otherwise you need to move away from thinking of maths as just being arithmetic. A lot of maths is basically just calculations (ie a lot of calculus and statistics) but there are vast swathes that are very different, including group theory and number theory which underpin Sudoku construction and the branches of logic which describe how they might be solved.
*should say logic puzzles instead of number puzzles I guess then!
43 days ago #
They’ve done this sort of thing in the past with Rubik’s Cube. Now you can’t say that’s a waste?!
43 days ago #
Oh god have ppl no
43 days ago #
Pedants….. Didn’t the Greeks just classify that as a mental illness?
43 days ago #
“…group theory and number theory which underpin Sudoku construction…”
Sorry, but with all respect that’s wrong. Group and number theory DO NOT underpin sudoku. Solving a sudoku puzzle is no more than a process of physical elimination – ultimately, deciding that a digit must go in a certain location because it is physically blocked from going anywhere else. If I want to put a can of beans in a cupboard and all but one shelf is completely full I’ll put it on the shelf that isn’t; there is no mathematical process at work and the logic behind sudoku is identical. Numbers are used because they are the most convenient – it could be letters, drawings of fruit, coloured buttons.
The main inaccuracy in the article, though, is that it equates the toughness of a puzzle with the number of seed numbers in the grid. A 17-seed puzzle may actually be very easy, and a 36-seed puzzle extremely difficult. What matters is the type of logical step required to either place a digit or eliminate a candidate.
I’ve found it’s reasonably easy to create a sudoku of 18 seeds. You use the left and right central regions and place 3 consecutive digits in each, one in the upper row and one in the lower row. Staying symmetrical, in the top and bottom rows of regions you place 3 consecutive digits in the middle region and 3 more (on different rows) left/right. I’ve produced several of these and some were calculated to be ‘very easy’ – that is, every required move is based on a cell having only one potential candidate.
On the other hand you can have a puzzle where only a dozen or so cells are unfilled, but the next move needs you to find X/Y-Wing, Skyscraper, Turbot Fish, Squirmbag or any other of the ‘colours’ shapes.
*sigh*
Where to begin?
I said group/number theory underpin Sudoku construction, not that Sudoku solving was doing group theory. That said there’s no reason why deciding what digit goes in a cell can’t be a group theory question (though probably not sensible in this case)
Your use of the word “Physical” is somewhat spurious.
Deciding where to put a can of beans can be expressed mathematically. Also rather different situation unless you insist that none of your shelves has two identical cans of beans on it (and that each can of beans must be in a different position on each shelf).
I am well aware that the use of numbers doesn’t necessarily imply the use maths and also that the absence of numbers doesn’t imply the absence of maths.Yes, the article makes the mistake of mixing difficulty with number of clues. Although I think it’s safe to say that the two are correlated in general. (I suspect your easy 18-clue example is the exception and most that sparse are quite tricky).
I don’t know the specific techniques you refer to at the end, but had you thought that you are (unconsciously) making use of group and/or number theory when you work these things out. Unless you’ve simply learned them by rote and are doing pattern recognition, in which case you’re not the one doing the thinking and so can’t comment on what techniques are being used.Fun underpins sudoku!
39 days ago #
ffs……….. its a puzzle does any1 give that much of a shit that you’re having a debate on the ins n outs of it!?…. :/
38 days ago #
I first saw sudoku puzzle in 2nd year college when studying discrete Maths. D puzzle had less than 17 clues and the lecturer said he’d give an A to anyone who could solve it. At the end of d year we solved it using an algorithm based on shortest path thm and graph theory (if I remember right).
Sudoku can be solved using Maths bt logic is easier!
Also here we call it Maths, bt in the US it’s math.
Add New Comment
Embed this post
To embed this post, copy the code below on your site
Download the TheJournal.ie for the iPhone, iPad and iPod
Most Popular
Most viewed articles in the past 24 hoursMost Commented
Most commented articles in the past 3 daysDownload the TheJournal.ie Android AppTrending Opinions
Most Popular Today
Column: It’s time to end the casual use of homophobic language in Ireland 
Sunday Times journalist Marie Colvin killed in Syria
Poll: Do you subscribe to the idea of a Lenten sacrifice? 
David Norris says tabloid editor told him stories about him were “payback” 
Personal info of YouPorn chat service users compromised, says company
Google glasses will send info to your eyeballs – reports
Comments (19 Comments)