×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

The Godfather of Sudoku

Zonk posted more than 7 years ago | from the brain-twisting- dept.

Puzzle Games (Games) 47

circletimessquare writes "The New York Times profiles 55 year old Maki Kaji who runs Nikoli, in its article Inside Japan's Puzzle Palace. Nikoli is a puzzle publisher that prides itself on 'a kind of democratization of puzzle invention. The company itself does not actually create many new puzzles — an American invented an earlier version of sudoku, for example. Instead, Nikoli provides a forum for testing and perfecting them.' Also notable is how Mr. Kaji describes how he did not get the trademark for Sudoku in the United States before it was too late. But reminiscent of a theme many Slashdotters will find familiar about intellectual property: 'In hindsight, though, he now thinks that oversight was a brilliant mistake. The fact that no one controlled sudoku's intellectual property rights let the game's popularity grow unfettered, Mr. Kaji says.' Will Nikoli be the source of the next big puzzle fad after Sudoku?"

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

47 comments

Next Big Thing? (1)

Aladrin (926209) | more than 7 years ago | (#18451571)

"Will Nikoli be the source of the next big puzzle fad after Sudoku?"

I dunno, be he found the right place to Slashvertise, if he has it ready. (According to him, he has hundreds ready. I kind of hope he manages to get other logic puzzles popular as well.)

Sudoku Solvers (4, Funny)

Nymz (905908) | more than 7 years ago | (#18451711)

Rather than solving Sudokus manually, I wonder how many Slashdotters have programmed their own solver, and in what languages?

Re:Sudoku Solvers (1)

nebaz (453974) | more than 7 years ago | (#18451903)

Solvers are easy, I wrote one in about 3 hours in Java. (For each square, see what permissible values it has, and try to fill things in, brute force). What is more interesting is generation. How do you know that the puzzle you've come up with has a unique solution? With a complete solution in mind, which squares can (should) you remove. That seems harder to me.

Re:Sudoku Solvers (5, Interesting)

white_owl (134394) | more than 7 years ago | (#18453155)

Actually a generator which will generate puzzles at a given level of difficulty is not too hard if you organize the solver as a rule based system (Rule 1: first look to see if there is a square that only allows one number; Rule 2: look for pair of numbers that must exist in a pair of cells{sometimes called hidden pairs} . . . )

After you create the rules that will solve the puzzles you categorize the rules as easy, medium or hard.

Now if you want to create an easy puzzle you start randomly adding in (legal) numbers and each time you try to solve it using only the easy rules. The first time the solving part of the program solves the puzzle you are done. Alternatively you can start with a completed puzzle and remove a number and see if the number you removed is recoverable with the level of rules (easy, medium, hard) that you choose for the final puzzle.

Re:Sudoku Solvers (1)

maxume (22995) | more than 7 years ago | (#18451907)

Or just read the devastation of it:

http://norvig.com/sudoku.html [norvig.com]

Re:Sudoku Solvers (1)

To The Lighthouse (1041682) | more than 7 years ago | (#18454867)

Norvig clearly shows how to combine constraints and search to write a solver. More interesting though is to write a solver that imitates the way people solve sudoku. Such a solver can be used for example to rate the difficulty of a puzzle, something a solver that does brute-force search can never do accurately. [To answer the parent question: Perl.]

Re:Sudoku Solvers (1)

Dan Hayes (212400) | more than 7 years ago | (#18456139)

I did this in C# and it wasn't too tricky - trying to write one for Killer sudokus though was a lot harder and I got distracted by something shiny partway through dealing with endless sets :)

Re:Sudoku Solvers (1)

twistedsymphony (956982) | more than 7 years ago | (#18458419)

you should pop your code over into Microsoft's Visual Studio express and get it published on Xbox Live Arcade. I'd love a Sudoku game on XBLA.

I tried making one myself but I'm not really a programmer (it's just a hobby) and while I got a really basic brute force solver done it was ugly and not optimized very well.

Re:Sudoku Solvers (1)

maxume (22995) | more than 7 years ago | (#18456675)

I think of the puzzles as existing on a 'length to solve' or 'involvement' scale. The more a human acts like a computer, the faster they can solve them; more interesting games tend to work the other way.

Re:Sudoku Solvers (1)

warewolfe (877477) | more than 7 years ago | (#18452143)

I made a webpage (for practice)http://www.claritycode.co.nz/Sudoku.php [claritycode.co.nz] that solves sudoko puzzles. It validates in javascript and solves in php. However if the puzzle takes too long to solve the server blanks out.I'm currently writing another version in javascript to get around this. After that I'll try Perl and Java.

If I run it as a straight php script thru the cmdline the algorithm works okay.

Any tips for optimising server side php?

Re:Sudoku Solvers (0)

Anonymous Coward | more than 7 years ago | (#18452283)

Increase max execution time in php.ini? :P

Re:Sudoku Solvers (3, Informative)

Sigma 7 (266129) | more than 7 years ago | (#18452367)

If I run it as a straight php script thru the cmdline the algorithm works okay.

Any tips for optimising server side php?


It might not work, as some sudokus are extremely devilish. Instead of trying to solve it in one batch, try breaking it down into steps (e.g. have the script partly solve the system rather than having the server time the script out.)

An example is the implementation at http://www.scanraid.com/sudoku.htm [scanraid.com] - although this is slower since it takes step-by-step very literally.

Re:Sudoku Solvers (2, Interesting)

warewolfe (877477) | more than 7 years ago | (#18452889)

It's a brute force algorithm using recursive functions on a 3D array. (It seemed like a good idea at the time) but it doesn't lend itself well to stopping halfway through as it can't declare any additional numbers are right until the puzzle is solved in it's entirety.

Unlike a logical approach which could solve Sudoku puzzle in a piecemeal fashion.

To half solve a puzzle and give the user the chance to restart again to prevent the server timing out the page would require transferring the original state, the current state and the information on how it got there.

The interesting thing is, on some test puzzles that were marked difficult it took remarkably few recursions to solve while some that were marked simple took a lot longer.

Difficulty Rating (2, Informative)

Nymz (905908) | more than 7 years ago | (#18453043)

The interesting thing is, on some test puzzles that were marked difficult it took remarkably few recursions to solve while some that were marked simple took a lot longer.

That makes sense, as ratings are based on difficulty for a human to solve.

A difficult Sudoku might involve identifing a complex relationship in order to solve it logically, without guessing. Where as a simple Sudoku might involve only identifing simple logical relationships, but may have numerous possibilities that would increase the time of a brute force technique.

Re:Sudoku Solvers (1)

Chrax (782154) | more than 7 years ago | (#18452743)

A few months back, I got a working first shot in Python. I tested it with puzzles from counttonine.com, and it will solve up to medium, but tends to crap out on a hard or expert one. I haven't had another of that sort of insomniatic nights since, so I haven't figured out exactly why it sometimes doesn't work.

Re:Sudoku Solvers (0)

Anonymous Coward | more than 7 years ago | (#18452807)

Since you asked, my puzzle solvers are mostly written in OCAML (or Java when I wanted a GUI).

Re:Sudoku Solvers (1)

GrumpySimon (707671) | more than 7 years ago | (#18453173)

I was addicted to them for a few months, and eventually wrote a solver in PHP [simon.net.nz] . Haven't done one since. However, the best solver I've seen solves them with regexes [abigail.be] . Regex ninjas scare the hell out of me.

Re:Sudoku Solvers (1)

twistedsymphony (956982) | more than 7 years ago | (#18458603)

holy freekin crap. I have a hard enough time warping my head around that stuff for basic mod rewrites in apache. ... scary ninjas indeed.

Re:Sudoku Solvers (0)

Anonymous Coward | more than 7 years ago | (#18453653)

I created a spreadsheet that works in Excel and OpenOffice.org Calc, it doesn't use macros, just cell formulas.

Re:Sudoku Solvers (3, Interesting)

Bronster (13157) | more than 7 years ago | (#18453991)

Yeah, I wrote one in Perl. Also one for Kakuro.

My Perl sudoku solver was probably more complete - it even does set analysis: [A, B, C] are blank, values [2, 5, 7] are available, but A can only be [5, 7], B can only be [5, 7] so C must be 2.

It reverts to brute force only where its algorithms can't find any possible moves. I've only found that to be the case for puzzles with more than one legal solution (crappy cheap books).

Kakuro is more interesting - first the format is a cow to transcribe to a data file. I'm using "X Y DIRN LEN SUM" as the format. Output is a HTML file because plaintext doesn't quite read easily (my sudoku solver just outputs ASCII art).

The solver itself actually turned out to be very easy to write, and I get the feeling that it's not even complete yet (there are things I can do by hand that it doesn't attempt) and yet every puzzle I've thrown at it solves fine. It doesn't have a brute-force mode. I suspect this may be because either the kakuro book I'm using isn't very advanced, or it's just not so popular yet that people have crafted difficult puzzles.

What I'd really love to see is a standard data file format for describing these puzzles so I can share them and/or use other peoples' puzzles as input to my scripts. But I don't have THAT much free time, really... ;)

File Format (1)

Nymz (905908) | more than 7 years ago | (#18456079)

What I'd really love to see is a standard data file format for describing these puzzles so I can share them and/or use other peoples' puzzles as input to my scripts. But I don't have THAT much free time, really... ;)

My solver uses a simple XML format, so that it could easily grow elements for any future features, without obsoleting older sudoku collections. But I think I prefer doing the pen-and-paper format of daily papers. :)

Re:File Format (1)

Bronster (13157) | more than 7 years ago | (#18456535)

Mine uses plain text, 9 rows in which _ is an empty square, a number is a number, everything else is formatting gunk. Easy enough to write by hand, looks readable

_ _ 1 | 3 4 5
_ 2 3 | _ _ 7
7 _ _ | 9 _ 8 ...

But yeah, harder to do that sort of thing for some other puzzles.

Re:Sudoku Solvers (1)

OglinTatas (710589) | more than 7 years ago | (#18457505)

I wrote a puzzle solver too, but instead of having it brute force a solution, it stops at an impasse.
It is THOSE puzzles that are interesting. Is there something I can learn by studying the pattern? sometimes I figure out a new trick to add to my bag of sudoku solving techniques. Many times I have to resort to a parallel solution, i.e. if a box with two possibilities, if I set it as one or the other and proceed to solve, which boxes then resolve to the same number, or which boxes have the same number eliminated? I am not insightful enough to recognize those patterns yet.
If the tool solves the puzzle all the way through, I don't bother solving it myself.

Re:Sudoku Solvers (1)

Bronster (13157) | more than 7 years ago | (#18469187)

That's fine if your puzzle source is guaranteed to give one possible solution, as opposed to multiple possible solutions in which case you're wasting your time on an inferior sudoku source.

That said - if _my_ solver couldn't solve past that point, I would figure out why not and encode the logic I used into it. The challenge is understanding the puzzle well enough to describe it to a computer.

By the way - you might realise that you're describing brute-forcing (Many times I have to resort to a parallel solution, i.e. if a box with two possibilities, if I set it as one or the other and proceed to solve) as my solver implements it. If you reach a point where no rules can find a move, then split the board into two copies and make a speculative change in each one.

Re:Sudoku Solvers - Prolog (1)

robthebob (742982) | more than 7 years ago | (#18455665)

Prolog has got to be the way forward here. With the Eclipse constraint libraries I programmed a solver in about 10 lines. All I had to do was specify the constraints on rows (all_different and sum_to(45)) columns and squares.

Example problems (1)

Sigma 7 (266129) | more than 7 years ago | (#18451777)

I tried the example problems on the webpage. I had to use MSPaint, as the interface given does not support "pencil" marks and automatically assume that you are directly building the finished product.

Binary Sudoku (2, Funny)

camperdave (969942) | more than 7 years ago | (#18453491)

The following is a Binary Sudoku with a "difficult" rating:
1|.
-+-
.|.


Good Luck!

Re:Binary Sudoku (1)

Bronster (13157) | more than 7 years ago | (#18454011)

Has no solution in which all blocks contain all possible values. You could do one with 2x2 (1234), but that's pretty trivial.

Re:Binary Sudoku (1, Informative)

Anonymous Coward | more than 7 years ago | (#18456117)

Unless I'm reading it wrong, it is 2x2, and that's the joke. Vertical and horizontal lines delineate the cell borders.

Re:Binary Sudoku (1)

twistedsymphony (956982) | more than 7 years ago | (#18458867)

Unless I'm reading it wrong, it is 2x2, and that's the joke. Vertical and horizontal lines delineate the cell borders.
The GP is correct... each "cell" would only contain a 1 or a 0... when to be a Sudoku puzzle each cell would need to contain a 1 AND a 0.

A good rule of thumb is that you cannot have a sodoku puzzle unless you can take the square root of the number of elements in a cell and come out with a whole number: 2x2 (1-4) is the smallest valid possibility (though you could argue a 1 cell Sodoku is valid also). followed by traditional puzzles of 3x3 (1-9). What would be fun and interesting is a hexadecimal puzzle 4x4 (0-F). IIRC they call those "Super Sodokus". Binary doesn't work because you want 2 elements in each cell a 2x2 implies that there are 4 elements... but that's not binary.

I get that it was a joke, though they tend to loose their humor if the reader is required reduce their level of understanding to get it.

nikoli.com (3, Insightful)

aclayton (682343) | more than 7 years ago | (#18455155)

The article only mentions Nikoli's book-related site [nikoli.co.jp] , which is limited to quick introductions to a few of the puzzle types and a way to order their books. The books are beautiful, with top-notch puzzles printed on high-quality paper, but the international shipping rates make it a somewhat expensive leap of faith for someone new to these puzzles.

A better choice is Nikoli's online puzzle site [nikoli.com] , which is linked from their site mentioned above, but it might be easy to miss as it's not featured very well in that uncharacteristically ugly site design. There they publish 3-4 puzzles per day out of 7 different types, sizes, and varying levels of difficulty, for a monthly subscription of around $4. Nonsubscribers can play a few of each type to try out the solving interfaces, which use Flash and are far better than the ones in the NYT article. They support pencil markings, "try" modes, unlimited undo steps, partial checking, etc. What's not obvious from the nonsubscriber page is that it saves your solving histories and times for each puzzle, and you can see how you stack up to all the other subscribers. Also, you can replay your solve (with speedup/step options) to watch how you did it, or more interestingly, watch how other people did it, to expand your arsenal of techniques. You can write comments for each puzzle and read through others', but unfortunately for me most comments are in Japanese, I'm hoping the gaijin population there continues to grow..

The variety of constructing styles and solving methods possible in puzzles like Slitherlink, Nurikabe, and Heyawake is far greater than in Sudoku, where it's often impossible to discern whether a puzzle was human-generated (i.e. Nikoli) or computer-generated (i.e. almost everything in newspapers and those bookshelves stuffed with books crapped out by every publisher trying to cash in). So for those who may have tired of relatively repetitive Sudoku solving, I recommend giving these other more elegant and interesting puzzle types a spin.

I'm not affiliated with Nikoli, just an addicted subscriber for several years, and purchaser of many of their books. Trying to spread the word, as on one hand I'm happy to see logic puzzles like Sudoku increasing in popularity, but on the other hand I worry about high-quality puzzles getting buried by all the cash-in crud..

Nikoli didn't make Sudoku. (1, Redundant)

kinglink (195330) | more than 7 years ago | (#18459567)

Howard Garns did, he published in magazines, it was called Number puzzle. The earliest found copies are 1976, almost 9 years BEFORE nikoli even published a "sudoku puzzle"

The difference between number puzzle and sudoku is.... the name, it's 100 percent the same, same rules, same game.

It's doubtful that "kakuro" is even Nikoli's either, that was another invention first found in american culture in the same magazines as number puzzle. That was called Cross Sums.

But then again why am I expecting a massive news publication like the New York Times to do a little research about these topics before announcing them. It's not like they are nationally read.

Re:Nikoli didn't make Sudoku. (1)

The-Bus (138060) | more than 7 years ago | (#18460535)

Did you read the article?

"The company itself does not actually create many new puzzles -- an American invented an earlier version of sudoku, for example."

Re:Nikoli didn't make Sudoku. (1)

kinglink (195330) | more than 7 years ago | (#18461685)

Funny the article also claims Nikoli to be the godfather of sudoku? They are more like the taxi driver.

"Try your hand at three different puzzles from Nikoli, a company run by the self-proclaimed godfather of sudoku,"

Why is it that Garms isn't mentioned at all in the article. It's not hard to mention the founder of these puzzles that Nikoli appropriated. The obvious point is it's shabby journalism to call them the godfather and not clairify what they mean. An American invented the puzzle? So does that mean he's not worthy of mention, is Cross sums more worthy because Nikoli took it from someone else? Are logic puzzles worthless because Nikoli doesn't print them? These simple facts just prove that the article is a fluff piece at best.

Feel free to be lead around by the nose, but I demand a better level of journalism from a "newspaper of record"

Re:Nikoli didn't make Sudoku. (1)

The-Bus (138060) | more than 6 years ago | (#18479047)

The New York Times did not proclaim him the godfather of sudoku. Maki Kaji proclaimed himself the godfather; Nikoli is not a person, it's the company. And godfather doesn't necessarily mean creator or originator. It means sponsor, or someone who brought something to wide acclaim and recognition. Kaji has the right to give himself that title if he wants, although it belongs to Wayne Gould just as much (who brought Sudoku to the UK).

That you're making a tempest out of a teacup is an understatement.

Re:Nikoli didn't make Sudoku. (0)

Anonymous Coward | more than 7 years ago | (#18460537)

But then again why am I expecting a massive news publication like the New York Times to do a little research about these topics before announcing them. It's not like they are nationally read.
From TFA & Summary:
"The company itself does not actually create many new puzzles -- an American invented an earlier version of sudoku, for example."

But then again, why am I expecting a troll to do a little research about these topics before ranting? It's not like they can read.

Re:Nikoli didn't make Sudoku. (0)

Anonymous Coward | more than 7 years ago | (#18460569)

So, did you you miss that part where he said that an American invented the puzzle?
  Or the part where he said that they didn't invent most of their puzzles, they just perfect and "democraticize" them? I know people don't read the article, but at least read the summary.

Also, to be technical sudoku's must have a rotational symmetry, whereas the Dell Number Puzzles did not.

I hope so... (1)

Thedalek (473015) | more than 7 years ago | (#18460175)

Like most people who became enamored with Sudoku, I've grown weary of its overexposure. I don't know the exact point at which Sudoku became completely played-out, but Spongebob Squarepants Sudoku [booksamillion.com] would probably be well past that point.

Sudoku was fun, but the majority of the fun with any of these puzzles for me was figuring out solution methods for myself. Sudoku is now so heavily documented as to be trivial to solve, even at the highest difficulty levels (Especially if you have the patience to try Bowman's Bingo).

After getting burned out on Sudoku, I found out about Nikoli, and the other myriad puzzles they publish. At first I started with Hashiwokakero, then quickly moved on to Heyawake, Nurikabe, Hitori, Akari, Ripple Effect, Masyu, and even some not listed on the English version of Nikoli's website (Kin Kon Kan is particularly fun, once you figure out the rules).

In that time, I've ordered several books from Nikoli's website, traded for books with occasional Japanese acquaintances, and hunted Japanese auction sites for out of print editions. In short, it's expensive and time consuming to feed my language-independent logic puzzle habit. I'd be very happy if some stateside publisher would put out a magazine akin to Nikoli's "Puzzle Communication", or a compilation of new puzzles. I've seen a few books featuring other Nikoli puzzle types, but they do not feature more than 3 or 4 different puzzle types. Games magazine's puzzle magazines frequently feature Nurikabe and Slither Link, but only 2-5 puzzles per issue. What I want is variety and volume. Lots of different puzzles, lots of instances of each.

By the way, those with the ability/desire to import Japanese video games might want to check out Puzzle Series [play-asia.com] for the Nintendo DS. Volume 5 is Slither Link, Volume 6 is Illust Logic (Known to many as Picross, Nonograms, Edel, or Paint by Numbers), Volume 10 is Hitori, Volume 11 is Nurikabe, and Volume 12 is Akari (Light Up). You may also want to check out Simon Tatham's Portable Puzzle Collection [greenend.org.uk] . NetGame is particularly interesting.

And of course, no discussion of grid-based, wordless logic puzzles is complete without a mention of Solitaire Battleships, which currently cruises under the radar with the name Yubotu [amazon.com] .

Check for New Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...