davidbau.com

This isn't actually how you solve Sudokus when you're doing them by hand, is it? I have one Sudoku book where the instructions say that the "hard" puzzles require guessing and backtracking, and another one which says "you should never need to guess". The puzzles in the "no guessing" book are still very hard, but I find them much more fun to solve... I suppose the answer is to extend your simple solver to have some more sophisticated strategies before it starts to guess. (and then perhaps the rating could be based on some subjective ranking of the difficulties of the strategies the solver ends up needing to use?)

You are right. When you play Sudoku by hand, you basically never guess - instead you try to look ahead and then just write numbers when you are absolutely sure. Maybe it's like a breadthfirst versus a depthfirst search.

Even though the computer's depthfirst strategy is plenty fast for solving puzzles, I'm not sure it's the best way to rate the difficulty of a puzzle. There are pretty simple Sudoku strategies that my algorithm does not know.

But I am also running into the opposite problem: apparently the algorithm finds it easy to deduce squares (without guessing) that I find it very difficult to locate. I have been stuck on a particular "Level 0" board all morning, wondering where the heck the computer saw a simple deduction. I am not sure why it is so hard for me to see what I am missing.

Any ideas on the right way to rate difficulty?

I also did a small development in Excel to solve the first part of a puzzle, which is the "guessing" of all possible figures in each cell, following the three basic rules: Nine different figures on each row, column and 3x3 matrix.

After that, the real "guessing" process becomes very enjoying and takes much less of our relaxing time per puzzle (5 minutes for an easy puzzle is the average for an average IQ user).

The next step is to get an automatic figures generator with difficulty choice inside the worksheet using script, to avoid typing every new puzzle.

After reading you article I realized that possibly you have the right solution for my intent.

If you accept doing me such please, I would like to send you my worksheet to enable a better understanding of my idea. (Some writings are in Portuguese but I think this will not be a concern).

I believe that the worksheet engine (formulas) will be automatically translated to English inside your Excel.

Thank you

Valerio

You should never need to guess. You can create a true solver in Excel, but as it is an iterative process (which is not Excel's strong suit) it becomes a very intensive application. Better is to set it up in MATLAB. As long as you watch out for the possiblity of an endless loop you can create a solver pretty quickly.

Either way, the algorithm goes like this:
1. Create a blank puzzle for each number 1-9.
2. For each space, indicate whether it is the number, an open space, or filled with some other number.
3. For all of the open spaces, determine if it can be filled by the number (others get treated as if they were filled with some other number).
4. Check if it is the only eligible space in the row/column/square. If so, fill it.

Repeat these steps enough times and any solvable sudoku will be solved. That is to say, I have not yet found a published puzzle that could not be solved in this manner.

i didn't see the steps algorithm of saving sudoku
i really want to see it

thank you

Valerio Deo's solution is not quite right.
Since Sudoku is an NP-hard problem you will always run into problems if you are using a fixed rule set (i.e. rules that "look ahead" only a fixed number of steps), at least when you're incresing the Sudoku size (to 16x16 or even more)
The described algorithm even runs into problems for harder 9x9 instances:
There often are situations where there is not only one eligible space for a number.

Whey you say "You don't have to guess" you really mean you should not write down guesses. Thinking about what number would fit is nothing but making a lot of guesses in your head and looking whether they will lead to a conflict...

I know a better way to generator:

1. get a valid one like:
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

2. then randomly switch two lines(row) in a group or switch two big groups.

3. randomly switch all positions for two numbers, like switch all 1 and 2
Actually you can do the step 3 before step 1.

Now you have a valid solution, you just need to get rid of number from it to create a sudoku.

Nice programming that you have here.

There is another strategy I have found, which I use for hard sudoku's on paper. Once you have worked out all the possibilities for each uncertain cell, look for a (row/column/block) that contains (2/3/4/5/6/7) different possibilities for the same number of cells in that row/column/block. Eliminate ALL of these options from all OTHER cells in that row/column/block.

For example, if you have 3 cells in the same row, empty, which have the possibilities of:
(3,4,5)(3,4)(3,4), then the last two of those cells must contain 3 and 4 (in no particular order), and so the first cannot contain either 3 or 4, and so must be 5.

Hi, can somebody give me an efficient algorithm to develop a Sudoku Software where in a problem is generated automatically and asks player solve it..

Hi, i need help coding a sudoku generator and solution checker, which also provides a gui that allows the user to input numbers into the puzzle, check their input, and generate a new puzzle at any time, using a neural network and random number generators.

Good algorithm, David.

I wrote a sudoku solver some time back that employs a few techniques: looking for cells with unique candidates, looking for the only position for a value along a row, column, or block. I also added another technique that looks at subcolumns within a block and comparing to other subcolumns. These techniques seemed to be able to solve all the puzzles from local newspapers, but that's only because thos puzzles were pretty simple.

I found Stephen Ostermiller's source code (http://ostermiller.org) and realzed there are more techniques.

In addition to the ones he implemented, there are others such as X-wing and sword fish, and probably many more.

I believe it can probably be proven (or maybe it is already proven) that as long as the solution to a sudoku puzzle is guaranteed to be unique, there must be a logical series of steps that one can take to solve the puzzle. These steps which may include really complex technqiues -- even ones that have not even been discovered.

Using algorithms that make guesses is probably just a shortcut for not having to develop and implement complex techniques. But if you implement as many of the known techniques as possible, it would help make the generator more likely to generate a harder puzzle.

Anyone here that has a Pascal or a C version of this generating algorithm? Cause I don't know Python and I don't understand the code. If you have one, please email me at emma_k89@yahoo.com. And, one more thing: I don't know Java either. I'm pretty young:)

