[Adak]

to Quest 16's Main Thread

The client software tests are going well - getting about 12.6 Billion grids generated and checked for uniqueness, today. (On an i7@2.96GHz). (The only valid Sudoku puzzle grid, is one with a *unique* solution)

Humor:
Who invented Sudoku, anyway?

The Devil ! He wanted us to become obsessed with searching the unsearchable.

I'm getting re-acquainted with Forte's excellent newsgroup and email reader software. I'm looking for help on a probability problem (namely, how many 16 clue grids are there, all together), and also on optimizing the algorithm of the client program. The comp.newsgroups are a great resource for that, and is completely un-tapped at the moment.

I've tried asking on a few programming forums, but the instant they read "Sudoku", they start talking about solver program *stuff*. This is *not* a Sudoku solver program! It uses a solver to check for a unique solution to the grids, but the solver part of the program is already highly optimized. It's the grid generator part of the program, that needs more work.

Code:

-----------------------+
Grid Generator program |   =======> Generates a million grids 
-----------------------+            at a time, writing them 
                                    all to a file.

Then calls the 

-----------------------+
Solver program         |   =======> Checks each grid
-----------------------+            for a unique solution

writing out any grid which has a unique solution, of course.

When the Solver program is finished, the Grid Generator program continues right where it left off, and generates another batch of grids.

It's big-time craziness, in a big programming loop.

I'll be working on a Linux version of the client program (it's currently a Windows console program), next. I'm looking forward to seeing how Linux compares with Windows, in this program.

[Adak]

The testing continues, and the leader of the enemy army, in the flesh (sort of).

[Adak]

The Linux version has been put on hold for a bit. The install of Ubuntu into the box that I program on was a complete bust, thanks to Ubuntu's cavalier attitude about fixing bugs in their partition manager - unbelievable.

When the weather cools enough to run the server, I'll program it on that box, since it already has a good install of Ubuntu on it.

Fortunately, I've found a more efficient algorithm for the searching program (the generator program), and that update will give the client a much needed speed increase. I estimate that will require two more days to finish.

That will make those windmills absolutely dizzy trying to avoid the concerted attack!


I'm putting off the work to make this a BOINC project, until I have the client as fast as I can get it, while keeping it accurate and stable, of course. Once work starts on the administrative side of the project, there won't be time to work on the client, anymore.

P.S. The client instances now being tested, have searched through 90 Billion Sudoku grids, so far.

[Adak]

The speed increase <sigh> also made the program inaccurate, so fzzzt!!, out it went.

The version I'm working on now is the slower, but accurate version. I'm speeding this version up by adding some lookup tables. OO-RAH!

I'm not very experienced with lookup tables, so be patient.

The lookup tables failed**, but I have found a few other good ways to streamline the program. That will increase the program's speed by approximately 35%.

It's not easy though - it involves a lot of editing of the code, and then some testing to ensure it's still all accurate. Today is Sunday (day of this edit). The program won't be ready for 3 or 4 more days. The program (this part of it), has about 2955 lines of compilable code. This edit changes over 50% of that number. Thankfully, it also shortens it!

See ya Thursday!

** Lookup tables worked fine, but not for this Sudoku program. They lump tallies all together, and are wickedly fast, but in Sudoku, like when you're checking if a digit is legal for a square, you can't have all the row, column, or boxes of 9, tallied up all together - digits on the left, have to be checked - but digits on the *right* side of the one being tested, have to be ignored. Lookup tables won't give you that unless you have a lookup table for every square - and now where's your speed gone? And the program will be lengthened a great deal.

[Adak]

Version 2.0 is done, but before anything else, it must finish extensive testing to ensure it's accuracy.

I had meant to just make a few adjustments to the program, which was all the improvements I could think of, to net about 33% better performance.

While I was working on that, I had an insight into another improvement (an old idea from last month, but with a twist), which now has increased performance to about 70 X as fast.

What used to take 70 seconds, now takes less than 1 second, to do the same work.

Since the changes were more radical than expected, the testing has to be more thorough, as well. That will continue day and night, until I'm sure it's accurate.

Then that mean ol' windmill better watch out!

[donuts]

Keep us posted, this is interesting stuff!

[Adak]

While the client program is being tested, let's break out a few bits and pieces.

If you think of of a Sudoku grid as a single (very long) number, then the first number to start a search on, might be this:

000... 0001 << where the ... means we're skipping a lot of zero's. 80 in all

and ending with:

987654321... << where we have the very largest legal 80 digit number.

So the number of numbers we'd have to search would be *impossibly huge*.

Fortunately, we're a bit more clever than that! Stick with me on this, OK?

Every Sudoku puzzle grid can be mutated (like the creature from the Black Lagoon or something), into several other boards THAT ARE REALLY JUST THE SAME puzzle grid.

