Talk:Sudoku/Archive 1

Archive 1

Archive 2

Archive 3

Archive 4

This archive page covers approximately the dates between Jan 1, 2005 and Sep 23, 2005.

Post replies to the main talk page, copying the section you are replying to if necessary. (See Wikipedia:How to archive a talk page.)

Please add new archivals to Talk:Sudoku/Archive 2. Thank you. angusj 23:05, 23 September 2005 (UTC)

The term 'givens'

The Sudoku puzzles printed in most UK newspapers are apparently computer-generated but employ symmetrical givens, implying a more humanistic algorithm;

What!? Jooler 10:12, 14 May 2005 (UTC)

I know "symmetrical givens" is defined in the article; "humanistic algorithm" (for the non-computer-scientists out there) means basically a computer program written to do something in the exact same way a human being would. A computer could easily throw together a valid solution grid and then discard numbers to create a puzzle; I'm guessing Wayne Gould's program follows something more like the "Let's Make Sudoku!" site linked to by the article. ...Anyone know Wayne Gould? - ZM Zotmeister 17:50, 17 May 2005 (UTC)

Well when I wrote the above comment I hadn't read the term "givens" used in reference to numbers already placed in the grid, so it read as bewildering. I'm not sure "givens" is widely used anyway Google gives only 10 hits for 'sudoku +givens'. In any case the language is obscure. Jooler 10:35, 18 May 2005 (UTC)

The term "given" (as a noun) is generic: it applies to many different kinds of puzzles, not just Sudoku. It may also be the case that the term is only common parlance in the United States, whereas the Sudoku craze is presently epicentered in the United Kingdom. ...Besides, this is an encyclopedia - this is where the terminology should be defined.  :) - ZM Zotmeister 16:18, 18 May 2005 (UTC)

For what it's worth, I've become familiar with the term "givens" in this sense from UK-born puzzles, though my puzzle experience is wider than most. Hv 01:32, 17 August 2005 (UTC)

Origins of Sudoku

Thought I'd mention an article [1] in the (British) Observer newspaper which discusses the origins of Sudoku, including its origins in the US. 81.158.205.208 18:12, 15 May 2005 (UTC)

They say that Euler came up with the idea of latin square and that Dell published puzzles based on this and then they say that "Publisher Nikoli made two small improvements to the concept and renamed it Sudoku". what were those two small improvements? If they came up with the idea of dividing the grid into blocks of nine, then that would incline me to give Nikoli the credit for the modern puzzle. Jooler 18:48, 15 May 2005 (UTC)

I would guess, based on the rest of this article, that one of the innovations was the symmetrical placement of givens. Not sure what the other would be, though. Perhaps ensuring that none of the givens can be deduced from other givens?--OpenToppedBus 09:16, May 16, 2005 (UTC)

From these comments it is plausible that the two changes were (i) dividing the grid into blocks of nine and (ii) symmetrical placement of givens. JPF 10:22, 16 May 2005 (UTC)

Definitely not the former - the printed Observer article has a photo of the earliest Dell version (from 1979) and it's clearly divided into blocks of nine.--OpenToppedBus 11:39, May 16, 2005 (UTC)

My guess would be the symmetrical givens and hand-construction. Opinion: Nikoli puzzles give one the sense that they are matching wits with the composer; Dell puzzles feel randomly thrown together and lack personality. I live in the United States but possess books from both companies, importing Nikoli works from Japan, and I feel there's no comparison: those of Nikoli are far superior. - ZM Zotmeister 17:43, 17 May 2005 (UTC)

D'oh. Just checked Nikoli's own website, and they answer that question: symmetrical givens, and limited givens (under thirty). My opinion still stands, though. - ZM Zotmeister 18:16, 17 May 2005 (UTC)

Questions about Sudoku copied from the Wikipedia:Reference Desk

Having spent much of the day staring (in vain) at today's Sudoku puzzle in The Guardian, I found myself pondering. On a standard 9X9 grid, what would be the minimum number of "givens" needed to define a unique solution? And what would be the maximum possible number of givens that would allow more than one solution? --OpenToppedBus 16:11, May 13, 2005 (UTC)

The maximum possible is 77 = 9 * 9 - 4 - If you have any rectangle in which you have to fill the corners with two numbers, then you will not be able to distinguish between the two mirror images. The minimum... Um, no idea.-Fangz 16:39, 13 May 2005 (UTC)

According to http://www.dailymail.co.uk/pages/live/articles/news/news.html?in_article_id=348348&in_page_id=1770&in_a_source=# "It has been said that in a classic 81-square Sudoku grid, the fewest number of squares that can be filled in by the creator for the reader to have any chance of finishing the puzzle is 19." Jooler 12:39, 14 May 2005 (UTC)

I have seen Sudokus with 20 "givens" - it would be interesting to see a "valid" Sudoku with only 19 givens. The majority of puzzles have 22 to 26 givens, with 2 to 4 in each 3x3 block, although easy puzzles can have 30 or more givens. Gandalf61 08:53, May 15, 2005 (UTC)

Go to http://www.sudoku-xls.com/puzarc.pdf and look at the puzzles rated Almost Impossible - those only have 19 givens. (At time of writing, there are two of these.) --Pidgeot (t) (c) (e) 16:28, 15 May 2005 (UTC)

Those "Almost Impossible" ones are very hard, so far I've only managed to place 2 numbers and I've got 2 sets of 2 squares which are limited to holding one or other of a pair of numbers. Not gone to the extent of putting candidate numbers in every box though. Jooler 10:28, 18 May 2005 (UTC)

