a good worthy project ??

[prashanth]

hi friends
i know c and c++ somewat wel
i want to do a project in it
can anyone suggest me a good theme for it


thanks

 

[osmium]

i know c and c++ somewat wel
i want to do a project in it
can anyone suggest me a good theme for it

A sudoku solver or a sudoku problem generator.

 

[Barry]

A sudoku solver or a sudoku problem generator.

Aren't there already more sudoku solvers and
generators than there are possible sudoku puzzles?

 

[osmium]

Aren't there already more sudoku solvers and
generators than there are possible sudoku puzzles?

It's not even close. There are only five billion or so people on Earth. But
there are about
6670903752021072936960 sudoku puzzles, which is about 10^21.

 

[Clever Monkey]

It's not even close. There are only five billion or so people on Earth. But
there are about
6670903752021072936960 sudoku puzzles, which is about 10^21.

But, do all those actually need to be solved?

 

[Barry]

But, do all those actually need to be solved?

Acutally, I was being facetious. The sudoku solver has been beaten
to death. I wrote one a couple of years ago. Actually there are only
5,472,730,538 unique boards when you take symmetries into account.

 

[Richard Heathfield]

osmium said:

It's not even close. There are only five billion or so people on
Earth.

Can we assume there are 6670903752, please? Ta muchly.

But there are about
6670903752021072936960 sudoku puzzles, which is about 10^21.

In other words, every man, woman and child on the planet has written
about 1000000000000 solvers. That sounds about right, actually...

 

[Ian Collins]

osmium said:


Can we assume there are 6670903752, please? Ta muchly.

Not any more...

 

[osmium]

Acutally, I was being facetious. The sudoku solver has been beaten
to death. I wrote one a couple of years ago. Actually there are only
5,472,730,538 unique boards when you take symmetries into account.

Boy, it takes a huge bunch of symmetries to get from my number to yours!!
The source of my number is at the end of this message. Where did your
number come from?

As far as being beaten to death, I don't see the connection between a new
programmer and the fact that many people have attacked the same problem. Do
you think the new guy learns from emanations in the aether or something? I
think it is a problem that is easy to understand, so the OP can spend his
time solving it rather than spending a lot of time figuring out exactly
what the problem is. A lot of problems that would otherwise be good have
this shortcoming - a complicated problem definition. Another problem where
it is easy to understand the problem statement is chess. . Neither of
these need any digressions into graphics and such like, either.

http://theory.tifr.res.in/~sgupta/sudoku/expert.html

 

[Barry]

Boy, it takes a huge bunch of symmetries to get from my number to yours!!
The source of my number is at the end of this message. Where did your
number come from?

As far as being beaten to death, I don't see the connection between a new
programmer and the fact that many people have attacked the same problem.
Do you think the new guy learns from emanations in the aether or
something? I think it is a problem that is easy to understand, so the OP
can spend his time solving it rather than spending a lot of time figuring
out exactly what the problem is. A lot of problems that would otherwise
be good have this shortcoming - a complicated problem definition. Another
problem where it is easy to understand the problem statement is chess. .
Neither of these need any digressions into graphics and such like, either.

http://theory.tifr.res.in/~sgupta/sudoku/expert.html

A sudoku can be solved with a very short recursive function. It's not
inherently
much of a programming task.

When I said symmetries I was including remapping as a case of symmetry.

http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html

 

[Richard Heathfield]

CBFalconer said:

9! is about 3.5 * 10e6.

To be specific, it's 362880, so you're out by an order of magnitude.

 

[Keith Thompson]

CBFalconer said:



To be specific, it's 362880, so you're out by an order of magnitude.

No, you're off by an order of magnitude; he's off by two.

(10e6 is 10 million, not 1 million.)

 

[Richard Heathfield]

Keith Thompson said:

No, you're off by an order of magnitude;

....in the last part of my statement, yes.

he's off by two.

(10e6 is 10 million, not 1 million.)

And I thought /I/ had an eye for detail! Thanks for the correction.

 

[osmium]

... snip (somebody deleted attributions) ...

9! is about 3.5 * 10e6. This gets things within a factor of 100 or
so. Now look for other permutations, such as horizontal and
vertical interchanges.

OK, that kind of establishes one boundary. The other boundary is 81! which
I believe is about 5.79 x 10^120. So we are homing in on the answer!

That's based on the guess that you just made up 100, it sounds too "round"
to be accurate. And besides that, "or so" kind of minimizes any claims to
accuracy. I don't want to spend the rest of my life on this, but I really
would like to know whose expert is closer to right, my expert or the other
one. If anyone comes across another source, or a critique of either of
these two sources, I would like to know of it.

 

[Richard Heathfield]

osmium said:

OK, that kind of establishes one boundary. The other boundary is 81!
which
I believe is about 5.79 x 10^120. So we are homing in on the answer!

Looks about right. But of course we can constrain it further than that.
Each row has 9! possibilities, and *even if they are independent*
(which they are not), we need only consider (9!)^9 combinations, which
is a mere 109110688415571316480344899355894085582848000000000, or
approximately 1.09E48, for the upper limit, and which is practically
infinitesimal compared to 5E120.

 

[Keith Thompson]

It'll take a while to live this one down :-(.

Ah, but if we assume that "10e6" was intended to be hexadecimal, and
you merely left off the "0x", then you're only off by a factor of
about 24 (in the opposite direction).

And if we further assume that the '.' in 3.5 is really the Perl string
concatenation operator (which would require surrounding whitespace in
this context), then you're remarkably close:

3 . 5 * 0x10e6 =
3 . (5 * 0x10e6) =
3 . (5 * 4326) =
3 . 21630 =
321630

which is only about 11% smaller than the correct answer, 362880.

If you had used 3.15 rather than 3.5, you'd be within 1%. Perhaps the
missing 1 was merely a typo. That's a minor error compared to the
missing "0x", the missing whitespace around the "." operator, and the
use of Perl rather than C.

So don't feel too bad about it.