It's like you took a book, and you turned it 90 degrees - it's still the same book, but it looks slightly different, until you turn it back. You could also turn it upside down, or put in a different location. It's still the same book, clearly.

Sudoku grids are like that, but even more so. Here's the list of things you can do to a single Sudoku grid, and still have THE SAME puzzle.

1) swap any two rows within a band
2) swap any two columns within a band
3) swap any two cell values for all cells with those values
4) rotate the grid 90 degrees

Any combination of these actions can be used to rearrange a puzzle grid, anyway we want to -- this is called normalizing, standardizing, or canonicalization, of a puzzle grid.

A band = one of the three row horizontal groups in a puzzle grid. Here, one band is blue, the next is in yellow, and the third is in green.

Code:

+-----+-----+-----+
| 000 | 000 | 000 |
| 000 | 000 | 000 |
| 000 | 000 | 000 |
+-----+-----+-----+
| 000 | 000 | 000 |
| 000 | 000 | 000 |
| 000 | 000 | 000 | 
+-----+-----+-----+
| 000 | 000 | 000 |
| 000 | 000 | 000 |
| 000 | 000 | 000 |
+-----+-----+-----+

If you've jumped ahead and figured out that by rotation, we can make a horizontal band, into a vertical band (called a chute), then you're ahead of the game, and right as rain.

Next update, I'll show how standardizing can be used to cut down the search for a unique puzzle grid with 16 clues, immensely.

Meanwhile, the Quest program, continues it's preliminary testing.

Edit: The first test, which compared the output of the new version, with the output of the (known to be accurate) previous version of the program, is finished. It passed!

That's a big relief after doing all those changes to the new version.

The second test is underway. This will test both the new generator program, and the solver, on puzzle grids with 17 clues on them. This bunch is mostly studied, and verified, so again, it will be a comparison of known facts, with program output, as a test for accuracy.

It's a lot faster, but any program will be slowed down as it works it's way up the squares. Every new square will have 10 times as much work to be done as the last one!

I'm trying to figure out just how long this test might need to run. Keep your fingers crossed!

[Adak]

Sudoku is weird. It just clobbered my try at improving the search.

Say you took a car, or a bicycle, and removed two wheels from it. You know beyond a shadow of a doubt that what's left, is a car or a bike, which is just missing two wheels. It's hasn't been reduced to junk.

That's just common sense, but that's *NOT* how Sudoku works. Because if you take a perfectly good Sudoku solution (all the grid values are filled in A-OK), and remove a couple of those values - now it may not be a sudoku puzzle grid, with just one unique solution. It may have two, or 5 solutions!

Which means it's not a valid Sudoku puzzle grid, anymore. It's Sudoku junk!

So my test has ended, and I have altered the new version to use the values that were reached by the old program, (which had generated and searched slightly more than 44 Billion grids).

The speed up's are working well, in fact, maybe too well - it's set to print up the current grid it's working on only once every 25,000 grids or so. And right now, it's finding those grids, so fast, that the Sudoku grid display is zipping along, almost too fast to see. And way too fast to study. You get dizzy just watching it

Fun to watch, for sure, but it may need some adjustment to make it slow down on the display a bit. As the grids get higher in number, the generation speed, will be slowed. I'll wait a few hours and check back with it, then.

Here's our new starting position, where 'n' counld be any number (and they change fast and furiously).

Code:

+-----+-----+-----+
| 000 | 000 | 000 |
| 000 | 000 | 000 |
| 000 | 000 | 001 |
+-----+-----+-----+
| 000 | 000 | 000 |
| 000 | 000 | 000 |
| 000 | 000 | 002 | 
+-----+-----+-----+
| 000 | 000 | 000 |
| 001 | 90n | nnn |
| nnn | nnn | nnn |
+-----+-----+-----+

As you can see, we have a very tough army of Windmills to fight, before this war is won!

Just to get in the spirit:
http://www.youtube.com/watch?v=IReMf...eature=related

[Adak]

The next version of the client, which has a faster generator program, is complete. She's a beaut!

My plan now is to attack this on two fronts:

1) Keep working up, from the bottom of the possible 16 clue grids, as shown in the previous post.

2) At the same time, set up work units to search right in the "heart" of the range of valid 17 given unique grids. I have all the 17 clue grids, so this is an easy job.

When our search has checked one Trillion 16 clue grids in total, then we'll have our answer.

What about the top, though? The top possible grids are closely related, or identical to, the grids on the lower part of the list of possibles, because of the many ways that a Sudoku grid can be "morphed" into several other grids - all of which are (provably), the same grid.

You can call them being in the same "class" of grids, or "non-unique isomorphs", but bottom line is, we don't need to check all the possible 16 clue grids.

