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   

A program to detect guesses

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

Joined: 04 Dec 2008
Posts: 3
:
Location: Canada

Items
PostPosted: Thu Apr 23, 2009 9:02 pm    Post subject: A program to detect guesses Reply with quote

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
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Fri Apr 24, 2009 10:16 am    Post subject: Re: A program to detect guesses Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Fri Apr 24, 2009 12:24 pm    Post subject: Reply with quote

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
View user's profile Send private message
lacktose

Joined: 04 Dec 2008
Posts: 3
:
Location: Canada

Items
PostPosted: Fri Apr 24, 2009 2:23 pm    Post subject: Reply with quote

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
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Fri Apr 24, 2009 2:39 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Fri Apr 24, 2009 2:55 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Sat Apr 25, 2009 1:56 am    Post subject: Reply with quote

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
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Sat Apr 25, 2009 12:40 pm    Post subject: Reply with quote

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
View user's profile Send private message
strmckr

Joined: 24 Apr 2009
Posts: 52
:

Items
PostPosted: Sat Apr 25, 2009 12:55 pm    Post subject: Reply with quote

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
View user's profile Send private message
JasonLion

Joined: 16 Nov 2008
Posts: 62
:
Location: Silver Spring, MD

Items
PostPosted: Sat Apr 25, 2009 4:41 pm    Post subject: Reply with quote

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
View user's profile Send private message
strmckr

Joined: 24 Apr 2009
Posts: 52
:

Items
PostPosted: Sat Apr 25, 2009 6:58 pm    Post subject: Reply with quote

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
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Sun Apr 26, 2009 4:19 pm    Post subject: Reply with quote

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
View user's profile Send private message
strmckr

Joined: 24 Apr 2009
Posts: 52
:

Items
PostPosted: Sun Apr 26, 2009 6:25 pm    Post subject: Reply with quote

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
View user's profile Send private message
lacktose

Joined: 04 Dec 2008
Posts: 3
:
Location: Canada

Items
PostPosted: Mon Apr 27, 2009 5:09 pm    Post subject: Reply with quote

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
View user's profile Send private message
strmckr

Joined: 24 Apr 2009
Posts: 52
:

Items
PostPosted: Mon Apr 27, 2009 6:26 pm    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming 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