I will have to double-check my copies of Nikoli Gekikara Sudoku (Gekikara = Super Hard) 1 & 2; I could have sworn I saw one in there with only eighteen givens. Maybe my memory is off by one, but I'll find out and report back. In other news: the questions that started this section of the Talk page are mathematically significant, so I'm adding them to the article under that heading. I also note that, checking the link in Jooler's first post, that the puzzlesmiths of that publication should read the "Let's Make Sudoku!" site linked here, as they are going about it in a very inefficient manner in comparison. I should know - I'm a puzzlesmith, and I've used both methods. - ZM Zotmeister 16:18, 18 May 2005 (UTC)

[Indentation reset] An example eighteen, swiped from a Usenet article in rec.puzzles (<36013B8B.498CE80D@inprise.com>):

+-----+-----+-----+
|- - 5|- - -|- 4 -|
|- - -|8 - -|- - 6|
|3 - 2|- - 1|- - -|
+-----+-----+-----+
|- - -|- - 4|- 2 -|
|- - 9|- - -|5 - -|
|- 6 -|3 - -|- - -|
+-----+-----+-----+
|- - -|- - -|- - 3|
|- - -|- - 5|- - -|
|- 1 -|- - -|6 8 -|
+-----+-----+-----+

The article claims that the best for symmetrical givens is 20 (and gives a couple of examples); I suspect that both of these are empirical figures rather than calculated. Psmith 09:41, 19 May 2005 (UTC)

By the way, I ran this through a solver and can confirm that it has only one unique solution. So there's definitely at least one "eighteen" (or 9! eighteens, if you like, any renumbering would also be valid). --Robert Merkel 23:25, 23 May 2005 (UTC)

For each solution you can move around each block of 3 rows of columns through the following permutations, ABC, ACB, BAC, BCA, CAB, CBA, thus for each unique solution there are actually 9x6x6 (486) variations on that solution. Jooler 06:23, 24 May 2005 (UTC)

Um, I see where you get the 6x6 from, but I think you might be mistaking my 9 for 9 factorial = 362,880. You can also pivot columns or rows that are in the same "set of blocks" - ie rows or columns (1,2,3), (4,5,6), or (7, 8, 9). If I'm calculating this correctly, that would mean that you'd end up with $9!\cdot 6^{6}=16,930,529,280$ variations. That may sound like a lot, but it's still an infinitesimally small part of the total solution space. --Robert Merkel 14:03, 27 May 2005 (UTC)

The following paragraph was recently added to Japanese Wikipedia. (my translation)

The problem with the fewest givens yet published has 17 givens. It appeared in [a now discontinued Japanese magazine] Puzzler, when the magazine were seeking the fewest givens of some puzzles including sudoku (the magazine called it Number Place). After that, several 17-given problems were found by computer retrieval. All of them were asymmetric. The best one with symmetric placement is the piece that appeared in the 31st issue of Puzzle Communication Nikoli [published in the autumn of 1990], which has 18 givens. However, there is no proof that it is the limitation.

Pitan 19:58, 26 May 2005 (UTC)

Pitan, can you ask the Japanese Wikipedia to clarify this further. If somebody could provide the actual puzzle it would be good... --Robert Merkel 14:03, 27 May 2005 (UTC)

I've found the website [2] that was discussing the fewest givens of Sudoku two years ago. It is written in Japanese, but you can see some instances of 17-given problems found by computer programs [3][4][5]. A posting says the first 17-given problem appeared in the 185th (May 1997) or 187th (July 1997) issue of Puzzler. --Pitan 15:49, 27 May 2005 (UTC)

Gordon Royle lists a large number of 17-given problems on his site. --Jim Mayfield

I know at least a 16-given puzzle, which has only one solution (well I didn't prove that assertion, but the computer program I wrote reported only one solution).

+-----+-----+-----+
|3 - -|- - -|- 4 -|
|- - -|- 9 -|5 - -|
|- 6 -|1 - -|- - -|
+-----+-----+-----+
|- - -|- - -|- 1 -|
|- - 2|- - 8|- - -|
|- - -|5 - -|3 - -|
+-----+-----+-----+
|- - 1|- - -|- - -|
|2 - -|- - -|- 8 6|
|- - -|- 3 -|- - -|
+-----+-----+-----+

There are at least two solutions to that grid according to http://www.sudokusolver.co.uk/. - ZM Zotmeister 17:31, 6 September 2005 (UTC)

I gave up after counting 5,000,000! --angusj 23:15, 6 September 2005 (UTC)

Pronunciation

What is the correct pronunciation? I think read somewhere that it should be like "pseudo-coup" (sue-doe-koo) rather than sue-dock-oo ? Jooler 08:31, 19 May 2005 (UTC)

Yes, that's correct - it's in the Observer article linked to above. --OpenToppedBus 09:38, May 19, 2005 (UTC)

I never even thought about it - I studied enough Japanese to know the proper pronunciation intrinsically. If this isn't in the article already, I'll put it there; "pseudo-coup" is a perfect phoneme for it. ...In fact, if it weren't for the matching pronunciation, Pseudoku would be a great name for a variation of the puzzle. - ZM Zotmeister 18:46, 19 May 2005 (UTC)

Warning! That only works for American English. In British English "pseudo" is pronounced "syoodoh", not "soodo". - 23:07, 10 Jun 2005 (GMT)

I chopped the "e" from "doe" because it is a short "o". The "sue" (I prefer "suu") is long, the "do" is short, like "dot" without the "t", and the "ku" is short too. Jimbreen 11:13, 13 Jun 2005 (UTC)

Could a reader get confused and read "do" as "doo"? Unfortunately I don't know of a better way of spelling it. ian 21:00, 21 Jun 2005 (UTC)

Soo do'h ku'h ? Jooler 06:26, 22 Jun 2005 (UTC)

External links

Should these be trimmed a bit? A lot of it verges on link-spam. OpenToppedBus 12:17, May 24, 2005 (UTC)

I agree, but perhaps an interim measure would be to categorise the links. Poor quality links within each category could then be purged. JPF 13:00, 24 May 2005 (UTC)

I have attempted to categorize the links a bit better, based on how a Wikipedia reader might conceive of them, rather than the owners of the sites. -- 212.179.220.49 10:03, 14 Jun 2005 (UTC)

Mathematics of Sudoku

I have included a figure for the number of possible completed sudoku grids. Should I credit the programmer who derived this number? Link to the code that produced it? Link to the discussion that prompted the calculation?

Well I have credited the programmer and linked to the discussion.

I've removed the bit about 6,670,903,752,021,072,936,960 being "roughly the number of micrometers to the nearest star" on the grounds that it's 'only' about 2/3rds of light year (one light year = 9,460,730,472,580,800,000,000 micrometres) and a) the nearest star is only 8.3 light minutes away and b) the next nearest is over four light years away. Lovingboth 30 Aug 2005

