Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

To all sudoku gods, please help.
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
defunct

Joined: 02 Oct 2006
Posts: 6
:

Items
PostPosted: Mon Oct 02, 2006 9:23 pm    Post subject: To all sudoku gods, please help. Reply with quote

Hello everyone, thanks for taking the time to read my post.
My company is organizing a nationwide challenge consisting of many challenges and whoever is first to clear all stages will get a top prize.

One of the challenges for participants involve solving a sudoku puzzle. I have a couple of questions regarding that:

- is it possible to devise a unique sudoku that cannot be solved by
computer programs (or at the very least, take a very long time by programs to solve)?
- to prevent people from cheating (i.e using computer programs), should I devise alternative sudokus such as 16 by 16 or 25 by 25 ones? Or should I use symbols to replace the numbers or does it not make a difference for cheaters?
- does anyone have any advice regarding how I should go about setting the sudoku challenge?

Thanks again for reading. I am not a programmer so please reply in layman's terms when possible.

Cheers.
Back to top
View user's profile Send private message Send e-mail
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Tue Oct 03, 2006 12:40 pm    Post subject: Re: To all sudoku gods, please help. Reply with quote

defunct wrote:

- is it possible to devise a unique sudoku that cannot be solved by
computer programs (or at the very least, take a very long time by programs to solve)?

No. Most sudoku programmers have a backtracking program than can solve even the most difficult puzzles by trial and error in about 1 second. Many highly sophisticated logic solvers are available free on the Web, e.g. Sudoku Explainer, and they even give a blow-by-blow account of the solution.
Quote:

- to prevent people from cheating (i.e using computer programs), should I devise alternative sudokus such as 16 by 16 or 25 by 25 ones? Or should I use symbols to replace the numbers or does it not make a difference for cheaters?

You can certainly go to higher ranks as, to the best of my knowledge, solvers are not generally available, although they do exist.

Replacing digits by symbols doesn't help much, as any intelligent player can substitute digits for the symbols, use a solver, and then reverse the substitution.
Quote:

- does anyone have any advice regarding how I should go about setting the sudoku challenge?

