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   

Setting driving me crazy...

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
scourtaud

Joined: 30 Nov 2005
Posts: 6
:
Location: Paris, France

Items
PostPosted: Fri Dec 23, 2005 10:43 am    Post subject: Setting driving me crazy... Reply with quote

Hi,

I've worked over a simple solver using basic logical techniques that regular human brain could use :
Naked / hidden singles,
B/C/R Interactions,
Naked / Hidden subsets.

I solved a bunch of sudokus with it and I now want to set my own.

I'm trying to build a full grid and then remove candidates randomly to get a certain level of difficulty & a unique solution.

In order to acheive this, I build an empty 2D array and while I have some missing values or an error, I try setting a value in a cell choosen randomly from those having the less candidates.
I then check for grid valididity and clean candidates of all other missing cells.

Good new is it works (sometimes) but fails approximatively 50% of the time.

I gave a go to rolling back 2 cells when grid is invalidated but this slows down the script in a scary manner...

I could improve speed a little by changing parts of the code but that wouldn't improve the success rate.

So here I am hoping one of you could give me a hint on what are my flaws and how to imporve the success rates.


Thanks in advance for your help.


Sebastien


P.S. I'm coding in PHP.
Back to top
View user's profile Send private message
Bo

Joined: 02 Sep 2005
Posts: 27
:

Items
PostPosted: Fri Dec 23, 2005 12:14 pm    Post subject: Re: Setting driving me crazy... Reply with quote

scourtaud wrote:

I'm trying to build a full grid and then remove candidates randomly to get a certain level of difficulty & a unique solution.


My experience when using this approach is that you will typically get
sudokus too hard to solve by humans and therefore to filter out
a puzzle that humans can solve will take a rather long time.
A better approach is to instead start with an empty grid and then incrementally add clues and for each clue check if a unique solution and human solvable puzzle is achieved. This algorithm is described in other threads of this forum.

Bo
Back to top
View user's profile Send private message
scourtaud

Joined: 30 Nov 2005
Posts: 6
:
Location: Paris, France

Items
PostPosted: Fri Dec 23, 2005 2:08 pm    Post subject: Reply with quote

Hi,

Thanks for your reply...

I'm not yet at created an incomplete grid and publish it to be solved... I first want to create a full and valid grid. Once I get good success rate on doing this, I'll wonder about removing cells to publish it...

So my problem is only at setting a complete grid.

Could you point me to the thread you are talking about because I don't recall it...


Thanks


Sebastien
Back to top
View user's profile Send private message
Bo

Joined: 02 Sep 2005
Posts: 27
:

Items
PostPosted: Fri Dec 23, 2005 3:18 pm    Post subject: Reply with quote

Look at the thread:
http://www.setbb.com/phpbb/viewtopic.php?t=234&mforum=sudoku
Also scan through the other threads in "Setting sudoku" (they are not
so many).

Bo
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
Page 1 of 1

 
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