The Godfather of Sudoku

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?"

Comments

Godfather?

[FlyByPC]

Well, he does make a puzzle I can't refuse...

Nikolai

[rlbond86]

Nikolai makes my favorite type of puzzles, Nurikabe. Hopefully those will pick up in the US too.

Re:Nikolai

[MagicM]

I hate you now. Thank you.

Ku?

[pluther]

What is ku, and why is he running it as root?

Sudoku Solvers

[Nymz]

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

Re:Sudoku Solvers

[Sigma 7]

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 - although this is slower since it takes step-by-step very literally.

Re:Sudoku Solvers

[warewolfe]

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.

Re:Sudoku Solvers

[white_owl]

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

[Bronster]

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... ;)

Difficulty Rating

[Nymz]

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.

Binary Sudoku

[camperdave]

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

Good Luck!

nikoli.com

[aclayton]

The article only mentions Nikoli's book-related site, 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, 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..

Re:Nikoli didn't make Sudoku.

[Alzheimers]

James Brown didn't invent soul, either.