Sudoku: Verskil tussen weergawes
Dewet (besprekings | bydraes) vertaling so vêr |
(Geen verskil)
|
Wysiging soos op 23:04, 6 Junie 2006
Sudoku (数独, uitgespreek sūdoku in Japannees) is a kopkrapper wat gegrond is op 'n logiese plasing van syfers in 'n 9×9 rooster. Hierdie rooster is op sy beurt opgemaak uit nege 3×3 roosters, en word afgeskop met verskeie syfers wat gegewe is in party selle. In elke ry, kolom en 3×3 rooster mag enige syfer slegs een maal voorkom. Om die kopkrapper te voltooi verg uithouvermoë en logiese vaardigheid. Alhoewel die raaisel vir die eerste keer in 1895 in 'n Franse koerant gepubliseer is, het dit 'n opvlamming herleef in Japan gedurende 1986, en het internasionale populariteit in 2005 gewen.
Inleiding
Die naam "Sudoku" is die Japannese afkorting van 'n langer frase, "Suuji wa dokushin ni kagiru" (数字は独身に限る), wat beteken "die syfers moet enkel bly." Dit is 'n handelsmerk van Nikoli in Japan. In Japannees word dit as [sɯːdokɯ] uitgespreek — sien Internasionale Fonetiese Alfabet vir nadere inligting. Alternatiewelik word die titel as "Su Doku" gespel.
Die syfers in Sudoku-raaisels word gebruik slegs vir gerief: die wiskundige verhoudings tussen syfers is heeltemal oorbodig, en enige stel simbole sal voldoen: letters, vorms of selfs kleure kan gebruik word sonder om die reëls te verander. Vir eenvoud word na syfers verwys in hierdie artikel.
Die trekkrag van hierdie raaisel is sy eenvoudige reëls, alhoewel die redenasie wat tot voltooiing lei kompleks kan wees. Sudoku word deur sommige leerders aangeraai as 'n oefening in logiese beredenering. Die moeilikheidsgraad van die raaisels kan gekies word om by die gehoor te pas. Die raaisels is verder baie maal vryelik beskikbaar vanuit gepubliseerde bronne, maar kan ook nuut geskep word in sagteware.
Die spel
In sy mees bekende vorm word die spel in 'n 9×9 rooster voorgelê, wat verder uit nege 3×3 roosters bestaan, en kan na verwys word as 'streke', 'blokke' of selfs 'kwadrante'. Party selle bevat reeds syfers, wat as leidrade optree. Die doel is om die leë selle te vul met syfers, sodat elke kolom, ry en streek die syfers 1-9 slegs een maal bevat. Elke syfer in die oplossing verskyn dus slegs een maal in elkeen van die drie "rigtings".
Strategieë vir die oplossing
Om die raaisel op te los moet drie prosesse gevolg word: rondsoek, merk en analise.
Rondsoek
Hierdie is die eerste stap, asook een wat dwarsdeur die oplossing gedoen word. Daar hoef slegs gesoek te word tussen analise-stappe, en bestaan uit twee basiese tegnieke:
- Uitkrap: Dit behels die deursoek van rye (of kolomme) om te bepaal watter lyn in 'n spesifieke streek 'n gegewe syfer mag bevat, en word deur 'n proses van eliminasie gevind. Die proses word dan herhaal met kolomme (of rye). Vir die vinnigste resultate word syfers uitgekap volgens hulle frekwensie van verskyning. Dit is belangrik om hierdie stap sistematies te doen, en al die syfers te toets van 1 tot 9.
- Tel van 1-9 in streke, rye en kolomme om vermiste syfers te vind: Deur te tel vanaf die laaste ontdekte syfer mag die soektog bespoedig. Dit is ook die geval — veral wanneer die raaisels moeiliker raak — deur dit verkeerdom te benader: d.w.s., deur die sel se streek, ry en kolom te deursoek vir syfers wat dit nie moontlik kan wees nie om die oorblywende waardes te bepaal.
- or,
- and
The puzzle is then completed by assigning an integer between 1 and 9 to each vertex, in such a way that vertices that are joined by an edge do not have the same integer assigned to them.
A completed Sudoku grid is a special type of Latin square with the additional property of no repeated values in any 3×3 block. The number of classic 9×9 Sudoku solution grids was shown in 2005 by Betram Felgenhauer and Frazer Jarvis to be 6,670,903,752,021,072,936,960 [1] Sjabloon:OEIS : this is roughly 0.00012% the number of 9×9 Latin squares. Various other grid sizes have also been enumerated -- see the main article for details. The number of essentially different solutions, when symmetries such as rotation, reflection and relabelling are taken into account, was shown by Ed Russell and Frazer Jarvis to be just 5,472,730,538 [2] Sjabloon:OEIS. Both results have been confirmed by independent authors.
The maximum number of givens that can be provided while still not rendering the solution unique is four short of a full grid; if two instances of two numbers each are missing and the cells they are to occupy form the corners of an orthogonal rectangle, and exactly two of these cells are within one region, there are two ways the numbers can be assigned. Since this applies to Latin squares in general, most variants of Sudoku have the same maximum. The inverse problem—the fewest givens that render a solution unique—is unsolved, although the lowest number yet found for the standard variation without a symmetry constraint is 17, a number of which have been found by Japanese puzzle enthusiasts [3] [4], and 18 with the givens in rotationally symmetric cells.
History
Number puzzles have been appearing in newspapers for well over a century. Le Siècle, a French daily, produced a 9x9 grid with 3x3 sub-squares as early as 1892, but used double-digit numbers rather than the familar 1-9 [5]. In 1895, another French daily, La France, created a puzzle that used the numbers 1-9 but did not mark the 3x3 sub-squares (although the solution does indeed have 1-9 in each of the 3x3 areas where the sub-squares would be). These puzzles, printed weekly, were a feature of newspaper titles including L'Echo de Paris for about a decade but disappeared at about the time of the First World War.[6]
The modern Sudoku was designed anonymously by Howard Garns, a 74-year-old retired architect and freelance puzzle constructor, and first published in 1979.Sjabloon:Ref Although likely inspired by the Latin square invention of Leonhard Euler, Garns added a third dimension (the regional restriction) to the mathematical construct and (unlike Euler) presented the creation as a puzzle, providing a partially-completed grid and requiring the solver to fill in the rest. The puzzle was first published in New York by the specialist puzzle publisher Dell Magazines in its magazine Dell Pencil Puzzles and Word Games, under the title Number Place.
The puzzle was introduced in Japan by Nikoli in the paper Monthly Nikolist in April 1984 as Suuji wa dokushin ni kagiru (数字は独身に限る?), which can be translated as "the numbers must be single" or "the numbers must occur only once" (独身 literally means "single; celibate; unmarried"). The puzzle was named by Maki Kaji (鍜治 真起 Kaji Maki?), the president of Nikoli. At a later date, the name was abbreviated to Sudoku, taking only the first kanji of compound words to form a shorter version. In 1986, Nikoli introduced two innovations that guaranteed the popularity of the puzzle: the number of givens was restricted to no more than 32 and puzzles became "symmetrical" (meaning the givens were distributed in rotationally symmetric cells). It is now published in mainstream Japanese periodicals, such as the Asahi Shimbun. Within Japan, Nikoli still holds the trademark for the name Sudoku; other publications in Japan use alternative names.
In 1989, Loadstar/Softdisk Publishing published DigitHunt on the Commodore 64, which was apparently the first home computer version of Sudoku. At least one publisher still uses that title.
Yoshimitsu Kanai published his computerized puzzle generator under the name Single Number for the Apple Macintosh [7] in 1995 in Japanese and English, for the Palm (PDA) [8] in 1996, and for Mac OS X [9] in 2005.
Dell Magazines, which publishes the original Number Place puzzle, now also publishes two Sudoku magazines: Original Sudoku and Extreme Sudoku. Additionally, Kappa reprints Nikoli Sudoku in GAMES Magazine under the name Squared Away; the New York Post, USA Today, The Boston Globe, Washington Post, The Examiner, and San Francisco Chronicle now also publish the puzzle. It is also often included in puzzle anthologies, such as The Giant 1001 Puzzle Book (under the title Nine Numbers).
Within the context of puzzle history, parallels are often cited to Rubik's Cube, another logic puzzle popular in the 1980s. Sudoku has been called the "Rubik's cube of the 21st century".
Popularity in the media
In 1997, retired Hong Kong judge Wayne Gould, 59, a New Zealander, saw a partly completed puzzle in a Japanese bookshop. Over 6 years he developed a computer program to produce puzzles quickly. Knowing that British newspapers have a long history of publishing crosswords and other puzzles, he promoted Sudoku to The Times in Britain, which launched it on 12 November 2004 (calling it Su Doku). The puzzles by Pappocom, Gould's software house, have been printed daily in the Times ever since.
Three days later The Daily Mail began to publish the puzzle under the name "Codenumber". The Daily Telegraph introduced its first Sudoku by its puzzle compiler Michael Mepham on 19 January 2005, and other Telegraph Group newspapers took it up very quickly. Nationwide News Pty Ltd began publishing the puzzle in The Daily Telegraph of Sydney on 20 May 2005; five puzzles with solutions were printed that day. The immense surge in popularity of Sudoku in British newspapers and internationally has led to it being dubbed in the world media in 2005 the "fastest growing puzzle in the world".
It was not until the British Daily Telegraph introduced the puzzle on a daily basis on 23 February 2005 with the full front-page treatment advertising the fact, that the other UK national newspapers began to take real interest. The Telegraph continued to splash the puzzle on its front page, realizing that it was gaining sales simply by its presence. Until then the Times had kept very quiet about the huge daily interest that its daily Sudoku competition had aroused. That newspaper already had plans for taking advantage of their market lead, and a first Sudoku book was already on the stocks before any other national UK papers had realised just how popular Sudoku might be.
By April and May 2005 the puzzle had become popular in these publications and it was rapidly introduced to several other national British newspapers including The Independent, The Guardian, The Sun (where it was labelled Sun Doku), and The Daily Mirror. As the name Sudoku became well-known in Britain, the Daily Mail adopted it in place of its earlier name "Codenumber". Newspapers competed to promote their Sudoku puzzles, with The Times and the Daily Mail each claiming to have been the first to feature Sudoku.
The rapid rise of Sudoku from relative obscurity in Britain to a front-page feature in national newspapers attracted commentary in the media (see References below) and parody (such as when The Guardian's G2 section advertised itself as the first newspaper supplement with a Sudoku grid on every page [10]). Sudoku became particularly prominent in newspapers soon after the 2005 general election leading some commentators to suggest that it was filling the gaps previously occupied by election coverage. A simpler explanation is that the puzzle attracts and retains readers—Sudoku players report an increasing sense of satisfaction as a puzzle approaches completion. Recognizing the different psychological appeals of easy and difficult puzzles, The Times introduced both side by side on 20 June 2005. From July 2005, Channel 4 included a daily Sudoku game in their Teletext service (at page 391). On 2 August 2005, the BBC's programme guide Radio Times started to feature a weekly Super Sudoku. The Dutch company Mobile Excellence International developed together with their Vietnamese partner the first mobile i-mode Sudoku game. The game was launched throughout Europe in September 2005. [11]
As a one-off, the world's first live TV Sudoku show, Sudoku Live, was broadcast on 1 July 2005 on Sky One. It was presented by Carol Vorderman. Nine teams of nine players (with one celebrity in each team) representing geographical regions competed to solve a puzzle. Each player had a hand-held device for entering numbers corresponding to answers for four cells. Conferring was permitted although the lack of acquaintance of the players with each other inhibited an analytical discussion. The audience at home was in a separate interactive competition. A Sky One publicity stunt to promote the programme with the world's largest Sudoku puzzle went awry when the 275 foot (84 m) square puzzle was found to have 1,905 correct solutions. The puzzle was carved into a hillside in Chipping Sodbury, near Bristol, England, in view of the M4 motorway. The stunt was cleverly timed to coincide with a major road expansion, where an imposed 40 mph speed restriction allowed drivers to safely view the puzzle whilst driving.
United States broadcaster CBS has run several stories concerning Sudoku, including on the Early Show in summer 2005, and on the CBS Evening News that autumn, on October 26.
Dr. House was clearly seen working on a Sudoku puzzle on his office computer in one scene of the December 13 2005 episode of House, M. D.; Sudoku is supposedly now banned on the studio set due to the cast constantly playing it.
During February 7th's episode of The Daily Show, correspondent Jason Jones suggested that to ease the conflict over the Jyllands-Posten Muhammed caricatures, newspapers should be stripped down to only featuring Sudoku puzzles.
There are also Sudoku video games, such as Go! Sudoku for the PSP Dr. Sudoku for the GBA and Sudoku Mania for the DS (estimated USA release June 20 2006). Sudokus are also featured in Brain Age: Train Your Brain in Minutes a Day.
Competitions
The first world championship was held in Lucca, Italy from 10 to 12 March 2006 [12]; it was won by Jana Tylova, a 31-year-old accountant from the Czech Republic. The competition included variants; a full list can be found in the PDF here.
The United States Sudoku Association Inc. [13] is another corporation hosting tournaments across the United States. Currently, they are sponsoring a tournament for charity for the American Legion. Their website also includes a forum.
See also
- List of newspapers featuring Sudoku
- List of Nikoli puzzle types
- List of Sudoku terms and jargon
- Latin square
- Killer Sudoku
-->
Verwysings
- Garns, H. "Number Place." Dell Pencil Puzzles & Word Games. No. 16, May p. 6, 1979.
- sudoku.com Website of Wayne Gould, populariser of Sudoku; also includes forum which discusses solution techniques and mathematics of Sudoku
- NRC Sudokus - information about NRC Sudokus
- Sudoku Variations article at MAA Online; also includes the history of the puzzle's invention
- Basic Solving Techniques
- Keys to Solution at Puzzle Japan
- Solving Sudoku Step-by-step guide by Michael Mepham
- Mathematics of Sudoku
- Complexity and Completeness of Finding Another Solution and its Application to Puzzles Mathematical reference proving NP-completeness
- Frazer Jarvis's Sudoku page Contains programs, data, an article with Bertram Felgenhauer detailing the enumeration of Sudoku grids, and the results of Ed Russell
- Hayes, B., "Unwed Numbers - The mathematics of Sudoku, a puzzle that boasts 'No math required!'", American Scientist 94(1):12 (2006) [14].
- History
- Rules and history from the Nikoli website
- Boyer, C., « Les ancêtres français du sudoku », Pour La Science 344 (June 2006), pages 8-11 & 89
- Article in The Times on Sudoku's alleged French ancestry
- Java Programs to Solve Sudokus
- Solving Sudokus in Java An article explaining how to solve Sudokus using Constraint programming in Java by Koalog
- Java Sudoku Solver A short program to solve Sudoku problems using backtracking similar to the eight-queens algorithm.
- Commentary on the sudden popularity of Sudoku in Britain: