PDA

View Full Version : Quest 16 Project: Intro and FAQ

08-14-09, 01:32 PM
Welcome to Quest 16!

Quest 16 is a project to search through all the Sudoku puzzle grids which have 16 clues (givens), and see if any of them, have just ONE possible solution. Those are the only proper puzzle grids, to a Sudoku fan. :)

Background:

I got interested in Sudoku solving, but right away, I wanted to program a solver for it.

So I did. :cool:

That got me interested in some of the many different and esoteric techniques used to solve the puzzles, (which are really mind-blowing, trust me).

One day, I read a post saying that nobody knew if there were any valid puzzles grids with only 16 clues. Over a couple of years, that became the challenge - OK, my "Windmill" to tilt at, a la Don Quixote. I started to plan my attack on this monster problem.

I stopped working on it, when a BOINC DC project "The Sudoku Project", was started by some European University guys. Great! Problem will be solved, yes?

No!

Oddly, they began their search for a valid 16 clue puzzle, by searching through grids with only 10, 11 or 12 clues, then they went inactive, stating they lacked the resources to search through the grids with more clues. Huh?

So the Windmill still needs a good jouster. :p

FAQ:

1) Is this a DC project?
Not yet. That is the goal, however.

2) Will this save lives, etc.?
No. It is a brute force computerized search, to find an answer that we can't prove with theories. Hard to say what you or I might do later, with what we learn about running a challenging DC search project.

3) How big is this project?
Oh, *BIG*. :D One way to think of it is to imagine a number 9, with 80 zero's to the right of it. Fortunately, we only need to check out about half of that, so make the 9 into a 5. (still with 80 zero's to it's right).

*Big* Windmill !! :eek:

4) Current status?
I'm testing the first 7 work units, whenever the Summer temperatures, allow.

The current software scans through about 400 million grids, in 24 hours, on a 2.66GHz cpu.

5) When will this become a BOINC DC project?
That depends on how the testing on the WU's, etc., turns out, and how readily I can go from noob to BOINC project admin. BOINC site says "Three months", minimum after your in-house testing is a success.

"that's a *BIG* Windmill, isn't it?" :D

6) Next to do?
Code up a program to create the work units. I made the first seven work units by hand, but that's far too slow.

7) When will the project be finished?
Wild guess is seven to ten years, depending on the number of participants, and how much we can optimize the client program.

This is all preliminary, at this time, but every jouster needs another to avoid those horrid spinning arms of the windmill. If that sounds interesting, please post up here, or private message me. Or subscribe to the other Quest 16 Main thread. It will be going up, soon.