Reference to Marriage Theorem

I can't understand the following sentence? What is the matching involved? I can't see what the connection is between Sudoku and the Marriage Theorem. Dillon256 16:18, 25 May 2005 (UTC)

The matching involved is related in principle to Hall's marriage theorem, in that the inductive method to prove Hall's theorem throws light on deductions to be made from any given set of restricted possibilities.

I've removed the sentence. Dillon256 13:17, 27 May 2005 (UTC)

Hmmm...

... funny. This seems to be a slightly more complex form of a test given to me as a psych evaluation for my current job. Oh, and I sucked at doing these :-) Ta bu shi da yu 06:45, 30 May 2005 (UTC)

Italics

What's with the italicisation? It's now entered English as a loanword, we don't need to italicise it. Unless we want to italicise Chess . . . Slac speak up! 05:35, 2 Jun 2005 (UTC)

I strongly disagree. The italics distinguish it as a title of a published work, thereby properly reporting the current usage of the term. We italicize (and capitalize) Sudoku and not chess for the same reason we emphasize Band-Aid brand adhesive bandages but not aspirin (which was once a registered trademark). It is not the place of the Wikipedia to declare such a title generic, especially when it is still a very much active copyright; just because the copyright is not in an English-language-native nation is no excuse. Even the original English name, Number Place, has remained unique to Dell for roughly three decades and has not become generic either. - ZM Zotmeister 18:53, 7 Jun 2005 (UTC)

I think you may mean trade mark rather than copyright: in the UK, at least, there are so many different people publishing Sudoku puzzles, I doubt they are all licensing the term from the same person, any more than you would need to license the term "crossword" or "acrostic". -- ALoan (Talk) 18:17, 10 Jun 2005 (UTC)

In Japan, Sudoku is a registered trademark, and an enforced one, held by Nikoli. Nikoli is now publishing their Sudoku puzzles in the UK, under the name Sudoku; although I don't know the precise legal details involved in their partnership with Puzzler Media, I think it is safe to say that Sudoku should not be assumed to be a generic term in any nation. Removing its italics would be as ignorant as someone now moving this whole article to Number Place (something I almost did, albeit before the flood gates opened... and something that would still make empirical sense to me). - ZM Zotmeister 20:46, 10 Jun 2005 (UTC)

LAtin squares

No mention of Sudoku as a special form of Latin square? GraemeLeggett 08:27, 10 Jun 2005 (UTC)

Strike that, small mention in middle of article. GraemeLeggett 08:34, 10 Jun 2005 (UTC)

What strange coincidence!!

Today, 2005-06-10, the Times of India, (Mumbai) introduced it in its main newspaper on page 17. yesterday the city was on the Featured Article.  =Nichalp (Talk)= 08:47, Jun 10, 2005 (UTC)

Don Knuth's Insights

The University of Oxford Computing Laboratory had a competition that involved writing a Sudoku solver. The email sent round afterward contained some insights by Don Knuth:

Don Knuth observed that the Sudoku problem is an instance of a class of exact cover problems that can be formulated in terms of Boolean matrices and solved by a backtracking procedure he calls "dancing links", using pointer manipulations to cover and uncover rows and columns of the matrix.

Knuth's observation is interesting because it reveals that a number of apparently important distinctions are actually artificial. A Sudoku problem can be solved by making a sequence of choices to place a digit in a square. Each choice must be consistent with the choices that have gone before it. The choices are of four kinds:

o  select a square (r, c) and fill it with an chosen digit d.
o  select a row r and a digit d and put d in a chosen place in row r.
o  select a column c and a digit d and put d in a chosen place in column c.
o  select a block b and a digit d and put d in a chosen place in block b.

In each case, the choice satisfies a constraint that each square must contain exactly one digit, or that each row, column or block must contain each digit exactly once.

Knuth's approach reformulates the problem in terms of finding an exact cover of a 729 x 324 Boolean matrix. The 324 columns correspond to the 4 x 81 constraints enumerated above, and each of the 729 rows corresponds to a move that puts one of the 9 digits in one of the 81 cells. Each row contains four 1's, corresponding to the way the move satisfies one constraint from each group. The problem becomes one of finding a subset of the rows that contains exactly one 1 in each column.