well,i think algo from shawn would b the best to generate new random sudoku's........wen u hav nothin.......and solver from david dated 28 dec,2007 is the best 1......but further isn't there any method 2 generate new sudoku's from a blank board.......i tried it this way.....first a generator which puts fixed no of random nos at random positions....follwoing possible conflicts.....then a solver which would solve this......if solver could solve it ...it's a valid sudoku.......else generator is called which generates a new sudoku from scratch.......but this gets quite typical for comp as it does guess work........can't there sum logical sol to this

Good stuff David, thanks. I wrote an solver in Excel VBA a few years back that employed a few different logical rules. It was pretty effective but could not solve the "brute force" type so recently I wrote a very simple smalltalk version that works very much the same way as your approach. I've been meaning to get around to writing a sudoku generator and this has now inspired me to get on with it!

David -

I wrote a solver that uses brute force, not 'logic', based on the fact that there are only 46,656 (9x6x3x6x4x2x3x2) possible patterns of one number in a 9x9 puzzle. Just generate all of them, eliminate those for each number that are not consistent with the positions of that number, then successively merge non-conflicting patterns across numbers. Requires no look-ahead/backtracking, just match/eliminate. Has 217 lines of Ruby code, and will solve 'hard' puzzles in about 30 seconds on my 5 year old PC.

Interesting stuff here.
What I've been wondering lately is if there is some way to generate completed sudoku puzzles from scratch. In other words a way to create a two dimensional array (9*9) which would contain the data from a completed sudoku.
Sky's way souunds alright for my purposes, but I was wondering if you could make one from scratch.
Thanks guys.

http://www.setbb.com/phpbb/viewtopic.php?t=314&mforum=sudoku

Seems like a good thread on generating random sudoku puzzles

I have been reading on the subject and from what i have hear you can use the dancing links (DLX) algorithm I have used this to salve the N Queens problem but never sudoku. I think it will work though it uses linked lists.

"But if you read the advertisements for Sudoku Gridmaster for DS, you will notice that it is said to come with "over 400" Sudoku puzzles. With crosswords, I can understand why your software might have only a few hundred puzzles, since each hint needs to be done by a human editor. But with Sudokus, I wonder why they don't just let the software generate millions of puzzles? Imagine how many millions of puzzles "included" they could claim."

