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   

how to best control difficulty?

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

Joined: 21 May 2006
Posts: 1
:

Items
PostPosted: Sun May 21, 2006 11:20 pm    Post subject: how to best control difficulty? Reply with quote

I've been scanning this forum, but I havn't found much in the way of creation, beyond
add one hint -> apply solver, or
subtract one filled square -> apply solver.

I've been tinkering with a modification to the subtraction method, with some success. What I'd like to know is,
is it old hat? just plain wrong?

Here it is, in broad terms:
I'll assign a difficulty to each solving technique for reducing a square's candidates. Based on the puzzle's desired difficulty rating, a difficulty for each square will be preferred by the algorithm.

step 1: choose remove a random remaining square (the difficulty of each square could be calculated, but that would take more time)

step 2: check conditions a, and b, see below (each square will store an array of its candidates, so checking b will be easy).
- if condition a is true, the square should be removed, regardless of desired difficulty

step 3: add the value of the random square as a candidate for ALL of its neighbors (squares in the same row, col, or box).

step 4: using standard solving techniques*, try to eliminate all of the candidates added in step 3.
-apply methods from easiest to hardest, and if successful, keep track of the difficulty required.

*locked candidates, naked/hidden groups, etc.

step 5: test condition c.
-if invalid, remove the rest of the candidates added, and mark the square as a final clue.
-if valid, check the highest difficulty technique needed against the desired level for the square. If too high or too low, store the location of the square as a potential, and try to find a better one.

step 6: once all remaining squares are marked as final, it's done.


Other subtraction methods I have found are slightly different: they remove one square randomly, then apply a full blown solver algorithm to make sure the removal was valid.

Mine may possibly leave room for multiple solutions or an unsolvable puzzle, but I can't see how yet.


Above, I refer to
a square may be removed when one or more of the following apply:

a -it is a member of a filled row or column or box

b -removing it would leave it with only one candidate

c -removing it would make it a candidate for another square in its row AND column AND box.

These are, as far as I can determine, the only way to legally remove a square.

How does it look?
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