Pencilmark only Sudoku

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: Pencilmark only Sudoku

Postby blue » Tue Aug 20, 2019 11:33 pm

From another thread:

blue wrote:
denis_berthier wrote:A more interesting question for me would now be: can one find a Sukaku not in B7B?

Tarek's "singles backdoor size 6" puzzles are all "TE[singles](4)" -- "in BBBB, but not in BBB".
There were two more puzzles of interest, mentioned here:

The others (with high SE ratings) were "TE[singles](2)", and so in BB.
I can't say whether they're in B7B.

I should have added that if locked candidate and locked set eliminations are added to the techniques that are employed (initially, and after each guess or elimination), then the "singles backdoor size 6" puzzles become "T&E(3)", and "tareknasty1" becomes T&E(2).

Something else worth mentioning:
  • Sudoku Explainer's "Cell/Region Forcing chains" eliminations, cover Denis Berthier's "(singles) braids" eliminations.
  • Sudoku Explainer's methods cover all T&E[singles](1) eliminations; some part of the T&E[singles](2) eliminations, and some part of T&E[?](2) eliminations involving naked/hidden pairs and X-wings, and (I think) small chains.
  • (*) Sudoku Explainer's "Dynamic Cell/Region Forcing chains" cover something that, doesn't correspond to anything in the category of "T&E" eliminations -- common outcomes produced (in a complex way) from any one of a short list of possible guesses, one of which is inevitably "correct" (assuming the puzzle actually has a solution).
Aligned Pair and Aligned Triple eliminations, I don't really understand, but it's likely that they fall outside the scope of T&E eliminations too.

Disregard what follows.
The differences were due to a bug in by code. Thanks tarek.

@Dobrichev: referring to your latest post; for the first of the BDS 6 puzzles SE+ "failed" here:

Code: Select all
+-------------------------------+-------------------------------+-------------------------------+
| 3678      13456789  12346789  | 23456789  46789     12456789  | 2346789   3456789   4789      |
| 2356789   37        23457     | 2389      2346789   248       | 23689     1         2345789   |
| 12346789  1234567   1234678   | 12345689  123456789 12345678  | 23689     234569    2346789   |
+-------------------------------+-------------------------------+-------------------------------+
| 23456789  46789     12456789  | 1356789   13456789  145789    | 23456789  46789     12456789  |
| 23689     12346789  123456789 | 12356789  1379      12345789  | 12356789  2346789   12478     |
| 12345689  12346     123456789 | 123569    12345679  12347     | 12345689  2346      12345678  |
+-------------------------------+-------------------------------+-------------------------------+
| 12346789  156789    1246789   | 123456789 12345678  1245678   | 236789    3456789   12346789  |
| 12356789  179       1245789   | 123689    12346789  12478     | 2356789   379       12345789  |
| 12369     12345679  12346789  | 12345689  12346     12345678  | 12346789  2345679   12347     |
+-------------------------------+-------------------------------+-------------------------------+
ED=20.0/2.3/2.3

T&E[singles](2), T&E[singles + locked candidates](2), T&E[singles + locked candidates + locked sets](2), and T&E[singles + locked candidates + locked sets + basic fish](2) ... all "fail" at this point:

Code: Select all
+--------------------------------+--------------------------------+------------------------------+
| 3678       13456789  12346789  | 23456789   46789      12456789 | 2346789    3456789  4789     |
| 2356789    37        23457     | 2389       2346789    248      | 23689      1        2345789  |
| 12346789   1234567   1234678   | 12345689   123456789  12345678 | 23689      234569   2346789  |
+--------------------------------+--------------------------------+------------------------------+
| 23456789   46789     12456789  | 1356789    13456789   145789   | 23456789   46789    12456789 |
| 23689      12346789  123456789 | 12356789   1379       12345789 | 12356789   2346789  12478    |
| 12345689   12346     123456789 | 123569     12345679   12347    | 12345689   2346     12345678 |
+--------------------------------+--------------------------------+------------------------------+
| 123456789  156789    1246789   | 123456789  12345678   1245678  | 236789     3456789  12346789 |
| 12356789   179       1245789   | 123689     12346789   12478    | 2356789    379      12345789 |
| 12369      12345679  12346789  | 12345689   12346      12345678 | 123456789  2345679  12347    |
+--------------------------------+--------------------------------+------------------------------+