It's best always to select a constraint that has the smallest number of remaining possibilities. If that number is zero, then we have followed a dead end, and should backtrack. If the number is one, then we can definitely fill in a square, and there is no genuine choice. If it is more than one, then we can explore all the possibilities in a depth-first pattern.

This shows that the distinction between forced moves and arbitrary choices is artificial, since a forced move is just the special case where there is only one choice. Knuth's method also treats all four kinds of constraint uniformly, so that it can not only backtrack over all the digits that can fit in a square, but also over all the places that a given digit can be put into a row or column or block. This may not be necessary for Sudoku, but it does reveal a symmetry to the problem that is rather nice.

I'm not sure whether some or any of this has a place in the Main article.

Popularity in Newspapers section out of control

Sudoku: Popularity in newspapers has grown out of control. It takes up too much vertical space for so little content. This either needs to be cut or reorganized/condensed significantly. —thames 18:50, 10 Jun 2005 (UTC)

I would agree. The section could be reduced to describing how the phenomenon started (in the UK?) and has since propogated

Good job with condensing it! - ZM Zotmeister 20:47, 10 Jun 2005 (UTC)

Guess what - it's out of control again. At this point, do we really need to list every single newspaper in every single country that publishes these? Is that really the job of an encyclopedia? I'd leave the portion before the bulleted list that's there now alone, but I'm inclined to simply provide a rough count for the rest (which at this point would read "The puzzle is now printed in over fifty different publications in over twenty different countries."), which I think would be sufficient. Who agrees? - ZM Zotmeister 29 June 2005 20:47 (UTC)

I would be inclined to leave it for now. Firstly, it seems to be of continuing interest to readers who continue to add in another publication. It provides a sense of participation. Secondly, it may be regarded as data tracking the spread of a newspaper meme. Someone could use the original data to produce a diffusion map. However, I agree that the longer the list gets the more it clutters the page. Perhaps the answer is to create a spillover page which deals with the geography of Sudoku. JPF 30 June 2005 06:11 (UTC)

Excellent points, and well put. I can envision a "Sudoku Around The World" graphic, showing a map of the planet and colored areas showing where Sudoku is published... - ZM Zotmeister 1 July 2005 16:02 (UTC)

NP completeness

I corrected the section regarding the NP-completeness of the problem. In fact the problem on 9 x 9 boards is finite and so trivial to solve with a Turing machine in constant time and space by walking the game tree and looking for a valid solution which uses the givens. The practical problem is that this constant is very, very large. The same issue exists with Chess, Checkers, and Go. Deco 22:21, 10 Jun 2005 (UTC)

Meaning

The meaning is "the numbers must be single" or "the numbers must occur only once", as 138.217.20.56 correctly wrote; the translation by User:Che fox, "Numbers are only for Singles", which 213.162.124.40 reverted it to, is inaccurate, and claiming that 138.217.20.56's edits are "vandalism" is incorrect. See [6], in particular Jim Breen's comments.

I'm happy to go with Jim's translation ("the numbers must be single"), but remember that the phrase is a bit of a pun that can't quite be translated directly. 独身 is only used for "unmarried people" as far as I've seen it in usage in Japan (mostly on forms to indicate if one is married or not).

I believe the phrase has a double meaning: "the numbers must be single" (referring to the nature of the puzzle), and "[these] numbers are only for unmarried people" (since only they would have time to do this puzzle). To get the double meaning, the translation of 独身 as "singles" is much better then "must occur only once".

In any case, either translation is much better than the one I replaced (which was a nice bit of machine translation: "number is limited only single (unmarried)"). --Che Fox 15:12, 11 Jun 2005 (UTC)

Well, the construction "X wa Y ni kagiru" is often used for expressing his/, her favorite. For example, "Natsu (summer) wa biiru (beer) ni kagiru" means "In the summer, I like beer above all things." So the original title of Sudoku was certainly a pun, but the hidden meaning is (somewhat politically incorrect) "I prefer unmarried (women)". Anyway, I think "the numbers must be single" is an accurate translation. --Pitan 22:57, 12 Jun 2005 (UTC)

A very common common use of the "xxx ni kagiru" construction is to say something is limited in some way, e.g. "kaiinsuu wo 50 ni kagiru" meaning "the membership is limited to 50". BTW, I (Jim Breen) am the vandalistic 138.217.20.56 referred to above. I forgot to log in.

Repetitions

I'm not feeling brave enough to hack at a featured article but we have some duplications:

Para 1: "The aim of the puzzle is to enter a number from 1 through 9 in each cell of a grid, most frequently a 9×9 grid made up of 3×3 subgrids (called "regions"), starting with various numbers given in some cells (the "givens"). Each row, column and region must contain only one instance of each number."

Rules and term. 1st para: "The puzzle is most frequently a 9×9 grid made up of 3×3 subgrids (called "regions"). Some cells already contain numbers, known as "givens". The goal is to fill in the empty cells, one number in each, so that each column, row, and region contains the numbers 1 through 9 exactly once. Each number in the solution therefore occurs only once in each of three "directions", hence the "multiple isolations" implied by the puzzle's title."

History 3rd para: "He promoted the puzzle to The Times in Britain, which launched it on 12 November 2004. Three days later The Daily Mail began to publish the puzzle under the name "Codenumber"."

Pop. in newspapers 1st para: "The Times launched its regular Sudoku puzzle, introduced by Wayne Gould, on 12 November 2004. Three days later the Daily Mail began to publish the puzzle under the name "Codenumber"."

I think there was at least one more but I can't see them now. Secretlondon 08:55, 13 Jun 2005 (UTC)

Sudoku in Politiken?

The article states that Sudoku was introduced in the Danish newspaper Politiken yesterday. I can't seem to find a reference, though. Could someone provide one?

On a related note, Morgenavisen Jyllands-Posten, which is published by the same company, started bringing Sudokus today. --Pidgeot (t) (c) (e) 15:34, 13 Jun 2005 (UTC)

I can't find any references offhand, but they're on the back of section 1. And I'm going absolutely crazy over it. Maybe it's because I've been up for 24 hours, or maybe I've suddenly become daft, because I can't complete more than one number (for example get all 1s placed). After that I'm unable to figure out where to put anything else :) Mikkel 14:37, 20 Jun 2005 (UTC)

Well, that's good enough of a reference for me :). --Pidgeot (t) (c) (e) 17:19, 20 Jun 2005 (UTC)

Rocky Mountain News

On the article page, it lists international newspapers that contain sudoku, but no American ones. Well, I think the trend has come to America as the Rocky Mountain News (a Colorado newspaper) started including the puzzles as of June 11, a few days after the article appeared on the main Wikipedia page. Concidinence?...

Psychology of sudoku

Are there any views on why sudoku is so popular? Here are some suggestions:-

1. Self explanatory: it is easy to guess what to do merely by looking at the puzzle.
2. Convenient duration: the typical solving time corresponds to the duration of a commuter’s journey or a relaxation break.
3. Community: many other people are doing the puzzle providing a shared experience.
4. Mental activity: many people enjoy mental activities which led to a clear conclusion:
   1. Puzzle solving: of those people who enjoy mental activities, many have a natural desire to solve problems.
   2. Satisfaction: completing puzzle gives sense of satisfaction.
   3. Solving mental puzzles can be addictive.
5. Self-esteem: completing puzzle confirms intelligence and reinforces self-confidence.
   1. Self-deception: difficult puzzles are avoided, failed puzzles are ignored.
6. Egalitarian: solvers emphasise that a solution has been found rather the level of difficulty of the puzzle.
   1. The usually successful initial scanning process is not distinguished from the more difficult subsequent logical analysis process
7. Prizes: some newspapers offer prizes for completing the puzzle.

JPF 12:37, 15 Jun 2005 (UTC)

"Multiple Isolations"

Each number in the solution therefore occurs only once in each of three "directions", hence the "multiple isolations" implied by the puzzle's title.

I don't understand what this means -- could someone clarify? — Matt Crypto 14:11, 21 Jun 2005 (UTC)

Each number in a solved Sudoku grid is the only one of its kind in its row - it's isolated, all alone. It's also isolated in its column and isolated in its region. - ZM Zotmeister 15:53, 22 Jun 2005 (UTC)

Sorry, should have been more specific: I didn't understand the "multiple isolations" implied by the puzzle's title-bit. — Matt Crypto 21:55, 22 Jun 2005 (UTC)

That is a remnant of the wrong interpretation of the Japanese name, which was correctly deleted in this annonymous edit [7]. --Pitan 22:35, 22 Jun 2005 (UTC)

Are you sure "number" for "multiple" wasn't an intentional pun? - ZM Zotmeister 16:39, 23 Jun 2005 (UTC)

sū (数) never means "many" by itself, unlike the English expression "a number of". --Pitan 20:31, 23 Jun 2005 (UTC)

Computer solutions section is poor

This section discusses what Sudoku-solving computer programs "would do", and what kind of programs "can be designed". Why not instead discuss what they "can do" and what "has been designed"? As it stands, it looks liks someone's speculation (it may be well-founded, but I can't tell). Fredrik | talk 11:53, 22 Jun 2005 (UTC)

It's my work; I stand by its accuracy (download GNU Prolog, read the instructions on the FD constraint solver, and try it yourself if you don't believe me). I'll try to tighten it up. Solving a 9x9 properly-specified sudoku by computer is actually a fairly trivial problem and one, while I wouldn't inflict it on Introduction to Programming 101 students, I'd expect Algorithms 201 students to deal with in fairly short order. --Robert Merkel 15:04, 24 Jun 2005 (UTC)

I do not want to edit the main article, but it should be noticed that it is quite trivial to write a backtracking program which finds a solution within a few milliseconds on a modern home computer. It is enough to keep some simple auxiliary data structures (arrays) for each row, column and subgrid which mark values which were already used. I wrote such a program in C: the main function has about 40 non blank lines and it provides a solution for "hard" examples in less than 10 milliseconds. Tsferreira Sat Sep 17 20:21:44 UTC 2005.

sudoku

You should introduce Constraint Satisfaction Problem (CSP) and the heuristic used in it.

History

"In 1997, retired Hong Kong judge Wayne Gould, 59, a New Zealander, was enticed by seeing a partly completed puzzle in a Japanese bookshop. He went on to develop a computer program that spontaneously produces puzzles; this took over six years." - can we have a note on how on earth it took him as long as six years to do that?? Lovingboth 29 Jun 05

I thought it was on his website at one point, but I can't seem to find it there now. At any rate, I didn't add that to the article - does some one else remember (or can point to it online somewhere)? - ZM Zotmeister 29 June 2005 20:32 (UTC)

IIRC the thing which took most of the time was the code to work out how difficult a given puzzle is. Stills seems rather a long time, but I suppose he probably didn't have formal CS/maths training. --PT

