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   

User-friendly internet only solver at sudokusolver.co.uk
Goto page Previous  1, 2, 3  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Software
View previous topic :: View next topic  
Author Message
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Tue Jul 26, 2005 6:59 am    Post subject: Re: XY-Wing Reply with quote

mathrec wrote:
The XY-Wing is a particularly easy logical loop to search for by hand. I appreciate that you've given it a name.


I didn't invent the name, it was originally proposed here.

mathrec wrote:
The XY-Wing is a special case of the exposed loop, depending only on simple elimination.


I would say the opposite is true: XY-Wing is more general.

mathrec wrote:
The challenge2 puzzle is not so kind. There are no exposed loops in that puzzle, since there are no wx-xy-yz pivots at all.


The challenge2 can be solved using several double forcing chains. It is solvable without backtracking, but definitely very hard for a human.
Back to top
View user's profile Send private message
antony

Joined: 22 Jul 2005
Posts: 13
:

Items
PostPosted: Fri Jul 29, 2005 4:33 am    Post subject: generic method D Reply with quote

I would suggest a new, more generic phrasing for Method D :

Look for N digits that are candidates in only N cells of a group ("unique subset"). Then the N digits must be in the N cells, and you can remove other candidates from those N cells. And similarly:
Look for N digits that are the only candidates in N cells of a group ("disjoint subset"). Then the N digits must be in the N cells, and you can remove those N digits from other cells in the group.

Example:
123 - 123 - 234 - 456 - 45 - 56 - 7 - 8 - 9
The two aspects of the rule help removing the 4 in the third cell:
1,2,3 appear in the first three cells only (unique subset) -> 4 can be removed in those cells
Only 4,5,6 appear in the last three cells (disjoint subset) --> 4 can be removed in the other cells
Back to top
View user's profile Send private message
daveliney

Joined: 29 Jul 2005
Posts: 1
:

Items
PostPosted: Fri Jul 29, 2005 11:07 pm    Post subject: Over-eager method F mistake? Reply with quote

Starting with:

Code:
9     | 1   7 | 5 2 8
  7   | 5   2 |   4 
  5 2 |   9   | 7 6 
------+-------+------
    4 |   5   | 8 1 7
5 8   |     1 | 2 9 6
  9 1 |   2 8 | 3 5 4
------+-------+------
    5 |   1   | 6 3 
  6   |     5 |   7 
3 1   | 2   6 |   8 5


9__1_7528+_7_5_2_4_+_52_9_76_+__4_5_817+58___1296+_91_28354+__5_1_63_+_6___5_7_+31_2_6_85

the solver starts using Method F and four steps in says:

"Found a double match for 8 in columns 3 and 5 and columns B and H
.. Removing number 8 from [B1] using Solve Method F"

However setting B1 to 8 does not cause there to be no possible values for all of B3, B5, H3 and H5. For example:

Code:
9     | 1   7 | 5 2 8
8 7 3 | 5 6 2 |   4 
  5 2 |   9   | 7 6 
------+-------+------
    4 |   5   | 8 1 7
5 8   |     1 | 2 9 6
  9 1 |   2 8 | 3 5 4
------+-------+------
    5 |   1   | 6 3 
  6 8 |   4 5 |   7 
3 1   | 2   6 |   8 5


As it turns out those values don't work but not for reasons that Method F was looking for, as I see it.

The problem seems to be that in the cycle of four cells there are five unique entries available (34689). Is this a problem with Method F, or is my logic off?
Back to top
View user's profile Send private message
mathrec

Joined: 15 Jul 2005
Posts: 10
:
Location: Carlsbad, CA

Items
PostPosted: Thu Aug 11, 2005 12:41 am    Post subject: Reply with quote

Quote:
However setting B1 to 8 does not cause there to be no possible values for all of B3, B5, H3 and H5. For example:

Code:
9     | 1   7 | 5 2 8
8 7 3 | 5 6 2 |   4
  5 2 |   9   | 7 6
------+-------+------
    4 |   5   | 8 1 7
5 8   |     1 | 2 9 6
  9 1 |   2 8 | 3 5 4
------+-------+------
    5 |   1   | 6 3
  6 8 |   4 5 |   7
3 1   | 2   6 |   8 5

It does, however, cause there to be no place for an 8 in column 5. That's what X-Wings (AKA Solve Method F) does. It identifies situations where a choice like B1=8 would cause one of columns 3 or 5 to have no place for an 8.
Back to top
View user's profile Send private message Visit poster's website
karat

Joined: 14 Aug 2005
Posts: 1
:

Items
PostPosted: Sun Aug 14, 2005 12:28 pm    Post subject: Reply with quote

Karat

I think that the solution is toyour chalenge (http://www.sudokusolver.co.uk/challenge.html)
is simply that you missed a hidden chain on row E7, E8,E9 (49,24,(1)29)
so you have a 1 at E5 and then you can solve the puzzle. Sorry I can't code it (I didnt't wrote a line of code in 15 years).

Reuben
Back to top
View user's profile Send private message MSN Messenger
arsoncupid

Joined: 22 Nov 2005
Posts: 10
:

Items
PostPosted: Tue Nov 22, 2005 5:16 am    Post subject: illogic puzzle 14 Reply with quote

I've solved illogic puzzle #14 by hand. It did involve one guess, so this won't provide a new logical method by itself. But, puzzle 14 was listed as having 4 guesses required. With only one guess required, solving the puzzle could be simplified to solving for this one square.

The absolute middle square is either a 2 or a 3 (just from finding the givens and simplifying with mundane methods). By guessing a 2 in that square, and working into the upper and lower middle boxes (3x3). then out left from those, an inconsistency is found: an 8 in the second row in both the top and bottom boxes.

So, that middle-most square must be a 3. From there simple logic completes the puzzle.

Your logic program correctly solves the puzzle with only the 3 added to the starting arrangement.

...

When solving it by hand, I opted to guess the absolute middle square because the entire middle column of boxes are almost exclusively populated with 2's and 3's -- a lot would resolve from guessing this square.

I guessed a 2 after looking a couple levels deep into both the 2 and 3 guess ... after the 2 showed it was more quickly fruitful. Usually, for me, the branch with more resolution is the more likely to fail.
Back to top
View user's profile Send private message
arsoncupid

Joined: 22 Nov 2005
Posts: 10
:

Items
PostPosted: Tue Nov 22, 2005 6:41 pm    Post subject: Re: illogic puzzle 14 Reply with quote

arsoncupid wrote:
By guessing a 2 in that square, and working into the upper and lower middle boxes (3x3). then out left from those, an inconsistency is found: an 8 in the second row in both the top and bottom boxes.


I meant the second column, not row. arg
Back to top
View user's profile Send private message
arsoncupid

Joined: 22 Nov 2005
Posts: 10
:

Items
PostPosted: Tue Nov 22, 2005 8:45 pm    Post subject: Method E Reply with quote

I've been looking at your site some more ... your Method E is the method I describe above, I think, that excludes the 2. I've found this is called Nishio here, and I believe it is a generalized algorithm applicable in many different problems.
Back to top
View user's profile Send private message
melvincutter

Joined: 23 Dec 2005
Posts: 1
:

Items
PostPosted: Fri Dec 23, 2005 11:49 pm    Post subject: This is correct but you are missing 1 thing... Reply with quote

I found this site yesterday and figured out the formula for problem 1 last night. This response seems to be the closest to accuracy but one point needs to also be added.

He/She said:

"In general:
- Find a locked pair {xy}.
- Find two cells forming a square with the locked pair, one containing {zx} and one {zy}.
- Set the cell of the pair next to {zy} to {x} and the other one to {y}."

However, it must also be noted that {zx} and {zy} are the only possibilities that {z} can be; i.e. {z}cannot go anywhere else within the 3X3 box.
Back to top
View user's profile Send private message
InsaneProdigy

Joined: 29 Dec 2005
Posts: 1
:

Items
PostPosted: Thu Dec 29, 2005 6:31 am    Post subject: Remote Pairs Reply with quote

Someone may have already brought this up but the method described in "Solve Method E Explanation - by Mark Summerville" can be simplified some to solve that puzzle.

Rule: No cell that lies at the intersection of two cells that form an exclusive pair on a single number may contain that number.

Considering only the number 7 we find:

1A & 1H are exclusive on 7 (i.e. only one or the other can be a 7)
1H & 4H are exclusive on 7 (i.e. only one or the other can be a 7)
4H & 6G are exclusive on 7 (i.e. only one or the other can be a 7)

therefore 1A & 6G are exclusive on 7 (i.e. only one or the other can be a 7)

therefore 6A (the cell at the intersection of row A and column 6) may not contain the value 7 and must in fact be a 6. Your solver finishes this puzzle once that cell is resolved.

Roughly, the pseudocode would be:

1. For each cell:
A. For each possible value:

i. Check the row/column/box for the current cell to see if there is an exclusive pair (i.e. only 2 valid positions for the current value)
ii. Increment the step counter.
iii. If the step counter is even then this is an exclusive pair with the original cell. The current value can be excluded from the intersections of the base cell and the current cell.
iv. Using this new cell repeat steps i. - iv. until no new exclusive pair can be found.
Back to top
View user's profile Send private message
ednotover

Joined: 12 Jan 2006
Posts: 1
:

Items
PostPosted: Thu Jan 12, 2006 11:28 pm    Post subject: Reply with quote