Interestingly(?), nothing happens at level 2, except in the T&E[singles] case.

The difference between the two final states, is that SE has two additional eliminations: 5r7c1 and 5r9c7.
Is it an easy job to plug the PM state from just above, into SE, and "ask it" if it can still eliminate those two candidates, and if so, how ?

BTW: I'm only asking out of curiosity.
You guys are on you own here.
Good luck, and have fun :)
Last edited by blue on Wed Aug 21, 2019 10:30 am, edited 2 times in total.
blue
 
Posts: 1052
Joined: 11 March 2013

Re: Pencilmark only Sudoku

Postby tarek » Wed Aug 21, 2019 7:47 am

I had a go at the Sukaku Explainer GUI which accepts parsing the Pencilmark grid as you posted it
Pressing Solve Step would give 1st this step with difficulty rating of 9.2

Double Forcing Chain: I2.5 on & off ==> G9.5 off
Dynamic Double Forcing Chain
With this solving technique, we will prove the two following assertions:
If I2 contains the value 5, then G9 cannot contain the value 5
If I2 does not contain the value 5, then G9 cannot contain the value 5
Because the two assumptions are complementary, and the results are the same, we can conclude that G9 cannot contain the value 5.
Each assertion is proved by a different chain of simple rules. The chains can be dynamic, which means that the conclusions of multiple sub-chains must be combined in some cases.
The details of each chain are given below. Use the view selector below the grid to switch between the graphical illustrations of the two different chains.

chain 1 with image: Show
Chain 1: If I2 contains the value 5, then G9 cannot contain the value 5 (View 1): (1) If I2 contains the value 5, then I4 cannot contain the value 5 (the value can occur only once in the column) (2) If I2 contains the value 5 (initial assumption), then I6 cannot contain the value 5 (the value can occur only once in the column) (3) If I6 does not contain the value 5 and I4 does not contain the value 5 (1), then G9 cannot contain the value 5 (Pointing: Cells G4,G5,G6: 5 in block and column)
Image

chain 2 with image: Show
Chain 2: If I2 does not contain the value 5, then G9 cannot contain the value 5 (View 2): (1) If I2 does not contain the value 5, then B1 cannot contain the value 5 (Claiming: Cells A2,C2: 5 in row and block) (2) If I2 does not contain the value 5 (initial assumption), then B3 cannot contain the value 5 (Claiming: Cells A2,C2: 5 in row and block) (3) If B3 does not contain the value 5 and B1 does not contain the value 5 (1), then A8 cannot contain the value 5 (Claiming: Cells B7,B9: 5 in column and block) (4) If B3 does not contain the value 5 (2) and B1 does not contain the value 5 (1), then C8 cannot contain the value 5 (Claiming: Cells B7,B9: 5 in column and block) (5) If C8 does not contain the value 5 and A8 does not contain the value 5 (3), then G9 cannot contain the value 5 (Claiming: Cells G8,I8: 5 in row and block)
Image
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: Pencilmark only Sudoku

Postby blue » Wed Aug 21, 2019 10:29 am

Thank you tarek,

I had a stupid bug in my code ...
Code: Select all
if (solution[9 * r + c] == d)
    continue; // impossible elimination
should have been:
Code: Select all
if (solution[9 * r + c] == d + 1)
    continue; // impossible elimination

SE has its particular way of explaining things.
The two eliminations can be done with (simple) "grouped candidate" AICs, too ... starting from that PM state.
(Something else, that has been missing in SE).

BTW: After fixing the bug, nothing had changed in the T&E depth(s) that were required to solve the puzzles.
blue
 
Posts: 1052
Joined: 11 March 2013

Re: Pencilmark only Sudoku

Postby tarek » Wed Aug 21, 2019 12:45 pm

Explainer indeed has a language of its own. It remains a valuable tool nevertheless.

The future release(s) of Sukaku explainer will show more efficient and faster solving in general. The GUI also would accept pasting pencilmarked grids like the one you posted with explainer continuing solution from that point as I demonstrated.
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: Pencilmark only Sudoku

Postby m_b_metcalf » Tue Sep 03, 2019 10:40 am

This type of puzzle has somehow escaped my notice until now. For program testing I found the 729-digit string the most convenient format, so here are five published puzzles in that form for other adventurers:

Code: Select all
123456789123456789023456789123406789123456789120406789123406789123406780123456789123456789103050000023056700023056789123456789123456789123456789023000700123456789123456789123456789123456789120056789123456789120450789123456789123406789123456789123456789123456789123456789020056789123456789123456789123456789123456789123456789123456789100400000123456789120450789123456789123456789000450000123456789123456789123456789123456789123456789123056789123456789123456789123456789123456789123456789123456789123456789023456789123456789123456009123406789123456789020000700123456789123456789123456789123456789123456789103450009100406009123456789123456789123456789123456789123456789020050000123456789123456709123456709123456789020000700020050700
dobrichev 637

120050700023400709120400709020406080120456709100456080000050709003050700103450080103056709123456789000456700003056780023056000020056789020456009023400000003056709023400080120056000123056780120400780003450789100400709000456709103400000120006789123056789000456709003056000103000080020456000123400089120456700103000080120406700123406080103406709003406709020406080100056780123406789123406789000000780123456000020050780120006080003406789000056089123456780000450080123456700000006709120450789023456700020406780120450080100000009103456789123406089023050080023450089120006709003000780100006089100456089123456789123406780020050780120006000123456089003050089103056080103400709103400089103000789003456080003056089123400780000006700023056780
ruud's first

123000700120056000003006789020050789000400789000456009100006709023450700103400080020456000103400089003450009103056000003006709120400700020400780000050789123006080023050080020400789120006700020400089123450700103406080003456009000456080120000709100056009020050780003450700100456780003450009023056000023406089123006000100406789003006709123400080020400089123006000000056789100056009023050700100400089000450709100406089100056700023406780123000700120400089003450780123050000000050789000006789020400789003006780100406009103406000120406000103050700000056089120056789023450000123000080000456009120056780003050709023400700020006089100400709103400080023056000003450700003000789120056000023400089100456080020056789100050780023056009100450700
ruud 13.10.2006

000000009000000080123450000000000700003406000120406000123400000100450000023050000000000700123050000123450000123400080003400089120400089000006000100450089023050089123400000123000000000006000123400080000050000120400089123400780100400789023000789120006080000400000120000009100006080000006780000050000020000780003000000020006789123006080123006000000000700000000009003406080100406080000050000000406080020006080003056080003056009003050009003406080020000000000406780000400780000406789100000000123456000123056700000000080000056000000406700020406700000000009100056700003056700023056000023056709023050009020056080100000000020006789003000780000056780000400000100456000100056709100450009000456080000406789003000000100000780020000000000056780
champagne dry with r7c4 changed to 56

000400009120000000023000000003050000020050000100000080003006000000400700100000009000056000003400000000000709000000780020400000000400700100000700000000089000450000100000080003000700000050080000006009003006000100000009000406000020050000023000000020050000000406000100006000100000080003000700003000080020000009020000009103000000103000000020050000000000709000400700000050009020006000003006000000450000000050080003400000000000089000000780020400000100006000003050000000400700100006000000400080020000700000406000003050000100050000020400000000000709000006080100050000000400700000006009000000089103000000000006080003400000000006700020050000000400700120000000000000780020050000100400000100050000003000080020000009000050009003000080003006000
81 pairs
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13637
Joined: 15 May 2006
Location: Berlin

Re: Singles backdoor size 6

Postby m_b_metcalf » Fri Sep 13, 2019 11:46 am

tarek wrote:Here are the original 11 puzzles in the 729 line format

After much huffing and puffing, my solver finally solved the second version:
Hidden Text: Show
Code: Select all
  3  8  1  4  7  6  2  5  9   
  5  7  4  2  9  8  6  1  3
  9  2  6  1  5  3  8  4  7
  2  4  9  6  8  1  3  7  5
  8  6  5  7  3  9  1  2  4
  1  3  7  5  4  2  9  6  8
  4  9  2  3  1  5  7  8  6
  7  1  8  9  6  4  5  3  2
  6  5  3  8  2  7  4  9  1

and I'd be grateful for confirmation that that result is correct.

Thanks,

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13637
Joined: 15 May 2006
Location: Berlin

Re: Pencilmark only Sudoku

Postby creint » Fri Sep 13, 2019 4:20 pm

Result is correct, easy with minisat in 0.12 seconds. Did your solver use logic or DLX?
creint
 
Posts: 397
Joined: 20 January 2018

Re: Pencilmark only Sudoku

Postby m_b_metcalf » Fri Sep 13, 2019 4:50 pm

creint wrote:Result is correct, easy with minisat in 0.12 seconds. Did your solver use logic or DLX?

17 candidates were eliminated by logic, the rest was brute force.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13637
Joined: 15 May 2006
Location: Berlin

Re: Pencilmark only Sudoku

Postby creint » Fri Sep 13, 2019 6:12 pm

m_b_metcalf wrote:17 candidates were eliminated by logic, the rest was brute force.


So 5 in all corners from the corner boxes + 9r1c7. And how long did the solver take to find those?
With my current logic it took 0.6 seconds to reach that state.
creint
 
Posts: 397
Joined: 20 January 2018

Re: Pencilmark only Sudoku

Postby m_b_metcalf » Fri Sep 13, 2019 6:38 pm

creint wrote:
m_b_metcalf wrote:17 candidates were eliminated by logic, the rest was brute force.


So 5 in all corners from the corner boxes + 9r1c7. And how long did the solver take to find those?
With my current logic it took 0.6 seconds to reach that state.

Code: Select all
 At  7  1 cannot have   5
 At  7  9 cannot have   5
 At  9  1 cannot have   5
 At  9  9 cannot have   5
 At  1  1 cannot have   5
 At  1  3 cannot have   5
 At  1  7 cannot have   5
 At  1  7 cannot have   9
 At  1  9 cannot have   5
 At  3  1 cannot have   5
 At  3  3 cannot have   5
 At  3  7 cannot have   5
 At  3  9 cannot have   5
 At  7  3 cannot have   5
 At  7  7 cannot have   5
 At  9  3 cannot have   5
 At  9  7 cannot have   5

 phase 1 took .30 seconds
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 13637
Joined: 15 May 2006
Location: Berlin

Re: Pencilmark only Sudoku

Postby tarek » Mon Sep 16, 2019 10:56 am

Here on the hardest sudokus thread there was also a discussion on how convoluted some of these pencilmark sudokus (sukakus) can get
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: Pencilmark only Sudoku

Postby dobrichev » Sun Sep 22, 2019 3:18 pm

This is the distribution by rating for puzzles having 637 unresolved pencilmarks.

#puzzles, ER, EP, ED
Code: Select all
  86226 2.8   2.3   2.3
  32314 3.0   2.3   2.3
  10568 3.0   3.0   3.0
   1444 3.4   2.3   2.3
    266 3.4   3.0   3.0
   7528 3.6   2.3   2.3
   3256 3.6   3.6   3.6
   1224 7.3   2.3   2.3
     24 7.3   3.0   3.0
    426 8.3   2.3   2.3
     90 8.3   8.3   3.0
    180 8.3   8.3   4.4
    342 8.9   2.3   2.3
     90 8.9   8.9   3.0
     90 8.9   8.9   8.4
     84 9.0   2.3   2.3
     90 9.0   9.0   8.4

The greatest common divisor is 2.
dobrichev
2016 Supporter
 
Posts: 1863
Joined: 24 May 2010

Re: Pencilmark only Sudoku

Postby tarek » Sun Sep 22, 2019 7:38 pm

2 months and 2 weeks since you posted your 637 puzzle and look where we are now!!! Great work!
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: Pencilmark only Sudoku

Postby dobrichev » Sun Sep 22, 2019 8:06 pm

Actually all they appeared in the first 2 weeks, while I still experimented with the software.
They are close to each other and share small number of solution grids. [Edit: exactly 2 solutions, one of them has valid vanilla 17-clue puzzle, other has not.]
My attempt to reproduce them or find other island by starting from independent seed failed. So either I was lucky and this is the absolute minimum and complete list (which is very unlikely but still possible if the whole pencilmark space is well connected), or this is just one local minimum and the global can be much deeper.
dobrichev
2016 Supporter
 
Posts: 1863
Joined: 24 May 2010

Re: Pencilmark only Sudoku

Postby dobrichev » Thu Oct 03, 2019 4:47 pm

This puzzle is minimal and has 272 restrictions - i.e. it is high-clue.
Its first move is rated by SE as ED=10.3 Contradiction Forcing Chain: r7c3.1 on ==> r5c4.9 both on & off, followed by similar chains rated 12.6, 12.7, 12.8.
Its solution grid is the most-canonical grid.
Code: Select all
+-------------------------------+-------------------------------+-------------------------------+
| 139       236789    23456789  | 123456789 2345689   123567    | 3789      123458    4589      |
| 12459     23579     2356789   | 12456     123458    369       | 1245678   23457     13689     |
| 1234567   123456789 135789    | 145679    134589    12345789  | 134579    345679    147       |
+-------------------------------+-------------------------------+-------------------------------+
| 1248      2789      12456     | 23567     1234689   12789     | 12358     2345678   3456      |
| 123456789 23457     1247      | 2489      34        123456    | 236789    123569    2349      |
| 2567      2345689   24678     | 13589     234678    124678    | 3457      23689     12356     |
+-------------------------------+-------------------------------+-------------------------------+
| 1246789   3469      123456789 | 36789     1345678   123468    | 1489      134568    457       |
| 1245678   1239      145689    | 239       345689    356       | 12345679  12345689  12789     |
| 12456789  145679    1245678   | 1345678   234789    134569    | 1234579   2457      1345678   |
+-------------------------------+-------------------------------+-------------------------------+

It has backdoor of size 4 in both singles and singles+locked, lower compared to tarek's hardest puzzles above in this thread which have backdoor 6 in singles and 4 in singles+locked.

SE rating of 12.8 isn't very uncommon for pencilmark-only puzzles. By frequency maybe it is equivalent to something below 10.0 or even 9.0 for vanilla puzzles.
The low diamond rating for the minimized derivatives of vanilla puzzles is explainable. Randomly generated pencilmark puzzles also trend to have low ED, and from this perspective the above puzzle is exceptional.

The puzzle in 729-char format and the first SE solution steps.
Hidden Text: Show
Code: Select all
1.3.....9.23..6789.23456789123456789.23456.89123.567....3...78912345..8....45..8912.45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..1234567891.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8..2345678...3456...123456789.2345.7..12.4..7...2.4...89..34.....123456....23..6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56...12.4.6789..34.6..9123456789..3..67891.345678.1234.6.8.1..4...891.3456.8....45.7..12.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
10.3   Contradiction Forcing Chain: r7c3.1 on ==> r5c4.9 both on & off
1.3.....9.23..6789.23456789123456789.23456.89123.567....3...78912345..8....45..8912.45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..1234567891.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8..2345678...3456...123456789.2345.7..12.4..7...2.4...89..34.....123456....23..6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56...12.4.6789..34.6..9.23456789..3..67891.345678.1234.6.8.1..4...891.3456.8....45.7..12.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.6   Contradiction Forcing Chain: r5c1.2 on ==> r9c5.7 both on & off
1.3.....9.23..6789.23456789123456789.23456.89123.567....3...78912345..8....45..8912.45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..1234567891.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8..2345678...3456...1.3456789.2345.7..12.4..7...2.4...89..34.....123456....23..6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56...12.4.6789..34.6..9.23456789..3..67891.345678.1234.6.8.1..4...891.3456.8....45.7..12.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.7   Contradiction Forcing Chain: r3c2.9 on ==> r3c7.1 both on & off
1.3.....9.23..6789.23456789123456789.23456.89123.567....3...78912345..8....45..8912.45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8..2345678...3456...1.3456789.2345.7..12.4..7...2.4...89..34.....123456....23..6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56...12.4.6789..34.6..9.23456789..3..67891.345678.1234.6.8.1..4...891.3456.8....45.7..12.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.7   Contradiction Forcing Chain: r7c5.3 on ==> r8c8.1 both on & off
1.3.....9.23..6789.23456789123456789.23456.89123.567....3...78912345..8....45..8912.45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8..2345678...3456...1.3456789.2345.7..12.4..7...2.4...89..34.....123456....23..6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56...12.4.6789..34.6..9.23456789..3..67891..45678.1234.6.8.1..4...891.3456.8....45.7..12.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.8   Contradiction Forcing Chain: r7c6.3 on ==> r2c5.8 both on & off
1.3.....9.23..6789.23456789123456789.23456.89123.567....3...78912345..8....45..8912.45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8..2345678...3456...1.3456789.2345.7..12.4..7...2.4...89..34.....123456....23..6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56...12.4.6789..34.6..9.23456789..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7..12.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.8   Contradiction Forcing Chain: r5c7.3 on ==> r6c9.1 both on & off
1.3.....9.23..6789.23456789123456789.23456.89123.567....3...78912345..8....45..8912.45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8..2345678...3456...1.3456789.2345.7..12.4..7...2.4...89..34.....123456....2...6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56...12.4.6789..34.6..9.23456789..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7..12.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.8   Contradiction Forcing Chain: r8c1.1 on ==> r4c2.8 both on & off
1.3.....9.23..6789.23456789123456789.23456.89123.567....3...78912345..8....45..8912.45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8..2345678...3456...1.3456789.2345.7..12.4..7...2.4...89..34.....123456....2...6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56...12.4.6789..34.6..9.23456789..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.8   Contradiction Forcing Chain: r1c2.9 on ==> r7c4.7 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..8912.45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8..2345678...3456...1.3456789.2345.7..12.4..7...2.4...89..34.....123456....2...6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56...12.4.6789..34.6..9.23456789..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.8   Contradiction Forcing Chain: r2c1.2 on ==> r3c8.9 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8..2345678...3456...1.3456789.2345.7..12.4..7...2.4...89..34.....123456....2...6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56...12.4.6789..34.6..9.23456789..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.8   Contradiction Forcing Chain: r4c8.2 on ==> r8c8.4 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3456789.2345.7..12.4..7...2.4...89..34.....123456....2...6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56...12.4.6789..34.6..9.23456789..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.8   Contradiction Forcing Chain: r7c1.1 on ==> r1c1.9 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3456789.2345.7..12.4..7...2.4...89..34.....123456....2...6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23456789..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.9   Contradiction Forcing Chain: r7c3.7 on ==> r4c7.1 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3456789.2345.7..12.4..7...2.4...89..34.....123456....2...6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23456.89..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.9   Contradiction Forcing Chain: r5c1.4 on ==> r9c8.4 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.2345.7..12.4..7...2.4...89..34.....123456....2...6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23456.89..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.9   Contradiction Forcing Chain: r2c2.9 on ==> r5c8.1 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7...23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.2345.7..12.4..7...2.4...89..34.....123456....2...6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23456.89..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.9   Contradiction Forcing Chain: r9c3.1 on ==> r5c6.4 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7...23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.2345.7..12.4..7...2.4...89..34.....123456....2...6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23456.89..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.9.2.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.9   Contradiction Forcing Chain: r8c2.9 on ==> r4c1.4 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7...23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.2345.7..12.4..7...2.4...89..34.....123456....2...6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23456.89..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123......1..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.9.2.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.9   Contradiction Forcing Chain: r5c6.3 on ==> r9c8.7 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7...23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.2345.7..12.4..7...2.4...89..34.....12.456....2...6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23456.89..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123......1..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.9.2.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.9   Contradiction Forcing Chain: r5c8.3 on ==> r5c1.8 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7...23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.2345.7..12.4..7...2.4...89..34.....12.456....2...678912..56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23456.89..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123......1..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.9.2.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
13.0   Contradiction Forcing Chain: r9c1.1 on ==> r7c1.6 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7...23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.2345.7..12.4..7...2.4...89..34.....12.456....2...678912..56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23456.89..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123......1..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....789.2.4567891..4567.9.2.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
13.0   Contradiction Forcing Chain: r7c3.8 on ==> r8c5.5 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7...23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.2345.7..12.4..7...2.4...89..34.....12.456....2...678912..56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23456..9..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123......1..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....789.2.4567891..4567.9.2.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
13.0   Contradiction Forcing Chain: r8c3.1 on ==> r2c4.1 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7...23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.2345.7..12.4..7...2.4...89..34.....12.456....2...678912..56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23456..9..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.........456.89.23.....9..3456.89..3.56...1234567.9123456.8912....789.2.4567891..4567.9.2.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
13.0   Contradiction Forcing Chain: r5c8.2 on ==> r9c8.5 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7...23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.2345.7..12.4..7...2.4...89..34.....12.456....2...67891...56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23456..9..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.........456.89.23.....9..3456.89..3.56...1234567.9123456.8912....789.2.4567891..4567.9.2.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
13.0   Contradiction Forcing Chain: r5c2.4 on ==> r5c1.5 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7...23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.23.5.7..12.4..7...2.4...89..34.....12.456....2...67891...56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23456..9..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.........456.89.23.....9..3456.89..3.56...1234567.9123456.8912....789.2.4567891..4567.9.2.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
13.0   Contradiction Forcing Chain: r7c3.4 on ==> r7c4.6 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7...23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..12345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.23.5.7..12.4..7...2.4...89..34.....12.456....2...67891...56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23.56..9..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.........456.89.23.....9..3456.89..3.56...1234567.9123456.8912....789.2.4567891..4567.9.2.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
2.6   Pointing: Cells r8c2,r9c2: 1 in block and column
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7...23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567...2345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.23.5.7..12.4..7...2.4...89..34.....12.456....2...67891...56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23.56..9..3..67891..45678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.........456.89.23.....9..3456.89..3.56...1234567.9123456.8912....789.2.4567891..4567.9.2.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.8   Contradiction Forcing Chain: r7c5.4 on ==> r2c7.2 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7...23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567...2345678.1.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.23.5.7..12.4..7...2.4...89..34.....12.456....2...67891...56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23.56..9..3..67891...5678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.........456.89.23.....9..3456.89..3.56...1234567.9123456.8912....789.2.4567891..4567.9.2.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
12.9   Contradiction Forcing Chain: r3c5.4 on ==> r1c7.9 both on & off
1.3.....9.23..678..23456789123456789.23456.89123.567....3...78912345..8....45..891..45...9.23.5.7...23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567...2345678.1.3.5.7891..4567.91.3.5..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8...345678...3456...1.3.56789.23.5.7..12.4..7...2.4...89..34.....12.456....2...67891...56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56....2.4.6789..34.6..9.23.56..9..3..67891...5678.12.4.6.8.1..4...891.3456.8....45.7...2.45678.123.........456.89.23.....9..3456.89..3.56...1234567.9123456.8912....789.2.4567891..4567.9.2.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.
1.3.....9.23..6789.23456789123456789.23456.89123.567....3...78912345..8....45..8912.45...9.23.5.7.9.23.5678912.456...12345..8...3..6..912.45678..2345.7..1.3..6.891234567..1234567891.3.5.7891..4567.91.345..8912345.7891.345.7.9..34567.91..4..7..12.4...8..2....78912.456....23.567..1234.6.8912....789123.5..8..2345678...3456...123456789.2345.7..12.4..7...2.4...89..34.....123456....23..6789123.56..9.234....9.2..567...23456.89.2.4.678.1.3.5..89.234.678.12.4.678...345.7...23..6.89123.56...12.4.6789..34.6..9123456789..3..67891.345678.1234.6.8.1..4...891.3456.8....45.7..12.45678.123.....91..456.89.23.....9..3456.89..3.56...1234567.9123456.8912....78912.4567891..4567.912.45678.1.345678..234..7891.3456..912345.7.9.2.45.7..1.345678.   272   20.0/0.0/10.3   xx

Edit: serate 1.4.1 (Sudoku Explainer) 2019-09-22 can't solve it giving up after processing for
Code: Select all
real   1541m37.897s
user   5670m23.368s
sys   24m51.504s

Highest rating steps are 6 x 13.0.
All steps are added to the solution path in the hidden section above.
The first solving step is fast in SE GUI mode and shows two spectacular chain diagrams.
dobrichev
2016 Supporter
 
Posts: 1863
Joined: 24 May 2010

PreviousNext

Return to Sudoku variants