Sudoku card game?!

From one of our reference links: "Sudoku has sprung up in newspapers from France to Slovakia, while a card game is sweeping American high schools." Card game?! I've been unable to find out anything more about this; can anyone point me to info on this? It may prove to be interesting to mention in the article, and would definitely be of personal interest to me either way. - ZM Zotmeister 1 July 2005 16:30 (UTC)

Sample puzzle replacement coming

I just noticed that it would appear the excellent sample puzzle on the article at this time is soon to be deleted (click on it). Shame - I really like the one there, but copyright is copyright, and as a puzzle constructor myself I certainly understand the concern. I'll volunteer to compose a proper replacement to be licensed under the GFDL. I can't guarantee it will be quite as difficult, but I should be able to present a decent challenge, and hey, it can stay. I should have it finished and posted within 24 hours (I'm on company time right now). - ZM Zotmeister 6 July 2005 17:46 (UTC)

Building sodoku boards

I've found a method to generate sudokus which is extremely easy, although I have not found any reference to it in the web. Please feel free to use it.Just mention it as the "Peraita method". That'll make my mother very happy...

1. Generate a random permutation of the 1-9 digits. Let's take 123456789. But 298413765, or any other, would be perfect.

2. Assume that the 9 3x3 "quadrants" are named Q11, Q12, Q13, Q21, etc. according to their row.column placement. Each cell of each quadrant (81 in total) can be named as Q11-11, Q11-12, Q11-13... Q33-31, Q33-32, Q33-33.

3. Fill Q11 with "123456789", left-to-right, top-to-bottom. Thus, Q11-11=1, Q11-33=9.

4. Rotate-left "123456789" by one position, obtaining "234567891". Fill Q21 with that sequence: i.e. Q21-11=2, Q21-33=1.

5. Rotate-left the last sequence again, you'll get "345678912". Fill Q31; Q31-11=3, Q31-33=2.

6. Repeat this process with all 9 quadrants, going top-to-bottom and left-to-right. At the end, Q33-11=9, Q33-33=8.

7. I call the above procedure the "seeding" of the board. No matter what permutation of 1-9 you start with, you'll get a "valid" final board.

8. In the board you've just built many 3-long letter combinations are repeated, i.e. it is a very "obvious" board. You'll have to "shuffle" it. There are a number of "isomorphic" (that maintain the shape) transformations that you can use. Simmetries around the first diagonal (going from Q11-11 to Q33-33), the second diagonal (Q13-13 to Q31-31), the vertical axis (Q12-12 to Q32-12) and the horizontal axis (Q21-21 to Q23-23) are "global" transformations and I call them D1, D2, A1 and A2 respectively. "Local" transformations consist of row or column swapping between two rows or columns belonging to one set of horizontal of vertical quadrants. Thus, columns 2 and 3 can be swapped, just as rows 4 and 6, for instance. All these transformations maintain the "validity" of the board. These "shuffling" transformations can be applied in any number, in any order. You can force digists to move to designated places.

9. Now, you've got it! A beautiful filled-up Sudoku puzzle.

BREAK: I have a couple of questions here: a. Can all valid sudoku boards be generated with the above algorithm? b. Excluding repetition of three digit sequences (i.e. 345 or 678 appearing in more than one place), are some of the generated solutions intrinsically easier/harder than others?

10. Aha!! Now comes the last process... That of transforming the solution into a problem. You'll do that by blanking ("prunning") some of the cells. But how many? When can you stop? How do you make sure you've not blanked one too many and created a multiple-solution problem? I'm still working on these issues. Any contribution will be welcome.

BTW: the above method works nicelly for boards of any n2 size.

Hi there. Wikipedia has a policy of No original research - Wikipedia is not intended to be the first place some new discovery or technique is published. If you want to discuss new techniques for solving and composing sudoku, one place where there is an active discussion is at the forums on http://www.sudoku.com. The discovery of the number of legal sudoku solutions came through discussion on those forums, for instance.

That said, one simple way of doing the "pruning" you describe in step 10 is to use a computer solver to check whether removing a cell makes the puzzle ambiguous. --Robert Merkel 01:35, 13 July 2005 (UTC)

External link explosion

This is a good article, but I'm concerned about the large number of external links given. Wikipedia is not a web directory, and external links are chosen to be representative, rather than exhaustive. Can I suggest we trim the list down to just two or three of the best links in each case? — Matt Crypto 01:06, 15 July 2005 (UTC)

I agree that Wikipedia is not a link directory but in the case of Sudoku, I think many of the viewers are looking for sites with the puzzles themselves. If action is taken to reduce the list, please don't remove the popular online gaming sites or the "Essential Links to Sudoku" which in turn links to many good sites. --Douglebert 18:04, 16 July 2005 (UTC)

Sure, but I think we need to decide which links are most useful, and lose most of the rest. We must easily have a hundred links in the "External Links" section (and that excludes the links in the "References" section) — that's well outside the norm for a Wikipedia article; I would think 10-15 ought to be plenty. One idea would be to link to directory sites, and then those sites can list every single newspaper with Sudoku, or the numerous solver software etc. — Matt Crypto 20:50, 16 July 2005 (UTC)

I agree with the suggestion to prune the extenal links, but the obvious difficulty is deciding the 'worthy' ones to stay. Is it possible to have an editorial board??? Also, those applications which *make* as well as solve puzzles should have a separate subsection. --59.167.32.112 04:51, 17 July 2005 (UTC)

Should we not split off the content which relates to media coverage - popularity in newspapers, list of newspapers covering sudoku, internet pages etc., into a separate "Sudoku in the media" page? There is no doubt this latter page would expand in a variety of new forms e.g. TV programmes. JPF 12:06, 17 July 2005 (UTC)

That sounds like a good idea to me, for one. Keeping all the information while housecleaning the main article sounds like the best of both worlds. - ZM Zotmeister 18:33, 17 July 2005 (UTC)

Most annoying are the obvious ad links like this one by 195.151.37.11 added under Solvers and helpers. Can I just rv this kind of edit by an anon with this being his first and only edit? hydnjo talk 16:13, 21 July 2005 (UTC)

Never mind, I just boldly rv'd the ad link. hydnjo talk 02:25, 22 July 2005 (UTC)

Help me, please ...

... to find the "given" numbers in the last two columns in the "difficult" sudoku which used to be atop the Sudoku page. Part of this puzzle remains in older editions of the page, in the example (in red and green) of how to solve these. I was working on it, and now it's disappeared, except for that partial reproduction. Thanks. I wanted to finish it on a flight tomorrow, to Canada to escape this dreadful D.C. heat. Sfahey 18:32, 22 July 2005 (UTC)

Which Daily Telegraph?

The Daily Telegraph owned by Nationwide News Pty Ltd is the Sydney, Australia one. But does anyone know for sure that it is this one that is meant, not the London one? Barnabypage 21:11, 22 July 2005 (UTC)

It clearly refers to the British Daily Telegraph in the second case (was rapidly introduced to several other national British newspapers including ...). It isn't obvious for the first reference (A three-dimensional Sudoku puzzle was invented by Dion Church ...). Hv 02:20, 17 August 2005 (UTC)

Article disposition problem

'Dell Number Place' is mentioned in the Construction section, but the reader will not know what that is, or why it is important, until the History section.

Um... looks like it's covered in the intro paragraph to me. - ZM Zotmeister 17:08, 26 July 2005 (UTC)

External link explosion 2

OK, I'm still worried about the large number of external links, particularly as this is a Featured Article and shouldn't have these problems. It seems to me, after watching this page, that various software authors come and add their particular Sudoku app to the list -- and, given that it looks like a link directory, why wouldn't they? I've moved the somewhat dry lists of newspapers featuring Sudoku to a separate article, List of newspapers featuring Sudoku. To be cheeky and stimulate discussion, I've moved the external links here — let's add just the good ones back. Remember folks, Wikipedia is not a link repository ;-) — Matt Crypto 23:28, 2 August 2005 (UTC)

The list is currently at Sudoku/Resources so there's no point having it here as well. --angusj 09:37, 9 August 2005 (UTC)

Popularity in the media

John, I think a very brief entry concerning the Sky One fiasco is of general interest in that it demonstrates very well that Sudoku can be badly constructed and consequently have multiple solutions. I just don't think that details of the TV show is of sufficient interest to be included here too. Of course, this is only my opinion so I'm happy to open it to debate for you and others to comment. --angusj 15:11, 13 August 2005 (UTC)

Angus, I personally find it interesting to see how sudoku (and other cerebral pastimes such as chess and bridge) are handled in the media - not just newspapers. To the extent that a TV programme has been attempted with little success then we have learned something. Perhaps there will be another TV format in the future which will strike a more fruitful vein. The fiasco was the puzzle on the hill rather than the programme itself. Media is concerned about formats rather than the content of a puzzle. JPF 22:59, 13 August 2005 (UTC)

Hi John. Yes, I agree the fiasco was the badly constructed 'puzzle on the hill', not the TV programme per se. I've come round to understanding and agreeing with your position that the TV programme is independantly of interest as Sudoku at that point entered a new media (even though from reports it was far from successful). Thanks for your patience, I'm happy to restore your original edit. --angusj 23:26, 13 August 2005 (UTC)

The sudoku carved in a hillside by Sky One (in its disastrous publicity stunt) has, I think, 1906 solutions, not 1905. See http://www.jw-stumpel.nl/sudoku Cyobiz 15:12, 15 August 2005 (UTC)

Well I'm very confident your solver is wrong - see http://www.setbb.com/phpbb/viewtopic.php?t=179&mforum=sudoku. (My Simple Sudoku Program also agrees with Simes that there are 1905 solutions.) --angusj 22:36, 15 August 2005 (UTC)

Yes indeed. I stand corrected. A bug was the cause.

Guessing never necessary?

Recent addition by an anon:

Although difficult at times, all puzzles can be solved without guessing numerical values.

That's not been my experience, and the Sudoku books I've read strongly imply that guessing is necessary for some tough puzzles. The statement is true in the strictest sense; for example, you could, in theory, build a large lookup table of Sudoku puzzles and simply look up the answer, but I don't think that's what's meant here. — Matt Crypto 13:41, 14 August 2005 (UTC)

Yes, I agree it is premature to claim that all puzzles can be solved without guess. --angusj 14:11, 14 August 2005 (UTC)

This reminds me of the anecdote of G.H.Hardy who left giving a lecture at Cambridge hesitating in mid thought only to return some time later to confirm that the point under consideration was indeed obvious. Sometimes it may be easier to take the guessing route than to think through an analytical solution. JPF 23:36, 14 August 2005 (UTC)

