View previous topic :: View next topic |
Author |
Message |
| lacktose
| Joined: 04 Dec 2008 | Posts: 3 | : | Location: Canada | Items |
|
Posted: Thu Apr 23, 2009 9:02 pm Post subject: A program to detect guesses |
|
|
I'm looking for a program that would:
1. take as input a sudoku puzzle and a series of solution steps
2. go through those steps in order and determine if guessing was involved
3. output something that would tell me whether or not the solution is based on logic
It's an interesting problem. I suppose at each step the program would have to cycle through each technique, apply it to the current state of the puzzle, and see if it could yield the same clue as the solution step.
Does anything like this exist? Can any of the solvers out there do this? Can anyone program such a thing? |
|
Back to top |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Fri Apr 24, 2009 10:16 am Post subject: Re: A program to detect guesses |
|
|
lacktose wrote: | Can any of the solvers out there do this? |
I think many solvers posted here can do this, and a lot of them are free. Just look in the "Software" section.
My suggestion: "HoDoKu"
Or my own program (not as powerfull as HoDoku): "MPQ Sudoku"
EDIT: "It turned out that I misunderstood the question, sorry..." see later posts... _________________ Marc
~~~<><~~~<><~~~<><~~~<><~~~
Last edited by Lunatic on Sun Apr 26, 2009 10:05 pm; edited 1 time in total |
|
Back to top |
|
|
| hobiwan
| Joined: 11 Feb 2008 | Posts: 83 | : | | Items |
|
Posted: Fri Apr 24, 2009 12:24 pm Post subject: |
|
|
lacktose,
I personally doubt that what you try to do is possible. I believe (although there is no prove for it) that any elimination or placement can be expressed as some kind of Forcing Net. That said: The output of your program would depend entirely on the strength of the implemented algorithms (I have seen really good sudoku players come up with steps, HoDoKu for example would not find - those would be qualified as guesses when using my program as a measurement). On the other side an average player would probably not be able to come up with steps that many programs available can compute - their guesses would go unnoticed. |
|
Back to top |
|
|
| lacktose
| Joined: 04 Dec 2008 | Posts: 3 | : | Location: Canada | Items |
|
Posted: Fri Apr 24, 2009 2:23 pm Post subject: |
|
|
Thanks Lunatic and Hobiwan, I appreciate your feedback.
The background to this is that I programmed a sudoku game that keeps scores, and I want to disqualify players that cheat.
I'm assuming that cheaters will use a basic solver to generate a complete solution and then fill the game's solution cells in an unnatural order. So I keep track of the steps that players enter their solution and analyze those steps later (manually) if I want to investigate someone.
I only need to consider human techniques, because non-human techniques must come from cheating. |
|
Back to top |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Fri Apr 24, 2009 2:39 pm Post subject: |
|
|
REMOVED (see next post) _________________ Marc
~~~<><~~~<><~~~<><~~~<><~~~
Last edited by Lunatic on Fri Apr 24, 2009 3:13 pm; edited 1 time in total |
|
Back to top |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Fri Apr 24, 2009 2:55 pm Post subject: |
|
|
lacktose wrote: | I only need to consider human techniques, because non-human techniques must come from cheating. |
Well, that's thin ice, it all depends on the skill of the solver.
But, i get it now, you want some sort of program that scans the solving process of a human solver to determine if he made a step that wasn't based upon (human) logic, so you can proof that the solver somehow has cheated. In that case, you need a solver to log ALL possible steps on each step. It can be done, but how far will you go ? What solving techniques are you considering 'human'.
IMHO, i would make a difference between using pencilmarks or not.
Without pencilmarks, one must be able to solve hidden singles, naked singles, locked candidates, and maybe small hidden or naked subsets. _________________ Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
Back to top |
|
|
| daj95376
| Joined: 05 Feb 2006 | Posts: 349 | : | | Items |
|
Posted: Sat Apr 25, 2009 1:56 am Post subject: |
|
|
lactose: I think you're trying to push sand uphill.
I provide puzzles to member of the DailySudoku forum, and I'm amazed at the solutions many of them find manually.
One particular technique they use is to take a useless XY-Wing and extend one or both of the pincer cells to (effectively) produce a 4/5-cell XY-Chain that is useful. They will also take a useless XY-Wing and transport one endpoint to a strong link in another unit and turn it into something useful. Some take useless W-Wings and useless M-Wings and perform similar operations on them.
Bottom line: You'll have a difficult time duplicating their logic for perfectly legitimate eliminations. |
|
Back to top |
|
|
| hobiwan
| Joined: 11 Feb 2008 | Posts: 83 | : | | Items |
|
Posted: Sat Apr 25, 2009 12:40 pm Post subject: |
|
|
Firstly: I think daj95376 made an important point. A check like you described could probably only detect cheaters among average sudoku players who think that a naked triple is the most advanced technique that will ever be needed.
Secondly: Lunatic's remark about pencilmarks is imortant too. Does your program support pencilmarks or not?
Thirdly: When solving for speed, guessing is a time honoured solving strategy, so a few guesses should be allowed.
That said: If we assume that your program uses pecilmarks and that you want to apply the check to not too hard puzzles, you would need to check, whether an elimination or a placement could have been done using a restricted set of techniques. That doesnt sound too hard. |
|
Back to top |
|
|
| strmckr
| Joined: 24 Apr 2009 | Posts: 52 | : | | Items |
|
Posted: Sat Apr 25, 2009 12:55 pm Post subject: |
|
|
i think its evern worse then that, i play on many sites and have been acused of cheating as well.
and banned.
or restricted as a result.
i use very advance techniques manually with out pms.
i also can use symetrical assertion and other ones not coverd anywhere.
guessing should be allowed.
the speed players are quoted using nothing more then an x-wing
and guess and test mehtods to win there competions
the puzzles in question have little to no depth.
guessing can assert a
back door
and leave all singles.
many puzzles have a back door size 1/0 for competions.
which can make it implossible to tell anything from the solution path.
it does come down to the skill of a player to what htey can use, but its another question to figure out what htey are doing in the first place with out physically watching them or haveing them explain the logic.
ie, odd ordered assertion that people dont like either..
how can you back trace any sequece of movs if you dont get the logic that implented them in the first place.
or understand that i can start one move paritally complete it and notice somethign else and go to that then jump back to the starting move at some random point?
and people can make very educated guess using ur's and ur 1.1 that are naked and hidden sets.
for examples..
from my discussion on it form other sites.
sudoku-champions.ca
/forum/index.php?topic=39.45
Quote: | Quote
there are many steps in your explanation which are missing
there is no step missing that i am aware of.
typos yes as you have pointed out thank you.
Quote
those deductions which you have made, you have described them in a backwards order
in your presepective perhaps, but not in mine explained below with detail on them.
Quote
I think you have to respect the task of seeing a cheating play, and make an effort to enter the digits in the logical order; otherwise, it's impossible
not imporabable, depends on the view of the solver. order and resolution path is dependant on the solver.
how can you desern or imply there has to be some kind of ordered sequence of steps : if i use a move and back fill in using logic and you cant figure it out? {as you have}
yes i respct the task of identifying a cheater, i dont approve of the current models that is all.
Quote
Well yes, but it has to start with r78c6=(79), then r8c45=(34).
no it does not have to start with 79 then 34
the givens for the three postions i list are 346789 (these are seen directly at R7C45 and r9C4 has 1346789 as givens
thus its a triple no matter what. (the digits all three spots are not seeing are 1-25!)
it is directly given befor the singles and after the singles.
Quote
You have to notice the r8c1=(1) and r7c1=(6)
no all you need is the 1.
that leaves pms as this
259 (R9C1)
29 (R9C3)
29 (r7C3)
25(R9C4)
xyz smashes the rest.
fill in any order you wish. (does it need an order to look logic?/, i dont think so when its the cells begin used)
and you can add in the 6 afterwards it a single either way.
Quote
(not r1c2!). You mean R7C1=(6),R2C3=(4).not r1c8!)
thaks for catching the typos, i'll have to correct those.
Quote
R8C9<6>,R8C8<2>,R8C7<5>" in the wrong order,
and how do you figure its the wrong order?
if r2C9 is 5 R8C7 is 5. (there is no other place for it on the row8!)
which means row r8c7 is 2 (no other place on the row8!)
and 8c9 is 6.
now resolve it. i find it easier to back track.
6=> 2 => 5
or you have your view.
r2C9 => 6 => 5 => 2
can see it can be resolved in many diffrent ways?
order doesnt matter its perspective that differs.
Quote
How do you know that the 7 and 9 are in c2 and not in c1?
look at box 1.
these are the pms for the spaces in question.
r2C1 {28)
R1C2 {29}
R3C2 {279}
the hidden pair solves r2C9 as 5 which intern directly solves row8
as
6(R8C9)
2(R7C8)****
5(R7C7)
we have a pair of 28(R2c8)
that is connected to the r7c8.
thus box 1 solves.
Quote
Also, you talk about the ur of (13) but you don't even mention that it makes the (5) at r5c6...
how did you remove the
2 at r5c6 ?
give the state of the grid befor the ur reductions? (the ur only removes 1&3)
this is the grid at the state befor the ur.
|.95|7.4|...
|214|936|785
|.76|...|..4
|---+---+---
|..8|...|.5.
|...|.9.|.7.
|.5.|.7.|..2
|---+---+---
|632|..7|.4.
|187|349|526
|549|268|317
i see a naked triple in box 5 (123) in R4c56+R6C6
that can be used to make it a single 5.
but not the ur.
Quote
I am intrigued by the idea that you solve this by seeing hard things first, which lead you to a more direct solution
i got bored along time ago on easy puzzles and figured id make them harder by only solving them with harder move sequences.
and in doing so i discoverd that they can be condensed quicker.
but it is a gamble, just like n e other method to solve is.
how do you pick the right tool to start with is the question. |
|
|
Back to top |
|
|
| JasonLion
| Joined: 16 Nov 2008 | Posts: 62 | : | Location: Silver Spring, MD | Items |
|
Posted: Sat Apr 25, 2009 4:41 pm Post subject: |
|
|
To expand on what strmckr is saying, to detect "cheating" you need a fully specified model of exactly what "cheating" actually is. In practice, that means you need a fully specified model of what "not cheating" means. If you can completely specify exactly what the player is "allowed" to think and which techniques they are "allowed" to apply, then yes you can do what you want.
In the real world, advanced players will always do things that you have not made provisions for. New techniques are discovered all the time. Only if you specify that every move must be made using a technique from a fixed list of techniques can you actually detect "cheating". |
|
Back to top |
|
|
| strmckr
| Joined: 24 Apr 2009 | Posts: 52 | : | | Items |
|
Posted: Sat Apr 25, 2009 6:58 pm Post subject: |
|
|
Quote: | Only if you specify that every move must be made using a technique from a fixed list of techniques can you actually detect "cheating". |
and the technique used
most be made in whole
(ie every filled cell form the same move must be filled in isntead of partial)
and your program must also realize that varations of implementing the deductions can be used. |
|
Back to top |
|
|
| daj95376
| Joined: 05 Feb 2006 | Posts: 349 | : | | Items |
|
Posted: Sun Apr 26, 2009 4:19 pm Post subject: |
|
|
Okay, from the responses, it seems that guessing, technique choices, and technique order are not going to be something you can use to detect cheating -- which is what you're really after. So, how do you go about foiling cheaters?
To me, it seems that a manual player would take erratic times between moves as (s)he finds and performs eliminations. Whereas, once a cheater has solved the puzzle, (s)he would enter eliminations as quickly as possible in order to win. If rhythmic times between eliminations occurs over a sequence of puzzles, then there's a good chance a player is cheating.
You might also consider requiring that all initial Singles be resolved before any other technique can be applied. A cheater might enter the Singles in a straightforward order instead of an order consistent with when each single is exposed if performed manually. Of course, if your program displays cell candidates, then this approach wouldn't be useful.
In any event, after the initial Singles have been completed, a cheater would likely try to enter additional eliminations as quickly as possible. Analyzing the time between eliminations might be very effective now. Even an advanced player is going to have a jerky time between eliminations as (s)he locates patterns and determines if they are useful. |
|
Back to top |
|
|
| strmckr
| Joined: 24 Apr 2009 | Posts: 52 | : | | Items |
|
Posted: Sun Apr 26, 2009 6:25 pm Post subject: |
|
|
variance in time betweeen techniques is an option
the first x many moves of a puzzle if solved in the order of all singles first followed by harder tehcniques.
the solver could solve first x many moves in so much time
then a delay and solve the end of the puzzle in 60% faster time then the intial solving.
remember they are on a unfll puzzle vrs a almost finished.
the problem is then again.
if some one drops a single in that is a back door.
they could essentially solve the puzzle wiht a flat consitance speed
but still display an increase of speed as the puzzle is incrementalyl filled in.
a list of all back doors is also required.
as daj suggest an assortment of records ovre a long period of time could suggest cheating but still not guarentee they are.
stiff requirments on a specific solving order would also be a joke.
a cheater with a program
would know the exact order to solve in
but are they smart enough to use it in a human like model
they could be.
or they just drop in the specific order and win.
and
you wouldnt know the diffrence either way.
heres a way to detect it.
but its privacy invasive and illegal in many places.
write a script that tells you exactly what windows are open on the computer at the time of solving.
it should be only 1.
the site where the game is on.
this does not stop muti accounts
nor does it stop muti computers.
but its a thought. |
|
Back to top |
|
|
| lacktose
| Joined: 04 Dec 2008 | Posts: 3 | : | Location: Canada | Items |
|
Posted: Mon Apr 27, 2009 5:09 pm Post subject: |
|
|
First, to answer the questions... my sudoku game does have pencilmarks, does not display cell candidates, and right now we have no explicit rule about guessing. We have puzzles ranging from Easy to Very Hard (which can have Forcing chains or Nishio).
JasonLion wrote: | If you can completely specify exactly what the player is "allowed" to think and which techniques they are "allowed" to apply, then yes you can do what you want. |
I think you nailed it here. Unfortunately, if you want to design a workable automated anti-cheating system there's gonna be tradeoff. Advanced sudoku players like strmckr might use educated guesses and crazy techniques like extending x-wings, but I think we'd have to classify that as "cheating". Some people might not like it, I think it's more important to prevent the scoreboards from being taken over by people using software.
So maybe this could be a list of acceptable techniques:
* Cell only has one number in it
* Number only appears as candidate once in a row, column or block
* Number appears in a specific row or column within a block
* Number only appears in one block in a row or column
* Number appears in two blocks, twice, in the same row or column
* Number pairs
* Number chains
* Hidden number pairs
* Hidden number chains
* X-Wing
* Y-Wing
* Swordfish
* Fishy Cycles
* Colouring
* Forcing chains
* Nishio
Unacceptable techniques:
* Guessing or anything else not listed above
The program could take the sequence of steps made by the player and determine the % of those steps that were based on acceptable techniques. Anyone with less than, say, 90% acceptable would be flagged as a cheater.
daj95376 wrote: | In any event, after the initial Singles have been completed, a cheater would likely try to enter additional eliminations as quickly as possible. Analyzing the time between eliminations might be very effective now. Even an advanced player is going to have a jerky time between eliminations as (s)he locates patterns and determines if they are useful. |
This could be another indicator along with the "% acceptable" above. I think a cheater would need some time to enter the puzzle into a solver program, so there would be one slow step. So perhaps I could calculate the variance of time taken on all steps excluding the slowest one. Based on the timing variance numbers we see in the wild, we can set a threshold so that if you don't have enough variance you're flagged as a cheater.
Of course, cheaters that delay using a solver program until later on in the puzzle will have more variance, but I suppose the longer they wait the less of a problem they pose... I'll start adding code to track the timing of cell entries and report back on what I find in the wild in a few days.
strmckr wrote: | write a script that tells you exactly what windows are open on the computer at the time of solving. |
Unfortunately that isn't possible using Javascript and I don't want to force my users to install any software. |
|
Back to top |
|
|
| strmckr
| Joined: 24 Apr 2009 | Posts: 52 | : | | Items |
|
Posted: Mon Apr 27, 2009 6:26 pm Post subject: |
|
|
basically your asking for:
a solver that can identify these all of these at each phase of solving:
Quote: | singles naked / hidden
x-chains (single digit cycles)
pointing pairs/trips (aka cyclops fish / locked candidates)
pairs/trips/quads (naked & hidden)
X - wings
2-string kytes (these three should be in it)
skyscrapers
sahsimi x-wings
finned x-wigns
Empty rectangle
XY - wings
xyz -wings (i would include these)
w - wings (and this)
swords
UR types 1-6
UR 1.1
xy-chains |
forcing nets/chains (this becoms an issue it requires guessing!!! and they are easy to use at any point in the puzzle)
Are you including degerative cases?
hidden variances of the move sets
if your not time variancs goes out the window.
Quote: | I think a cheater would need some time to enter the puzzle into a solver program, so there would be one slow step. |
yes some time but so small amount its seen as a person looking for a move.
there is a few ways to do it.
i can demenstrate importing a puzzle into a solver in 15 seconds.
manually.
and cycle the solution by x mnay cycles
using hot keys remembering say 5-10 singles at once.
alt tab between windows or have them miniimized and both active so u can read both at once. and simply click between the two.
then is a matter of ploting the order out pausing to find the next move
repeat.
looks exactly like a normal person solving.
the other ways are theory:
scrpyt or image reading software the transfers it to the solver for you thats microseconds.
ps... send me a very hard puzzle
i want to get a rating for them and analize the difficulty.
im pretty sure they wont need forcing chains or nisho.
instead of lableing a cheater as you cannt prove it one way or another:
but since you are askign for a tehcniques that can be used from a move set:
i would list them as a : and define it as a player that uses techniques other then those allowed.
ideal lables.
(Trial and error) TE
or (guess & test ) GT
or (andrians thread) AT
{spelling?}
and define that as a perons that uses a move set not inclued by the move sets indicated by your requirements. |
|
Back to top |
|
|
|