There are certainly people here who would happily provide you with high-rank puzzles (including me, see, e.g., http://www.sudoku.com/forums/viewtopic.php?t=4816). Another possibility is a Butterfly (Samurai) of five interlinked sudokus that cannot be solved independently. You would have to trust all of us not to enter though.
Regards,

Mike Metcalf
Back to top
View user's profile Send private message
Soultaker

Joined: 28 Feb 2006
Posts: 49
:

Items
PostPosted: Tue Oct 03, 2006 10:46 pm    Post subject: Reply with quote

I think high-rank puzzles are generally 'more' harder for human players than computers, if you get what I mean. I remember solving a 25x25 (!) puzzle programmatically; that took a minute where regular puzzles take less then a second, but solving it by hand would have been practically impossible. So, creating a larger puzzles makes it harder for both the computer and human solvers, but more so for the latter. I wouldn't recommend it.

Using a non-standard variation is a good idea, though. Although you can't prevent people from solving it with the computer altogether, you can at least prevent the use of any standard programs available today. For example, you could create a shape sudoku (one where the 3x3 blocks are replaced with arbitrary shapes) and combine it with a diagonal sudoku (where the digits on the diagonals must be all different).

For something completely different, you could take a look at the Exotic Sudoku subforum; many people have proposed variants that are pretty different from Sudoku as you know it, and I doubt solvers exist for most of them. Ofcourse, the question is wether or not you insist on including a Sudoku puzzle; you could include an exotic variant, but that wouldn't really be a sudoku puzzle anymore.
Back to top
View user's profile Send private message MSN Messenger
defunct

Joined: 02 Oct 2006
Posts: 6
:

Items
PostPosted: Wed Oct 04, 2006 6:14 am    Post subject: Need help Reply with quote

Thanks, Mike and Soultaker for replying.

Do you think it is better to use a butterfly/ samurai sudoku or just a plain 25X25 one?

I want an extremely hard puzzle but at the same time, one that is solvable after a very long time and a fair bit of mean thinking.

The butterfly/ samurai sudoku seems like a very interesting variant.
I would love to use it in the latter stages of my challenge if you think it is a difficult enough variant.

How long does it take for an expert to solve a butterfly/ samurai puzzle?

Can anyone please devise a unique butterfly/ samurai sudoku for me?

I will include your name in the writing credits of the mystery if I were to
use any of your work.

Thanks again in advance. Very Happy
Back to top
View user's profile Send private message Send e-mail
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Wed Oct 04, 2006 12:50 pm    Post subject: Re: Need help Reply with quote

defunct wrote:

Do you think it is better to use a butterfly/ samurai sudoku or just a plain 25X25 one?

How long does it take for an expert to solve a butterfly/ samurai puzzle?

Can anyone please devise a unique butterfly/ samurai sudoku for me?


Actually, I'm not very good at solving any puzzles, so I'm not the person to ask about subjective matters like difficulty of solving for humans. Below, I attach a 25x25 as sample. It is symmetric (which most people like), so not quite minimal. I can produce these in vast quatities. To make a butterfly I need to fiddle a bit by hand so I need an hour and would do it only if really needed. However, I can send you a sample one by e-mail if you send me your address (it's fairly difficult, but I made it in January and my programs have evolved since then). You can test them on somebody (something you should do anyway if setting a competition -- remember the great Sky TV debacle!).

Regards,

Mike

Code:

  .  . 10  . 23  .  .  .  .  .  .  . 25  .  .  .  .  .  .  .  5  .  6  .  .
  .  .  . 22  .  .  . 14  .  8  .  . 10  .  . 25  . 20  .  .  . 16  .  .  .
  .  .  .  5  .  . 19  .  2  .  . 24  6  8  .  . 21  .  9  .  .  4  .  .  .
  8  4 12 21 17  .  .  .  .  .  . 23  . 16  .  .  .  .  .  . 13 24 19  9 10
  9  1  .  .  .  . 10  5 23  . 15  .  .  . 22  . 13 14  8  .  .  .  . 11  3
 22 25  . 17  .  1 24  .  . 12 10 16  .  2  8 21  .  . 14 19  .  5  . 23 20
 18  .  .  .  . 17 21 25  .  .  .  . 23  .  .  .  . 13  1 16  .  .  .  .  7
  .  . 19 23  .  .  5  .  3 20  1 14  . 21 25 12  8  . 24  .  . 10 11  .  .
  .  5  . 12  .  6  . 19 14  .  .  .  .  .  .  .  9 15  . 10  . 17  .  1  .
 20  . 16 14  1 11  .  . 10 23  4  .  .  . 15  3 25  .  . 17 21 18 24  . 19
  .  . 22  8 16 18 11  . 19 25  . 21  .  7  . 17  3  . 13 15  1  9  5  .  .
  .  7  5  . 19  .  8  .  4  9 20  .  .  . 18  1 23  . 21  . 17  . 13  2  .
 15  .  9 11  .  . 14  6  .  .  . 19  . 22  .  .  . 24 16  .  . 23 21  .  4
  . 13 18  . 12  . 23  . 21 24 17  .  .  . 16 14 10  .  2  . 11  .  7 25  .
  .  . 21  2 24 13 17  . 12  1  .  4  .  5  . 19 22  .  6 11 10  8 20  .  .
 19  . 11  9 22 12  .  .  5  6  3  .  .  . 10 16  2  .  . 24  7 20  4  . 15
  . 10  .  6  . 14  . 23 11  .  .  .  .  .  .  .  7 17  . 22  . 25  .  8  .
  .  . 25 15  .  . 22  . 16 18 11  7  .  1  6 13 14  . 20  .  .  2 17  .  .
  7  .  .  .  .  3  2  8  .  .  .  .  5  .  .  .  . 19 11 12  .  .  .  .  9
  2 24  . 16  . 21  1  .  . 10  9 12  . 19 14 15  .  .  4  8  . 11  .  6  5
 17 22  .  .  .  .  9  2  6  . 24  .  .  . 21  . 20 11  7  .  .  .  . 15 14
 16 15  6  1 20  .  .  .  .  .  . 10  . 18  .  .  .  .  .  .  4  7  9  5 11
  .  .  . 18  .  .  3  . 20  .  . 15  2 13  .  .  1  . 10  .  .  6  .  .  .
  .  .  . 24  .  .  . 16  . 11  .  . 19  .  .  5  . 21  .  .  .  1  .  .  .
  .  . 14  . 11  .  .  .  .  .  .  .  9  .  .  .  .  .  .  . 22  . 25  .  .
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Wed Oct 04, 2006 1:36 pm    Post subject: Reply with quote

It seems to me that your insisting on having a complicated Sudoku puzzle in your contest will lead to one of two possible outcomes:

1) Someone with access to an advanced solver will win your contest, or
2) No one will be able to win your contest.

If (2) is your objective, then substitute FreeCell Pro's (FcPro) deal #53687601 for the Sudoku puzzle. In the first 100,000,000 8x4 FcPro deals, this is the only deal that has never been resolved as solvable/unsolvable.
Back to top
View user's profile Send private message
defunct

Joined: 02 Oct 2006
Posts: 6
:

Items
PostPosted: Wed Oct 04, 2006 3:33 pm    Post subject: unique sudoku needed Reply with quote

I do not wish to create a puzzle that no one will be able to solve.
Just one that even experts will take quite a while to solve.
The sudoku is not the be all and end all in the contest. There are other stages that people with advanced programs will have to solve as well so it doesn't follow that whoever has an advanced solver will win the competition though that will be a huge advantage.

Mike, if you are interested in supplying us with sudoku puzzles, please
get in touch with me at cliff.gay@gmail.com or add me to your MSN using the email contact defunct21@hotmail.com and we can discuss how we can
work together.
Back to top
View user's profile Send private message Send e-mail
Soultaker

Joined: 28 Feb 2006
Posts: 49
:

Items
PostPosted: Thu Oct 05, 2006 12:52 pm    Post subject: Reply with quote