Because Sudoku Gridmaster doesn't use an algorithm -- all of the puzzles in it are handmade. Having solved many Sudoku puzzles in my lifetime, I can assure you that 400 handmade ones are more fun and artistic than millions of computer-generated ones. :)

I tried out the Dancing Links solution a few years back in Java, and it just didn't scale, and was extremely slow. Dancing Links are useful for enumerating all possible solutions to a problem, not definitely not ideal for finding just one solution.

The memory use, even just for a 9x9 puzzle, would balloon to over a gigabyte. Not good ;-)

To David Bau :

Your solution works very nice.

I'm a disabled person, former programmer, and I just love Sudoku.
Unfortunately, I do not understand the Python language (I was raised in Bill Gates' Dos years ...).

I had simply one question : can your code be compiled to a command line utility. Let's say it is called from the command line as

SUDOKU.EXE 54453

Where 54453 represent a seed for rabdomizing.

And the Sudoku.EXE then exports a textfile (even a textfile with the 81 char's is enough (0 represents a blank place)

This way, this could be implemented very easy in no matter what type of application (also in Clipper as I use ...)

Many thanks !

Greetings from Belgium

Hello,

I didn't know that there was so much fuss around creating a sudoku puzzle. I have developed SUHelper in www.charalampakis.info during my summer holidays. It is free... it creates random puzzles by rearranging a solved puzzle. I think it is rather fast, although I haven't tested it against other algorithms, nor was it my intention (to create the fastest algorithm). The program has full GUI. It can also try to solve a puzzle with logic (without guessing). Any feedback would be greatly appreciated.

Regards

Interesting... However, I don't believe the method above will generate a valid sudoku puzzle, because it uses best guess to determine if a sudoku is valid. Sudoku puzzles are supposed to be solved with logic, not trial and error.

Perhaps forced chaining would be a better approach. I've implemented this in my own code, and it was surprisingly easy. Here's a breakdown of how it works:

loop through all unsolved cells, first the ones with 2 possibilities, then 3, then 4, etc.

for each possibility in the cell, create a copy of the original solution matrix, and populate that cell in each of the copies with each possibility. eg, if cell A1 can only contain 5, 7 or 9, then make 3 copies, populate A1 in the first copy with 5, 7 in the second copy, and 9 in the third copy. then pass each copy to the solver as if it were a puzzle in its own right. compare the copies, cell by cell. If any cell is set to the same value in all three copies, then that cell must contain that value.

Simon,

The method of rearranging a solved puzzle always produces a valid puzzle. You just randomly swap rows and/or cols (with the necessary adjustments) for a number of times. That's it...

Here's the initial puzzle i use:

gSeed(1, 1) = 1: gSeed(1, 2) = 2: gSeed(1, 3) = 3: gSeed(1, 4) = 4: gSeed(1, 5) = 5: gSeed(1, 6) = 6: gSeed(1, 7) = 7: gSeed(1, 8) = 8: gSeed(1, 9) = 9
gSeed(2, 1) = 4: gSeed(2, 2) = 5: gSeed(2, 3) = 6: gSeed(2, 4) = 7: gSeed(2, 5) = 8: gSeed(2, 6) = 9: gSeed(2, 7) = 1: gSeed(2, 8) = 2: gSeed(2, 9) = 3
gSeed(3, 1) = 7: gSeed(3, 2) = 8: gSeed(3, 3) = 9: gSeed(3, 4) = 1: gSeed(3, 5) = 2: gSeed(3, 6) = 3: gSeed(3, 7) = 4: gSeed(3, 8) = 5: gSeed(3, 9) = 6
gSeed(4, 1) = 3: gSeed(4, 2) = 1: gSeed(4, 3) = 2: gSeed(4, 4) = 6: gSeed(4, 5) = 4: gSeed(4, 6) = 5: gSeed(4, 7) = 9: gSeed(4, 8) = 7: gSeed(4, 9) = 8
gSeed(5, 1) = 6: gSeed(5, 2) = 4: gSeed(5, 3) = 5: gSeed(5, 4) = 9: gSeed(5, 5) = 7: gSeed(5, 6) = 8: gSeed(5, 7) = 3: gSeed(5, 8) = 1: gSeed(5, 9) = 2
gSeed(6, 1) = 9: gSeed(6, 2) = 7: gSeed(6, 3) = 8: gSeed(6, 4) = 3: gSeed(6, 5) = 1: gSeed(6, 6) = 2: gSeed(6, 7) = 6: gSeed(6, 8) = 4: gSeed(6, 9) = 5
gSeed(7, 1) = 2: gSeed(7, 2) = 3: gSeed(7, 3) = 1: gSeed(7, 4) = 5: gSeed(7, 5) = 6: gSeed(7, 6) = 4: gSeed(7, 7) = 8: gSeed(7, 8) = 9: gSeed(7, 9) = 7
gSeed(8, 1) = 5: gSeed(8, 2) = 6: gSeed(8, 3) = 4: gSeed(8, 4) = 8: gSeed(8, 5) = 9: gSeed(8, 6) = 7: gSeed(8, 7) = 2: gSeed(8, 8) = 3: gSeed(8, 9) = 1
gSeed(9, 1) = 8: gSeed(9, 2) = 9: gSeed(9, 3) = 7: gSeed(9, 4) = 2: gSeed(9, 5) = 3: gSeed(9, 6) = 1: gSeed(9, 7) = 5: gSeed(9, 8) = 6: gSeed(9, 9) = 4

For those looking for an algorithm implemented in a language other than Python - here is the source for a Javascript sudoku engine that can actually also support hinting:

http://davidbau.com/sudoku/sudoku-engine.js

It's part of the hinter at http://davidbau.com/sudoku/

I have written a program in Excel that generates Sudokus. It is very interactive.

Is there a proven optimum algorithm for generating a Sudoku puzzle?

Dear Jort Bloem,

I am Akhilesh Godha. I came to know about you from my uncle Narendra Godha. Can you please contact me on my email id. It will be of great help to me. I am currently in Auckland and want to discuss with you.

My email: agodha115@yahoo.co.nz

Dear members, Sorry for posting this comment as I am seriously searching ways to contact Jort Bloem who has posted a comment in this webpage.

Thanks,
Akhilesh Godha

A simple solution:

http://pastebin.com/1LfMVdu3

Jort Bloem described a nice algorithm for getting pretty far in computer-solving sudoku without much work.

I remember how pleased I was a few years ago when, in writing my solver, I realized that David Bau's two rules here were actually instances of the same rule that Jort Bloem describes.

If you have a set of 1 cell with only 1 possible number that could go there, then put the number there.

If you have a set of 8 cells which among them have only 8 possible numbers, then the remaining number must go in the remaining cell (this is David Bau's rule 2).

Vary that parameter from 1 through 8 and you also get Jort Bloem's rules.

These rules don't take into account the interaction between the boxes and the rows/columns that make a sudoku different from a latin square, though; you also need a "box-line" rule of some sort, along the lines of "if all possible locations for a given number in a given line are in the same box, then delete that number from the possibilities for all the remaining cells in that box", and the same thing interchanging line and box.

I stumbled on a 2009 Canadian journal paper by Chungen Xu and Weng Xu that describes their work in purposely generating sudokus of a given difficulty. It basically follows the same idea suggested by David Maymudes in the comments above. Here is the link:

http://www.ccsenet.org/journal/index.php/jmr/article/viewFile/3718/3313

The most curious thing I think is that their paper directly cites this webpage (the one you are reading now) as a reference. Hooray for the web.

thanks for posting, just what i was looking for.

Are the puzzles that are generated at the given links available for commercial use?

For commercial use? No, not at this time. Enjoy them for free; please don't resell them, and thanks for asking.

minimum for 6x6?

since i made a 6x6 yesterday using 9 givens, i thought i might just ask...

...they were handwritten--can't use a generator on a ds :|

...they were handwritten--can't use a generator on a ds :|

I'd argue here with two posts:
Posted by: Shawn at May 14, 2007 09:23 PM
Posted by: Aristotelis Charalampakis at September 23, 2009 08:48 AM

What you say is true: with such a changes your board remains valid.

However during the game you can identify patterns which make solving relatively easy.

Just take the first column starts with 1 4 7.
If you go a bit right you can see a column starting with 4 7 1 and then one with 7 1 4.

If you follow the valid transformations (switching columns, rows) you will end up with having these triplets unmodified. (If you see somewhere 1 4 7 you can be sure that if you have a 7 and 4 in some column triplet, then the 3rd one is 1.)

If you use the "switch two numbers in all occurrences" rule then you will have the same issue, but different numbers.

What do you think?

Further thinking on this topic: the problem which i mentioned above is a problem of the starting board. If this board doesn't have such patterns, the result won't have it either.

Algorithms like some of the ones being proposed in the comments that require seeding with a valid Sudoku board before they will work ought to be considered cheating. If your algorithm cannot generate a valid Sudoku configuration without prior knowledge of one or more valid Sudoku configuration(s), then it is not a Sudoku generation algorithm. It's just a glorified array permutation algorithm.

I am using your sudoku generator, but I can't find the files sudoku-template.pdf/.ps/.txt/.html that you refer to in the comments. Great blog and useful stuff on sudoku and jquery. thanks.

poo

I saw some incorrect statements in the comments stating that all Sudoku boards can be solved by using the row/col/square technique, and I wanted to correct this. In fact the difficulty of a Sudoku puzzle is based on the technique used to solve it, and the above technique provides a definite solution only for easier puzzles. For more about this I found an excellent site: http://www.sudoku-solutions.com/background.php

Dancing links: This is tricky to implement efficiently, but Donald Knuth's own program for it, as well as his frontend for Sudoku puzzles, is available on his website:

www-cs-faculty.stanford.edu/~knuth/programs.html

Only drawback: you need a TeX installation, since the code is (of course) in Knuth's own literate programming language CWeb. The `ctangle` tool supplied with TeX turns it into C. I've found it to be very fast. The output from the dancing links program includes the number of insertions/deletions, which is correlated to the difficulty of the puzzle.

@Hal: The magic number is 6^6. There is a symmetric combinatorial interpretation, giving a one-to-one mapping between six-digit base 6 numbers and valid patterns. Think of the grid as three horizontal bands of three rows each and three vertical bands of three columns each, and associate a digit with each band.

Choose any valid pattern to be #000000.

Use the digits 0 to 5 to encode the permutations of (0,1,2), e.g.
0: (0,1,2)
1: (0,2,1)
2: (1,2,0)
3: (1,0,2)
4: (2,0,1)
5: (2,1,0)

To convert a number to a pattern, permute the rows or columns of pattern #000000 within each band according to the permutation encoded by its digit.

Dear David, Am creating some Sudoku puzzle books on create space. May I use some of your puzzles -- 8 of them? I would at least happily credit you for the originals and then permutate them to create more puzzles for my books. If you want additional exchange for puzzles from your sudoku puzzle generator, please let me know. Please respond. Best, Carolyn Berger

Dear David, Well, you say the sudoku generator is free. Clearly, I can use it to generate sudokus, so I shall. Thank you for creating it. ML, Carolyn Berger

I wondered if I can print your free sudoku puzzles in our paper BScene. It's a small community paper. Maybe eventually post them on our website. Is that OK and do you want accreditation and what exactly?

Thanks a lot,
Edith

hi
iam student and need pso in excel or xloptimizer( no demo)
can you help me thanks

hi
iam student and need xloptimizer(no demo)
can you help me
thanks

What is the axis variable used in the Python code? Please help me. What's the use?

The difference between the impossible and the possible lies in a person’s determination. 웹툰사이트