Checking one Trillion grids, (1,000,000,000,000), is not enough to say absolutely "There are no unique 16 clue Sudoku puzzles.", but it is quite enough, when done in this manner, to satisfy my curiosity. One way or the other.

Although the heat of August caused all my computers to be switched off (mostly), for a few weeks, the weather has cooled enough to continue the search.

On the mid level search, we haven't started yet. On the low level search, we have already checked 50 Billion grids. Seven instances are now running, 24/7.

Ooo-rah!

[Adak]

Here's our new starting position, where 'n' could be any number (and they change fast and furiously).

Code:

+-----+-----+-----+
| 000 | 000 | 000 |
| 000 | 000 | 000 |
| 000 | 000 | 001 |
+-----+-----+-----+
| 000 | 000 | 000 |
| 000 | 000 | 000 |
| 000 | 000 | 002 | 
+-----+-----+-----+
| 000 | 000 | 000 |
| 01X | XXn | nnn |
| nnn | nnn | nnn |
+-----+-----+-----+

About 210 Billion (1,000 Million) grids later, and the X'd squares shown above, have been completely searched.

Although I can only show one number on the '1' square, that square is being searched simultaneously with 1,2,3,4,5, & 6, as it's starting value.

Thank goodness for multi-core cpu's!

Since the temps are still at or near 100F, I've just had one computer do nearly all the work. Bit of a bummer, but that's Mother Nature for 'ya - no sympathy for a hard-working cpu.

Here's the oddball thing about this search -
When I started this search, I had the common sense idea that searching through all the grids for some square 'X', would be ten times faster than searching through the same thing for square 'Y', where the squares were like this:
YX
Because the whole search is being done just like an odometer on your car. Every digit that you go to the left, means you've gone 10 times as far as the digit displayed on it's right side.

And that holds true, at the bottom squares. However, once you get into the middle band, the program begins "short circuiting" the search, whenever it has too many givens (or clues). (numbers > 0)

That speeds the search up *hugely*.

So now, the hardest part of the search, will be the easiest, and the easiest part (I thought), has become the hardest part.

I'm sure glad we've got that straightened out.

Here's a screenshot of the last search (6 of the 7 instances of the program have finished their WU).

[Adak]

The search continues, although it will take about 10 weeks to complete the current square.

These are the problems I see with making this a DC:

1) To prevent HD overuse, you need to use a RAM disk in memory. There are free RAM disk programs you can use, but not all are reliable. I've found only one such program for Windows 7, and it isn't free.

2) The program is not using the best algorithm. Yes, it's very fast for it's type, but it's still a big step away from the performance of the ideal algorithm.

3) The time the project would need. Running a DC project for 5 years, in your spare time, is not a trivial task.

4) it's not the kind of project that gets people highly motivated, in general. Nor should it. It's a puzzle, and a hell of a big search. No hyper-muons will be detected from the "Grey's", in another galaxy, No horrid diseases will be researched.

Although I'll be keeping one or more instances of the Quest 16 search software running, For all the above reasons, I've decided not to try and make this a DC, at this time.

[Flurp]

Hmm... ok I tried reading the thread... but what exactly are you trying to do? find a soduku puzzle that only has one solution?

forgive me if I didn't follow :\

[Adak]

All valid Sudoku puzzles have only ONE solution. Anything else is just a mess, because you can't tell (without a computer and a program), if your solution, was correct, or not.

Several big contests have been plagued by this. The newspaper says your solution isn't correct, because they have a different solution, and don't know that the puzzle they put out may have 10's, 100's, or thousands of solutions.

What Quest 16 is about, is trying to find out if there is a valid puzzle grid, (with just one solution), which has only 16 clues in it.

There are valid puzzles with 17 clues, and there is one 16 clue puzzle with just *two* solutions, but so far, no valid 16 clue puzzle grid, has been found.

Unfortunately, the task of searching through each possible 16 clue grid, is just *HUGE*, and the effort outweighs the cost of conducting the search. I could easily use 500 computers, running Quest software every day, for several years.

It's truly tilting at Windmill's, but it's kind of fun to do something nutty once in awhile.

[Flurp]

no one does some sort of "folding" with this?

[Adak]

No folding.

This is all about searching and testing for, a unique 16 clue Sudoku puzzle grid. Folding is up in the folding team, sub-forum, or in the Rosetta team sub-forum. (I believe they call it "crunching" technically in Rosetta, but it's folding proteins, still).

I know my text only Sudoku grids are a touch "rustic", in the posted screenshots above, but c'mon man - they're not THAT bad!

OK, well maybe they are, but you can't draw like an artist, using just ascii char's.

This is the current status of the Quest 16 search:

Code:

+-----+-----+-----+
| 000 | 000 | 000 |
| 000 | 000 | 000 |
| 000 | 000 | 001 |
+-----+-----+-----+
| 000 | 000 | 000 |
| 000 | 000 | 000 |
| 000 | 000 | 002 | 
+-----+-----+-----+
| 000 | 000 | 000 |
| 0Xn | nnn | nnn |
| nnn | nnn | nnn |
+-----+-----+-----+

Where the X is the first number being changed, in this WU. The 'n' are digits that change, as the grids are generated and checked.

There are nine instances of the Quest program running currently. The search has generated and checked about 500 Billion grids so far.

[Flurp]

Sorry I didn't explain better, I meant why not try to get some more people and make it so that you can have your computer plus a few more all working together like each computer gets a starting number ending number(start/end puzzle) and that way the workload is divided... should get you your results faster... or have one computer generating the grids and uploading somewhere and then another solving them...

[Adak]

Originally Posted by Flurp

Sorry I didn't explain better, I meant why not try to get some more people and make it so that you can have your computer plus a few more all working together like each computer gets a starting number ending number(start/end puzzle) and that way the workload is divided... should get you your results faster... or have one computer generating the grids and uploading somewhere and then another solving them...

*THAT* was the original intention - make it a distributed computing project. The obstacles to that are:

1) You need to know (or learn) how to set up a project, with BOINC. That can be done, but it takes time.

2) You need to take on the administrative work of running a project.

3) You need to provide hosting, so everyone can upload/download their work or results.

4) If you use the program without a RAM disk utility program, your drive will be working, a lot. I have a free RAM disk utility for XP, (and Linux has it's own free RAM disk), but I don't have a free RAM disk utility for Windows 7, and I'm not sure about Vista.

5) At the low end of the search space, the program I have written for it, is great. At the middle and high end of the search space, the program (although it runs faster than ever), is much less efficient. There are simply far fewer 16 clue grids to be found, in that part of the search. I'm hunting around for a better algorithm for that part of the search.

6) Last, but not least, the interest from others has been very small. The Sudoku Project was just such a distributed project, but they have closed down.

If you look at this thread for instance, you're the only person with more than one post.

The Sudoku Programmer's Forum, has also lost interest in this search, preferring to find all the 17 clue puzzle grids with a unique solution. (There are about 49,000 of those, that have been found so far).

To give you an idea of the size of this search - I've completed finding and checking about 500 Billion grids. Normally I'd say "That's a lot!"

In this case, that is far less than 1 Billionth of 1% of the total search.

A better algorithm for the middle and top part of the search space, would help tip the scales in favor of making it into a distributed computing (dc) project. I need to renew my efforts to find one, and adapt it to this search.

[Flurp]

Ah verywell I think I understand your point now thank you

[Adak]

Review:

This is where the Quest is currently, after 800 Billion 16 clue puzzle grids have been generated, and checked:

Code:

+-----+-----+-----+
| 000 | 000 | 000 |
| 000 | 000 | 000 |
| 000 | 000 | 001 |
+-----+-----+-----+
| 000 | 000 | 000 |
| 000 | 000 | 000 |
| 000 | 000 | 002 | 
+-----+-----+-----+
| 000 | 000 | 000 |
| 0Xn | nnn | nnn |
| nnn | nnn | nnn |
+-----+-----+-----+

Where the X is the first number being changed, in this WU. The 'n' are digits that change, as the grids are generated and checked.


Which is exactly the same leading number the Quest was working on, last month.

The clients have run perfectly - none has crashed or slowed down, but the number of grids needed to be both generated, and checked, increases exponentially, with every new square that we move up to. If the last square took 10 days for example, the next square will take 100 days to finish, at least.

The powerhouse computer I've been using for 8 of the 9 quest clients, has returned to full time FAH folding duties, while I use some other rigs to finish off the current quest square. It will take a good deal longer, but that's OK.

Now I have been thinking about the next generation program.

Tell me what you think:

My idea (and I have not done any research on this yet), is this:

Birds of a Feather, Flock Together

We have found almost 50,000 17 clue puzzle grids, with just one solution. In a *HUGE* haystack, where would be the most likely places to find a valid 16 clue puzzle grid?

Very close to where the 17 clue puzzle grids were found. Because both 16 and 17 clue puzzle grids have to face the same geometry on the Sudoku puzzle squares, and neither has a comfortable number of squares with a given value.

So the new quest program will look right around every one of the 50,000 17 clue givens. From below it, to above it, by perhaps 10 million on either side of the 17 clue puzzle grid.
That seems like the most likely way to find the elusive 16 clue puzzle grid with just one solution - if it exists.

For now, I have some serious programming to do.