Maybe you should have a look at Ruud's clueless (not really) puzzles in the Exotic Sudoku forum. They are:
- hard to solve by hand, but not as tedious as large (25x25) regular puzzles,
- very similar to Sudoku, gameplay-wise,
- non-standard enough so there is no solver available (ok, Ruud probably has a solver).

Either way, I think the way to go is to pick a non-standard variant, not a large regular sudoku. The large regular sudoku's are still easily solved programmatically, but tedious to do by hand. But it's your call ofcourse; if you have your mind set on a 25x25 Sudoku I won't stop you. Smile
Back to top
View user's profile Send private message MSN Messenger
defunct

Joined: 02 Oct 2006
Posts: 6
:

Items
PostPosted: Fri Oct 06, 2006 6:06 am    Post subject: Reply with quote

I'm thinking of a 25X25 because it's really difficult to solve and I can't find any solvers online using google. But you're probably right, a lot of people could probably break it easily with their own solvers.

What do you think are some of the more interesting variants?
Back to top
View user's profile Send private message Send e-mail
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Oct 06, 2006 11:27 pm    Post subject: Reply with quote

There are many solvers that cannot be found by Google, simply because they are not publicly available. Many members of this forum have written their own solver, but only a few make them available to others. This does not only apply to solvers for 9x9 sudoku, but also for other sizes. I have a solver/generator that can handle every size upto 16x16, but it takes me 2 minutes to modify it to handle 25x25.

Human players are not so lucky. 25x25 will not attract many players, because you cannot manage 625 cells as a human player. Unlike a Clueless or Samurai, you cannot isolate any part of the puzzle. The few people with computer solvers would have an even greater advantage.

Check Pyrrhon's variant page to check out some exotic variants. You can mix any number of constraints to come up with a new variant. But even if you create something new, there will always be people who can adapt their software for it. You need to stay one step ahead all the time.

Ruud
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Sat Oct 07, 2006 12:59 am    Post subject: Reply with quote

How about this,

Pick a puzzle know to have MULTIPLE SOLUTIONS or even NO SOLUTION...........

in order to establish the staus of the above you have to use very advanced techniques or a computer solver........

You are after the first few placements the a person can manage before getting stuck.... not knowing even that this puzzle is INVALID......

so you would know that for example r1c1....r5c6 can be uncovered using singles regardless of the staus of the grid any other placemnt need far more advanced techniques....No one would know the staus of the grid unless he cheated......

In the competition ask for the first 2 placements & if it matches the above then you've got a winner....Any other answer (which may be correct) would be a cheat, guesser.........

Not watertight, but tough to get around for a surprised cheat.

tarek
Back to top
View user's profile Send private message
Jean-Christophe

Joined: 19 Mar 2006
Posts: 126
:
Location: Belgium

Items
PostPosted: Sun Oct 08, 2006 2:52 pm    Post subject: Reply with quote

I agree 100% with Ruud Cool

Have a look at combined sudokus like this one

There are probably no software which will solve such a variant.
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.
Back to top
View user's profile Send private message Visit poster's website
defunct

Joined: 02 Oct 2006
Posts: 6
:

Items
PostPosted: Tue Oct 10, 2006 7:14 am    Post subject: Reply with quote

Ruud, I think you are right. A 25X25 puzzle will probably drive someone crazy. I was thinking of using a butterfly samurai puzzle but what do you think of my using that variant? Is is suitable?

Tarek, your suggestion is excellent but unfortunately it will be hard to execute that as none of us are expert sudoku solvers (much less setters).

Jean, the combined sudokus seem like a very interesting option as well.
Will any of you be willing to contribute your own puzzles to us?
Back to top
View user's profile Send private message Send e-mail
Jean-Christophe

Joined: 19 Mar 2006
Posts: 126
:
Location: Belgium

Items
PostPosted: Tue Oct 10, 2006 8:07 am    Post subject: Reply with quote

defunct wrote:
I was thinking of using a butterfly samurai puzzle but what do you think of my using that variant? Is is suitable?


Although, I'm not sure there are programs to solve overlapping puzzles like samurai, each of the sub-puzzle is a regular 3x3 sudoku. Using any software for each of the sub-puzzles will make it very easy to find the solution. I don't think it fits your needs Rolling Eyes
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.
Back to top
View user's profile Send private message Visit poster's website
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Tue Oct 10, 2006 12:18 pm    Post subject: Reply with quote

Jean-Christophe wrote:

Although, I'm not sure there are programs to solve overlapping puzzles like samurai, each of the sub-puzzle is a regular 3x3 sudoku. Using any software for each of the sub-puzzles will make it very easy to find the solution. I don't think it fits your needs Rolling Eyes


This is not strictly true. None of the sub-puzzles in its own right is a true sudoku as they are underconstrained and have multiple solutions. Solving the butterfly depends on transmitting crucial information between the puzzles. Thus, a solver can only be sensibly used at an intermediate point in the solution when enough of the cells in the overlapping regions have been solved to allow a solver to take over. Since this point is a priori unknown, the human must try several times, for each of the five, until that point has been determined. It's pefectly feasible but somewhat laborious.

Regards,

Mike Metcalf
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron