The New Sudoku Players' Forum

[QBasicMac]

> if clever guys like you cant understand each other

Actually, I'm sure the other two understood each other quite well, and I am also a newbie. But maybe that is an advantage re: your question.

Assume you are solving some puzzle and you have somehow discovered that the only empty cells on row 4 that can contain a 9 are in columns 3 and 8. Hmmm, you think - maybe I have an X-Wing here. So you look down and notice that in row 7 the cells in these columns are empty. Hmmm, you think - progress!.

You then study row 7 to see whether indeed those are the only cells on that row that can contain a 9.

Case 1: YES!. You found one.
Case 2: NO!. There is no X-Wing here.

So you know what an X-Wing is and how to find one. The next question is "So what?"

Well, in case 1 you must see that you have just proved that there are no 9's in any cell in columns 3 and 8 (other than in opposing corners of the X-Wing.) That is often the clue needed to fill a cell elsewhere.

In case 2, you have made no progress. You don't know whether the 9 falls in column 3 or 8 so you can't eliminate anything.

For example, imagine you have found that in row 1, the only cells that can contain a 9 are in columns 1 and 3.

In case 1, you know to immediately put a 9 in row 1 column 1 - right?
In case 2, you know nothing. It could be in either column.

And here is where expertise comes in: Suppose there is indeed an X-wing as described. If you did not know how to recognize it, you would not know to put the 9 in r1c1. You would be stumped.

The diagram on the left is a visualization of the above discussion.

Code: Select all

9 - 9  - - -  - - -      - - -  - - -  - - -
- - -  - - -  - - -      - - -  - 9 -  - - -
- - -  - - -  - - -      - - -  - - -  - - -

- - 9  - - -  - 9 -      - - -  - - -  - - -
- - -  - - -  - - -      - - 9  - 9 -  ? - -
- - -  - - -  - - -      - - -  - - -  - - -

- - ?  - - -  - ? -      - - -  - - -  - - -
- - -  - - -  - - -      - - 9  - - -  ? - -
- - -  - - -  - - -      - - -  - - -  - - -


It was based on finding two cells on a ROW that were the only two cells that could contain a certain digit (9 as an example)

The diagram on the right shows an X-Tree based on finding two cells in a COLUMN. Same logic, just rotated. Note in that diagram that if it can be shown that the two question marks could contain a 9 but no other cell in that column could (and if you were clever enough to notice that) then the 9 in r5c5 can be eliminated and thus you can fill in cell r2c5 with confidence.

IMHO

Mac

[scrose]

just how to find/identify an x-wing??

I will attempt to, step-by-step, explain how to identify an x-wing. There are two challenges to identifying an x-wing, especially when playing on paper.

• Having a correct set of pencilmarks is crucial. Make sure you haven't accidentally eliminated candidates that cannot be eliminated. Similarly, sometimes an x-wing doesn't appear until all possible placements/eliminations have been made.
• When do you start looking for an x-wing? This is very difficult to answer. I find it comes down to experience: once you are sure that the puzzle has reached at point where no more placements/eliminations can be made, start looking candidate-by-candidate for an x-wing.
  

In the list of steps I wrote above, enough eliminations have been made after step #6 that an x-wing has appeared in the candidate 6's. As I noted above, the first six steps are likely the fastest way to reach the x-wing in the candidate 6's. However, there are still other placements/eliminations that can be made which do not affect the x-wing: r2c1=3, r3c2=5, r8c2=3, r7c5=1, eliminate candidate 8's from r2c8, r2c9, r7c7, and r7c8, eliminate candidate 9's from r8c1 and r8c9. If you do not understand how the first six steps were made, or how I made these additional placements and eliminations, you are not ready to tackle x-wings: you should study, understand, and master the simpler techniques (such as candidate restrictions, pairs, triples) before attempting puzzles that require advanced techniques (such as x-wing, swordfish, colouring, forcing chains).

I will begin after step #6 has been applied. The candidates now appear as follows.

Code: Select all

 . . . | . . . | . . .     2 2 . | . . . | . . .     . . . | . . . | . . .
 . . 1 | . . . | . . 1     . . . | . . . | . . .     3 . . | . . . | . 3 3
 . . 1 | . . . | 1 . 1     . . . | . . . | . . .     . 3 . | . . . | 3 3 3
-------+-------+-------   -------+-------+-------   -------+-------+-------
 1 . . | . . 1 | . . 1     . . . | 2 . . | . 2 2     . . . | 3 . . | . 3 3
 1 . . | . 1 1 | . . 1     . . . | . . . | . . .     . . . | 3 . . | . 3 3
 1 . . | . . 1 | 1 . 1     . . . | 2 . . | . 2 2     . . . | . . . | . . .
-------+-------+-------   -------+-------+-------   -------+-------+-------
 . . . | . 1 . | . . .     2 2 . | . . . | . 2 .     . . . | . . . | . . .
 . . . | . . . | . . .     2 2 . | . . . | . . 2     3 3 . | . . . | 3 . 3
 . . . | . . . | . . .     . . . | . . . | . . .     . . . | . . . | 3 3 3


 . . . | . . 4 | . 4 .     . . . | . . . | . . .     6 6 6 | . . 6 | 6 . .
 . . . | . . . | . . .     . . . | . . . | . . .     . . 6 | 6 . . | . . .
 . . . | . 4 . | . 4 4     . 5 . | . . . | . . .     . . 6 | . . . | 6 . .
-------+-------+-------   -------+-------+-------   -------+-------+-------
 4 . 4 | 4 . 4 | . . .     . . . | . . . | . . .     6 6 6 | . . . | . 6 .
 . . . | . . . | . . .     5 5 . | . . . | . 5 .     6 6 . | . . . | . 6 .
 4 . . | 4 . 4 | . . .     5 5 . | . . . | 5 5 .     . . . | . . . | . . .
-------+-------+-------   -------+-------+-------   -------+-------+-------
 4 . 4 | 4 4 . | . 4 .     . . . | 5 . . | 5 5 .     . . . | . . . | . . .
 4 . . | 4 4 4 | . . 4     . . . | . . . | . . .     6 6 . | 6 . 6 | . . .
 . . 4 | 4 . . | . 4 4     . . . | 5 . . | 5 5 .     . . 6 | 6 . . | . . .


 . 7 7 | . . 7 | 7 7 .     . . . | . . . | 8 8 .     9 9 9 | . . . | . 9 .
 . . 7 | 7 7 . | . 7 7     . . . | 8 8 . | . 8 8     . . 9 | . . . | . 9 9
 . . 7 | . 7 . | 7 7 7     . . . | . . . | . . .     . . . | . . . | . . .
-------+-------+-------   -------+-------+-------   -------+-------+-------
 . 7 7 | 7 . 7 | . 7 7     . 8 8 | 8 . . | . 8 8     . . . | . . . | . . .
 . 7 . | 7 7 7 | . 7 7     . 8 . | 8 8 . | . 8 8     9 9 . | . 9 9 | . . .
 . 7 . | 7 . 7 | 7 7 7     . 8 . | 8 . . | 8 8 8     9 9 . | . . 9 | . . .
-------+-------+-------   -------+-------+-------   -------+-------+-------
 . . . | 7 7 . | 7 7 .     . 8 8 | . . . | 8 8 .     9 9 9 | . 9 . | . 9 .
 . . . | 7 7 7 | 7 . 7     . 8 . | . . . | 8 . 8     9 9 . | . 9 9 | . . 9
 . . . | . . . | . . .     . . . | . . . | . . .     . . 9 | . . . | . 9 9

I will immediately focus on the candidate 6's and explain how to identify the x-wing. However, it should be noted that when solving a puzzle I would have to use this identification process for each candidate (unless I luckily decided to examine the candidate 6's first).

Now would be a good time to review the conditions for an x-wing. To paraphrase from angusj's description: Given a specific candidate, the x-wing pattern requires either two rows containing exactly two cells with this candidate in each row, and these candidates must share the same two columns or two columns containing exactly two cells with this candidate in each column, and these candidates must share the same two rows.

It usually doesn't matter if you examine rows or columns first. Personally, in my head, I find it easier to examine columns first. So, to start, I am looking for columns that contain exactly two candidate 6's. It is easy enough to see that columns 6, 7, and 8 each have exactly two candidate 6's. Now I need to check if any of these three columns share the same two rows. Columns 6 and 7 share only row 1. Columns 7 and 8 do not share any rows. Columns 6 and 7 do not share any rows. Because we can't find two columns (that each contain exactly two candidate 6's) that share the same two rows, we cannot find an x-wing by looking at the columns.

So lets look for rows that contain exactly two candidate 6's. It is easy enough to see that rows 2, 3, and 9 each have exactly two candidate 6's. Check if any of these three rows share the same two columns. Rows 2 and 3 share only column 3. Rows 3 and 9 share only column 3. However, rows 2 and 9 share columns 3 and 4! We have found two rows containing exactly two cells with candidate 6's in each row, and the candidate 6's share the same two columns. We have identified the x-wing!

Well, that was a lot of typing. I do hope I haven't made any mistakes, which will only add to any confusion surrounding x-wings. And I hope this helped.

I think the most difficult part of identifying an x-wing is deciding when to start looking: only begin the search once you are sure that no more placements/eliminations can be made by other techniques.

Fixed: Grammar and spelling.

[goldie5218]

hi Scrose, thanks very much for your reply and all the effort you took to
type out and explain the principle of x-wings. i have decided to take your advice and concentrate on making sure i have eliminated every possible candidate, including all the hidden pairs and trips etc. until i am convinced that there is no further progress! then and only then will i look for an x-wing. your decription of how/where to look and identify these weird things finally makes sense to me and now i hope i will eventually find one on my very own - i guess if i stick to doing those puzzles marked as 'x-wing' types i will eventually get to a point where they apply and, if i am on the right track, will begin to identify/find them! ps. have printed your explanation and intend to refer to it while trying to find them - cheers and again thanks for your help!!!!!

[scrose]

Use of the x-wing, swordfish, colouring, and forcing chain techniques should be a last resort only, especially if you are playing on paper. These techniques rely heavily on having a complete, minimal, and accurate set of pencilmarks. If you make a mistake with your pencilmarks, it becomes much more difficult (in some cases, impossible) to apply these techniques.

Of course, it helps greatly if you know that a puzzle contains a x-wing. It is my understanding that The Times (which contains Pappocom puzzles), the Guardian (which contains Nikoli puzzles), and The Daily Telegraph do not publish puzzles that contain x-wings. (Perhaps Wayne can confirm this, and maybe let us know if any of the Pappocom puzzles that are published in newspapers ever contain x-wings.)

The Pappocom software only generates x-wings when creating puzzles rated as "very hard", and from my experience only about half of those will contain an x-wing.

The real challenge is when you have no knowledge of how difficult a puzzle is rated, or where the puzzle came from. It might contain an x-wing, maybe it has a swordfish, maybe it has both, or maybe neither but requires colouring instead. These can be the most frustrating puzzles to solve because it is such tedious and time-consuming work to examine the pencilmarks.

[QBasicMac]

What am I? Chopped liver? My reply was summarily ignored by all.

LOL - Actually I don't care about that. The reason I am posting is to say that I have never used the "pencilmarks" technique. It is interesting and thus I am off on another program-writing effort.

Just as "guessing" is frowned upon in this clique, using a language other than QBasic (DOS) is frowned upon in my clique. But I am going to use Visual Basic anyway because it looks more standard to non-programmers.

So I will have an array of "pencilmarks" beside the puzzle array and will automatically update it when guesses are made or retracted. (My existing SSP already does the equivalent). But in addition, I will allow the user to manually eliminate candidates to support the concept of "pencilmarks". Also, my current SSP only shows the pencilmarks of the cell that has been selected, so it is hard to scan. You have to keep moving the cursor and memorizing what you saw. And you have to memorize any candidates you have eliminated. It only eliminates candidates due to filling in a cell.

Hope to be finished by Christmas (Well, maybe sooner)

Thanks again for the input. My last answer was my best interpretation of what I've learned. Hope it is correct, if not useful.

Mac

[sudokustudent]

Explaining in other words. Correct me if I am wrong.

1. How to find an x-wing:
(a row= 9 squares that go from left to right horizontally
a column= 9 squares that start at the top and go down)
You need to go through every row thinking like this:
I know there is going to be a number 6 in this row.
Can it be in this square? (looking at the first square in the row)
if yes, you have found one square that can contain a 6. Go to the next square in the row.
If no, you have eliminated that square in the search for a possible place to put a 6 in that row. Go to the next square.
Go through the whole row examining each square.
In the case you find that only one square is possible you put the 6 there and feel good, you dont need an x-wing. If you find that 2 places are possible and 2 places only, you have found half a potential x-wing.
Move on to the next row.
You have now gone through all rows.
If you have found two rows where number 6 can be placed in two squares only AND the two possible squares in each row are directly above/under each other you have found an x-wing.
Not every sudoku has an x-wing so dont be sad if you dont find one.

2. Why find an x-wing? You can eliminate that the number 6 can be placed in any other square directly above or below the four found possible squares.

3. x-wing? Well I think it is a small spaceship that shoots at heroes in science-fiction movies.

[QBasicMac]

Explaining in other words. Correct me if I am wrong.

Looks good except note that you can replace "row" and "column" in the logic. What's true for eliminating candidates in columns, having found an x-wing in rows is also true for eliminating candidates in rows, having found an x-wind in columns.

And not only can one not find an x-wing, as you noted, also one can find one that is perfect in both the rows and columns and thus is useless since it eliminates nothing. A waste-of-time-wing?

Mac

[Ruud]

And not only can one not find an x-wing, as you noted, also one can find one that is perfect in both the rows and columns and thus is useless since it eliminates nothing. A waste-of-time-wing?

Mayby it was already used for eliminations. That would make it an ex-wing.

Ruud.

[QBasicMac]

ex-wing

ROFL

[sudokustudent]

Hi, thanks for your comment. Here is another statement, whats your point of view on this:

The reason (I think) most people do not grasp the concept of the x-wing is probably because you can use column or row as a starting point, and people explaining the x-wing keep stressing that.
Logically this is correct but redundant, you dont need to do both. So in my instructions I deliberatly chose row as starting point.

Why is the column starting point redundant?
1. The x-wing is found using the instructions I wrote.
2. To go through every column when you have gone through every row is redundant, because you will never find an x-wing you did not find using my instructions.
3. The elimination of squares/candidates in a row is not possible when you have used my instructions because both rows have only the two squares making up the x-wing as possible squares. All other squares in these rows are already eliminated.

If you understand why the column starting point is redundant you can write easy-to-read instructions. And you dont have to write so much code if you are developing a computer application.

And I played the violin for 3 years when I was a little kid
Regards,
Sudokustudent

[tarek]

I think the reason why stressing on Row/Column is important, is that Sea Food doeas not stop at x-wing only....... you have the Swordfish (rarely it is of the 3x3x3) formation........

So although it makes it easier to explain the x-wing... The transition to the next step will just be too confusing (AGAIN)....

tarek

[Ruud]

Hi sudoku student,

Look at the following diagram (from my Benchmark List).

Code: Select all

.---------------------.---------------------.---------------------.
|-17    -12378 *278   | 5      12368  1368  |*678    9      4     |
| 1459   12389  2589  | 12368  123468 7     | 68     1568   1568  |
| 1457   178    6     | 18     148    9     | 2      1578   3     |
:---------------------+---------------------+---------------------:
| 2      1789   3     | 1689   15689  1568  | 4      5678   5678  |
| 159    6      589   | 1389   7      4     | 38     2      58    |
| 57     78     4     | 2368   23568  3568  | 1      35678  9     |
:---------------------+---------------------+---------------------:
| 8      279    1     | 4      369    36    | 5      367    267   |
| 6      4      29    | 7      13589  1358  | 389    138    128   |
| 3      5     *79    | 1689   1689   2     |*6789   4     -1678  |
'---------------------'---------------------'---------------------'

Try to locate the X-Wing for digit 7 using your method.

Row 1 has 4 candidates
Row 9 has 3 candidates

Your method only looks at rows with 2 candidates, not at columns with 2 candidates. You will never spot this one without looking at the columns.

cheers,
Ruud.

[NetNinja]

I’ve created a list of heuristics for my own reference. Here's my laconic explanation of an X-wing:

Code: Select all

X-Wing:  Candidate <P> occurs in four cells, forming a rectangle & is conjugate in both columns.
Action:  Remove <P> candidates from the common peers of both rows.

NOTE:  the terms column and row are interchangeable here

I'm assuming some more familiarity than the original post. I know what I intend this to mean, but do any of the experts find this wording less than complete?

Thx

[QBasicMac]

I’ve created a list of heuristics for my own reference.

Your own reference? OK. I hope that list is of use to you.

Mac