Sad, but true. There's what's deducible, and then there's what's reasonably deducible by a human. The complexity of a Sudoku puzzle can exceed that, even if it has a unique solution. Although any Sudoku with a unique solution can be solved through deduction alone, it is sometimes so tortuous [to use John Foley's word - I had actually meant 'torturous', by the way] that rolling out Ariadne's Thread actually becomes more efficient. So although the statement is true for properly-built puzzles, I agree that its absence is desirable. - ZM (Zotmeister 14:50, 17 August 2005 (UTC))

"Magic" Sudoku a triviality?

There seems to be some contention over whether the section on "magic Sudoku" is of any encyclopedic merit. My personal opinion is that this "discovery" is perfectly trivial - swapping the digits of a puzzle so that the lo shu appears in it is of negligible difficulty and of no particular value. I'm thinking it's self-aggrandization and am quite willing to delete the paragraph whole, but I'd like to see what others think of this. - ZM (Zotmeister 14:50, 17 August 2005 (UTC))

I agree, this is not sufficiently notable. — Matt Crypto 15:08, 17 August 2005 (UTC)

I also agree, not sufficiently noteworthy. --angusj 23:57, 17 August 2005 (UTC)

I've deleted it. If a sudden influx voting the other way arrives, it can be replaced easily enough. - ZM Zotmeister 14:35, 18 August 2005 (UTC)

The section on Construction contradicts itself.

"Dell Number Place puzzles are computer-generated... They also have no authoring credits."

"Dell Number Place Challenger puzzles also list author credits."

I would fix it, but I don't know which is correct :) Captbaritone 00:00, 18 August 2005 (UTC)

The first statement "computer-generated... have no authoring credits" is incorrect. The credits are directed to the copyright owner of the software that generates the puzzles. --angusj 23:52, 17 August 2005 (UTC)

I removed the "have no authoring credits" sentence. Captbaritone 00:22, 18 August 2005 (UTC)

Ahem: Number Place and Number Place Challenger, as noted in the Variants section, are NOT the same puzzle - there is no inherent contradiction. In addition, the article reads "credits", not "copyright notices" - the name of the constructor of an individual Number Place puzzle in a Dell magazine is NOT printed alongside the puzzle [presumably because it isn't a human]; the constructor of a Number Place Challenger IS. What is meant is clear from the context of the rest of the section, which mentions Nikoli's listing of the author's name beside each puzzle. I am reverting that edit. - ZM Zotmeister 14:22, 18 August 2005 (UTC)

I'm not really fussed either way but I would consider a copyright notice a form of credit too, but it also has other legal meanings. --angusj 23:28, 18 August 2005 (UTC)

What exactly is the difference beteen Number Place and Number place Challenger? and perhaps this difference could be pointed out in this section to avoide confusion. Thanks for your input. Captbaritone 01:06, 19 August 2005 (UTC)

The difference is detailed under Variants, as I just said. Article redundancy is frowned upon, but I can add "(see Variants)" after "Number Place Challenger" in the Construction section. - ZM Zotmeister 15:45, 19 August 2005 (UTC)

Faster than a computer ??

A recent anonymous addition to the Introduction section says:

The strange thing is that the human mind may be sometime faster than computer software when a very hard SuDoku have to be solved.

I really doubt that this is true, but I don't feel certain enough to revert this addition. AFAIK, human methods of solving Sudoku puzzles are all deductive and can be easily directly implemented in a computer programme, which can then perform the operations much faster. There is little or no gestalt or inductive reasoning involved. In other words, I think solving a Sudoku puzzle is more akin to doing arithmetic than it is to playing chess (note this is not a value judgement). Any comments ? Gandalf61 11:17, August 27, 2005 (UTC)

I agree it's incorrect. I've removed that sentence from the article. --angusj 11:28, 27 August 2005 (UTC)

This is definitely incorrect. In the ongoing discussion on the Sudoku Programmers Forum on List of Hard Sudokus, the longest solution time found was 5.27 milliseconds. As far as examples I can personally attest to - while my computer is not the fastest (867 MHz), nor the program I use (Sudoku Susser) noted for speed, the hardest puzzle on Vegard's site takes 0.552 seconds by brute force, or 13 seconds by deductive methods. I don't think human neural transmission is fast enough to beat the brute solver times. RAFowell

Alphabetical variations

Can I suggest some clarification and attribution for the alphabetical variations section: "Sudoku Word" is the term used by Knight Features, and their puzzles do not feature a diagonal word. (Nor, indeed are the letters used given "underneath", in fact they are given above the puzzle, see http://www.knightfeatures.com/KFWeb/content/features/kffeatures/puzzlesandcrosswords/KF/Sudoko/sudoku_word.html) "Wordoku" is the term coined by Top Notch Sudoku (http://sudoku.top-notch.co.uk/wordoku.asp); the section as it stands is an accurate description of their puzzle. Godoku is indeed the Guardian's term for alphabetical puzzles, but I've never seen an example and am not sure if it has the Knight Features or Top Notch format (I suspect it's the former, if they are like the "godoku" seen at http://exepose.ex.ac.uk/pages_2005/week24/011%20-%20Features.pdf)

Perhaps also noteworthy is the "Code-Doku" devised by Steve Schaefer (http://www.mathrec.org/hiddenmessage.html) which has an entire sentence embedded into the puzzle, and possibly Top Notch's "super-wordoku" which embeds two 9-letter words, one on each diagonal. It is debateable as to whether the "super-wordoku" and some (but not all) of the "code-dokus" are true sudoku puzzles, as (by design) they cannot be solved entirely by sudoku logic, and the solver must rely on deducing the embedded words. Top Notch claim this as a feature designed to defeat solver programs.