I see method E somewhat differently. I see it as a way to evaluate consistency of "fallout" trees when there's cyclical group overlap.

As Mark defined them, cyclical groups would just be sets of cells with related number pairs. However, it helps also to consider groups of three cells where two of the cells are pairs with a single shared number and the third is a triple of the numbers from the first two cells. This second type of grouping is determined completely if the number appearing in all three cells is chosen in any of those cells, or if any number is chosen in the cell with the triple.

(A1, A6, A9)
(H2, H3)
(H6, H7, H8)
(A1, H1)
(C4, D4, H4)
(A6, C4, C5)
(G3, H1)

By bringing those together where there's cell overlap, we have:

(A1, A6, A9) + (A1, H1) + (A6, C4, C5) + (G3, H1) + (C4, D4, H4)

(H2, H3)

(H6, H7, H8)

We need to evaluate only the first grouping, since the other two involve only a single group (there's no opportunity there for inconsistencies).

We simply check the possible values for the first cell in each evaluated grouping, and see what the fallout is. Build out the trees until all determinable cells in the grouping have been computed, or until an inconsistency is discovered.

Code:

A1: 1
  |
H1: 7
  +--------+
G3: 1    H4: 1
  |        |
G5: 6    D4: 3
  |        |
C5: 3    C4: 7
  |        |
A6: 6    A6: 6
  |        |
A9: 7    A9: 7


That's consistent; the only duplicated cell computations are A6 and A9, and the computed values agree.

When setting A1 to 7:

Code:

A1: 7
  +---------------+
H1: 1            A6: 6
  +--------+      |
G3: 7    H4: 7   C5: 3
           |      |
         C4: 3   C4: 7


It's inconsistent; the different branches of the A1: 7 fallout gave two different values for C4.

So A1 cannot be 7.
Back to top
View user's profile Send private message
Olliminatore

Joined: 10 Feb 2006
Posts: 3
:

Items
PostPosted: Fri Feb 10, 2006 6:48 am    Post subject: Grid Illogical 8, ordinary solved Reply with quote

Hello and greetings, I'm very new here.

I found a method to solve the Grid 8. (From the Illogical "Can't Solve By Logic".) Although this Method is (very) easy. It is also not included in the "Simple Sudoku" program by Angus.

I don't know how this method/technique is named, but I think it has already one.

Explanation: If a "nacked pair" appear in two boxes you can exclude bot numbers in the intersection of row and line.
Code:
8   3 |   2 9 | 7   6
    6 |   1 8 | 5   
      |   6   |     
------+-------+------
    5 |   4   |   8 
7   9 |   3   | 6   2
  6   |   9   | 1   
------+-------+------
      |   7   |     
    1 | 6 5   | 8   
5     | 9 8   | 4   3

In this grid the "nacked pair" 37 appear in R2C4; R6C8, so it can exclude the 3 on R2C8.

And then the riddle is complete solvable by ordinary method A/B.

How is the name of it? (or perhaps a new?) Smile

[edit] img+
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Feb 10, 2006 4:14 pm    Post subject: Reply with quote

There is no name for this technique.

Maybe because it does not work.

If it works in your example, then it could be called a lucky guess.

A naked pair must be connected in some way. The cells you show will not connect these 2 cells. If they would, they you would have remote pairs, a known technique.

If I am missing something, please explain carefully how your technique works. Currently I do not see it working.

Greetings, and welcome to the forum,

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

Joined: 10 Feb 2006
Posts: 3
:

Items
PostPosted: Fri Feb 10, 2006 6:08 pm    Post subject: Reply with quote

Hello Ruud,

Yes you are right this method is'nt so easy as i thought and it worked not exactly as i explained. It seems (very) rare and lucky but not guessy.

In the 37 pair can not occur the 7 concurrently, so it must a 3 in the fields and I can exclude the 3 on R2C8.

Ok let depict (declare): It is like a "nacked box pair" which i can exclude a number in the row/col intersection, if I know that be the other number in this pair can't occur concurrently.

Thanks for (future) name suggestion. Smile
_________________
Germany
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Feb 10, 2006 6:42 pm    Post subject: Reply with quote

I took another look at your method, and I do see how it works, now. My previous answer was too quick.

The center box has 3 candidates for digit 7. No matter which of these candidates is placed, it will always result in the elimination of 7 in one of those {3,7} cells, which in turn eliminates the 3, forcing BOTH cells in your pair to 7.

it may be difficult to describe this pattern in terms other than trilocation-implication-chains. The elimination of the 3 would then be a verity or veracity (names coined by MadOverlord).

I do not think this will occur often enough to deserve its own name, but I may be mistaken. A lot of new techniques have been named at the players forum.

Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Software All times are GMT
Goto page Previous  1, 2, 3  Next
Page 2 of 3

 
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