The New Sudoku Players' Forum

[m_b_metcalf]

Thanks, something like this is exactly what I need! I could not resist trying to solve this puzzle with my program. Your puzzle can be solved with basic methods including hidden tuples of size <=3, naked tuples of size <=4 and basic fishes of size <=3 with my solver in 0.3 s. The general SAT-solver needed 0.8 s to solve it. I fed the solution to my reduce routine using as I believe the same symmetry and created in 40 s a harder minimal puzzle which needs hidden+naked tuples + basic fishes of size <=4.

Nice, but note that r25c25 can also be deleted.

M

[hkociemba]

Nice, but note that r25c25 can also be deleted.

r25c25 + the 3 other cells due to symmetry. That's true but then it is not solvable any more with tuples and fishes of size <= 4. When I take out the "big gun" and reduce it further with the SAT solver I get for example:

Hidden Text: Show

Code: Select all

  . 44  . 16  . 43 10  . 36 32  . 18  .  . 11  . 23  . 40  4 26 21  .  1  . 34  .  3  8 35 17  .  9  . 28  .  . 31  . 39 47  . 30 13  . 25  . 37  .
 42  6  .  1  . 17 25  . 43 10 26 31 19  . 45  . 41  . 47  2  . 40 22  .  .  . 20 27  . 48 36  . 46  . 13  . 38 28 35 23 21  . 44 39  . 33  . 15 11
 27  . 20  .  .  . 49  .  4 33 44 46  .  3  . 28  .  . 16  .  . 23  . 14  . 36  . 47  .  . 19  .  . 10  . 40  .  5 48 15 24  . 43  .  .  . 41  .  8
  .  .  . 38  .  .  .  7 37  .  .  . 35 25 36  . 27 33 19  .  . 12 26 16  . 13  5 17  .  . 22 47 32  . 11 30  2  .  .  .  8 44  .  .  .  9  .  .  .
 15 36 31 14  .  . 33 28  .  .  9  . 38 12 25 29  .  .  3  8  . 44  .  4 45 19  . 11  .  6 26  .  . 20 24 27 17  . 34  .  . 46  7  .  . 32  5 47 35
 26 13 12  . 39 11  . 17 15  . 20  . 24  .  .  .  . 37  5 46  1 31  . 33 48 18  . 38 49 40 21  2  .  .  .  . 25  . 29  . 32 45  . 16  3  . 10 19 36
 46  .  . 18 45 41  8 39  1  . 34  . 11 49  .  .  .  . 24 13 42 37 43  .  9  . 25 29 33 23 12  .  .  .  .  4 19  . 10  . 16 26 27  2 40  6  .  . 48
  .  .  . 32  .  . 36 44 21 31  .  . 47  .  1 25  .  9  7  . 23 28  .  . 11  .  . 16 27  . 18 34  . 49 29  . 10  .  . 48  6 40 35  .  . 46  .  .  .
  . 15 26  9  . 27 31 19  .  .  . 37  . 16  .  . 30  .  .  . 24  7 20 46  . 35 22 48 39  .  .  . 23  .  . 34  . 17  .  .  . 49  2 40  . 44 45 21  .
  . 24 21  .  . 46  .  . 11  .  .  . 18  . 15  . 44 42 35 22  . 41  . 32  . 25  . 10  . 16 48 43 47  . 40  . 27  .  .  . 26  .  .  5  .  . 37  3  .
  .  3 16  4  .  6 30 24 38  . 46 39  . 33  . 11  .  . 49 40 18  . 13  . 14  . 34  . 21 15 31  .  .  1  . 41  .  7 47  . 45  2 12 25  . 22 23 10  .
 45  . 44  . 23  .  . 30 10 34 22  .  . 48  3  .  .  .  2  . 46  . 18  . 49  . 31  . 24  . 11  .  .  . 41 13  .  . 25 19 12 21  .  . 38  .  6  . 33
 10  .  . 41  .  . 14  . 29  . 25 20  4  2  .  . 37 45  .  . 31  . 23 21 33 17 42  . 19  .  . 12 36  .  . 46  9 30 38  . 39  . 11  .  . 49  .  . 18
 49 18  1  .  5 35  . 23  . 40  7  . 14  . 39 34 29 48 21  . 33  . 12  .  8  .  3  .  9  . 45  6 22 46 37  . 24  .  4 11  . 42  . 30 28  . 31 17 20
  .  . 13  .  . 34  .  2  .  . 40  6  .  .  .  .  .  8  . 32 47  3 24 19  . 46 43 45 37 31  . 23  .  .  .  .  .  9 39  .  . 12  . 38  .  . 36  .  .
 32  .  .  .  . 31  .  .  .  .  . 36 27  . 16  .  .  . 48 26  .  .  .  .  .  .  .  .  . 46 43  .  .  . 38  .  4 25  .  .  .  .  . 22  .  .  .  .  9
 21 45  9 40 26  . 46 41 18  . 13 22  .  .  2  .  6  .  . 25  . 14  1  .  .  . 39  7  . 42  .  . 19  . 34  .  . 16 32  . 48 20 33  . 24 23 27 30  4
  .  8 25  .  . 18  .  . 19  . 23  . 43  9  . 33  .  . 15  .  . 16 44 17 38  2 48 42  .  .  7  .  . 45  . 49 31  .  5  . 35  .  .  1  .  . 34 41  .
  .  7 22 48  .  . 37  .  .  . 47  . 30 26  .  . 43  1  . 42 20 10 21 13  . 12 36 25 35 18  . 49 14  .  . 28 41  .  6  .  .  . 19  .  . 40 16 31  .
  .  . 43 20  1 15 42  .  .  . 39  7 48  . 27 19 49 18  . 36 21 34  .  5 26  9  . 22  4  8  . 32 29 28  2  . 23 44  3  .  .  . 17 47 46 45 13  .  .
 30  . 36 23  2  5  3 38 20  . 16 14 25 42  . 12 34 35  .  . 22  . 28 27  . 41  4  . 17  .  . 24  6 47  . 19 11 33 21  . 46 13 15 43 49 29  7  . 39
  . 34 29 37 24  . 18  .  .  .  2  .  . 28 20 15  5  .  . 17 43  .  .  . 32  .  .  .  7  1  .  . 26  4 49 38  .  . 46  .  .  . 16  . 27 35 30 23  .
 38 40  6  .  . 19  . 37  . 16  .  . 32 29 22  .  2  3  .  . 28  .  .  .  .  .  .  . 47  .  . 48 18  . 12 21 49  .  .  4  . 10  . 31  .  . 46 36 17
  .  .  .  .  . 12  . 18 42 38 31  .  .  . 37 47  8 29 25  .  . 20  .  . 27  .  . 28  .  . 35 11  5 33 45  .  .  . 24 16 44 48  . 49  .  .  .  .  .
  .  2 14  .  . 49  .  . 46 11  . 34 21  4 24  9  . 10 44  6  . 22  3 41 12  8 15 36  . 39 27 17  . 37 31  5 30  1  . 18 29  .  . 42  .  . 32 48  .
  .  .  .  .  . 23  . 49  7 15 35  .  .  . 14 39 18 34 30  .  . 17  .  . 29  .  .  4  .  . 38 41  2  8 16  .  .  . 19 12 33 27  . 11  .  .  .  .  .
 31  5  4  .  . 32  . 47  .  6  .  . 23 39 49  . 26 19  .  . 45  .  .  .  .  .  .  . 20  .  . 13 30  . 22  7 34  .  .  2  . 17  . 29  .  . 28  8 12
  . 21 27 13 22  . 47  .  .  . 14  .  . 20  4 32 31  .  . 11 16  .  .  .  7  .  .  . 28 43  .  . 40  6 36 45  .  .  9  .  .  . 38  . 18 41 39 44  .
 35  . 17 26  9 47 20 31 41  . 37 11  1 27  .  3 39 30  .  . 44  . 14 48  . 32 19  . 10  .  .  7 15 21  . 23  8 12  2  . 40 33 34 28 25 38  4  .  6
  .  . 15 27  3  7 39  .  .  . 10 35 20  . 42 18 19 11  . 37 40 29  . 28 34 30  .  2 43 47  .  5 16 48 33  . 44 24 17  .  .  . 31  9 21 13 12  .  .
  .  1 45  5  .  .  6  .  .  .  3  .  9 23  .  . 20 41  . 35 25 39 31 40  .  4 11 13  2 30  . 28 12  .  . 18 48  . 37  .  .  . 32  .  . 16 33 29  .
  . 31 49  .  . 36  .  . 33  .  6  . 39 34  .  1  .  . 26  .  .  5 47 12 20 22 35 21  .  .  4  .  . 40  . 11 14  . 15  . 30  .  . 23  .  .  8 46  .
  4 25 28 30 16  . 48 14 49  . 29 42  .  .  6  . 47  .  . 45  . 36 33  .  .  . 27 15  . 37  .  . 41  .  3  .  . 20 26  . 22  9 39  .  7 18 43  5 40
 44  .  .  .  . 13  .  .  .  .  .  2 12  . 32  .  .  . 28 33  .  .  .  .  .  .  .  .  . 14  1  .  .  . 23  . 29  6  .  .  .  .  . 27  .  .  .  .  3
  .  .  2  .  .  8  . 48  .  . 21 32  .  .  .  .  . 23  . 14 17 25  7 10  .  1 44 41 36 29  . 45  .  .  .  .  . 43 27  .  .  4  . 37  .  . 20  .  .
 41 17 48  . 35 42  .  8  . 39 24  . 40  . 26 23 12 16 37  . 32  . 11  . 28  . 29  . 15  . 20 33 31 36 19  . 18  . 30 47  .  3  .  7 43  . 22  9 13
 25  .  .  2  .  . 34  . 48  . 38 29 46  6  .  . 11 36  .  .  3  . 17 26 43 16 13  .  1  .  . 27  4  .  . 22 40 19 23  . 37  .  5  .  . 15  .  . 31
 47  . 46  . 44  .  . 35 26 41  4  .  . 19 48  .  .  . 43  .  6  .  8  . 21  . 32  . 22  . 24  .  .  .  5  2  .  . 11 25 10 28  .  . 23  . 40  . 30
  . 43 37 49  . 30  5 12 22  . 28 44  . 18  . 45  .  . 39 41 35  . 15  . 23  . 40  . 13  2 16  .  .  9  . 17  .  4 42  . 20 36 24 48  . 11  3 27  .
  . 33 11  .  . 26  .  . 14  .  .  . 13  . 47  . 46 28 18 44  . 35  . 37  . 27  .  9  . 17  8 40  3  . 32  . 21  .  .  . 49  .  . 36  .  . 42  4  .
  . 19 32  8  . 45  7 25  .  .  . 33  . 11  .  .  1  .  .  .  5 47  4 18  . 42 46 20 38  .  .  . 43  .  . 35  . 48  .  .  . 31 29 41  . 26 49  2  .
  .  .  .  3  .  . 13 34 32 17  .  . 16  . 33 31  . 22 20  . 19 45  .  . 44  .  . 30 29  . 28 37  . 42 35  . 43  .  .  6 14  1 47  .  .  8  .  .  .
 18  .  . 10 31 20 32 22 25  . 11  . 49 15  .  .  .  . 34 19  8  2 38  . 41  . 16 37 12 36 23  .  .  .  . 14 28  .  7  . 27 35  1 26  6  3  .  . 47
 13 47  5  . 40 39  . 10 28  . 33  . 42  .  .  .  .  2 17  1 41 43  . 20 31 11  .  6 34 32 37 25  .  .  .  . 45  . 16  .  3 23  .  8  9  . 14 22 29
 16 41 30 45  .  .  1  3  .  . 18  .  7 46 10 37  .  . 13 39  . 15  . 24 35 40  . 33  . 28 29  .  . 22  8 32 26  . 49  .  . 47 36  .  . 48 19 43 23
  .  .  . 43  .  .  . 20 40  .  .  .  6  8 30  .  3 24 23  .  . 42 25 29  . 47 17 39  .  .  2 46 33  .  4 31  1  .  .  . 36 18  .  .  . 21  .  .  .
 34  . 24  .  .  . 19  . 39  5 41 38  . 35  .  4  .  . 32  .  . 30  . 22  . 49  . 23  .  . 47  .  .  3  . 20  .  2  8 33 13  . 40  .  .  . 11  . 37
  2 12  . 11  . 14 26  . 47 23 30 24 34  . 31  . 36  .  9 20  .  4 48  .  .  .  8 32  . 27 13  . 35  .  7  . 42 10 22  5 41  . 46 33  . 28  . 39 38
  . 23  . 15  . 25 22  . 13  2  . 19  .  . 44  . 14  . 33 38 29 18  .  3  . 28  . 26 41 11 39  . 21  . 20  .  . 37  . 46 17  .  4 12  . 42  . 16  .

1337 givens, 6832 candidates(pencilmarks).


This one presumely still is not minimal, it just takes too long to continue the reduction process.The SAT solver now takes 123 s to solve this puzzle and 127 s to prove that the solution is unique. I wonder if this one can be solved with some basic and advanced "human" methods.

[hkociemba]

Good progress concerning generation of a valid grid. Generation of 100x100 took 15 min though I did not try any optimization yet. For 225x255 though I do not think it will finish in a reasonable time yet.
The algorithm yet is extremely simple:
1. Fill all rows with numbers from 1..N in random order.
2. Select a random row r and in this row two random cells (r,c1) and (r,c2).
3. Count the number n1 of "wrong" numbers in the two columns c1 and c2 and in the two blocks b1 and b2 the (r,c1) and (r,c2) are in.
4. Swap the content of (r,c1) and (r,c2).
5. Count again. If the number n2 of "wrong" numbers is now greater, swap back.
6. Goto 2 and repeat until the grid is valid. Validity can be computed by the initial value I for the number of wrong numbers and always updating this value: I <-- I - n1 + n2.
Surprisingly the algorithm does not seem to get stuck in a local minimum (most of the time?) and this greedy algorithm works. For a standard 9x9 creation time is only about 30 ms on average, for a 49x49 20 s to 30 s.

[m_b_metcalf]

Good to know that your algorithm works up to higher sizes. You prompted me to make some new timings on ancient code, the result being:

Code: Select all

 box
size    number    time   average time
----    ------    ----   ------------

  3    1,000,000     28s      28µs
  4      1,000     0.41s    0.41ms
  5      1,000     6.28s    6.28ms
  6         10    19.70s    1.97s 
  7          3    12.55s    4.18s
  8          1    stalls

On an i5, with no output.

For x-sudokus my method works only for 9x9 and 16x16. For larger sizes I offer a solver a pseudo puzzle, empty but with the diagonals already in place, and take the first solution it finds. That works for up to 36x36.

I'll look at the 16x16 problem very soon.

M

[hkociemba]

For small blocksizes you algorithm works much faster than mine. For XSudoku mine does not seem to work at all. I have some idea how to manage this. I implemented a complete generator set of symmetry operations for non-XSudokus into my program now (permute_band, permute_stack, permute_bands, permute_stacks, reflect_diagonal,,relabel_nums). Only the last two also are symmetries of XSudoku too. So by applying the first 4 I will try to fix the XSudoku diagonals without destroying the Sudoku grid. But this will have to wait until next week. Btw., my program is written generally and works also for rectangular blocksizes. But I think XSudoku works best for quadradic blocksizes and I will restrict XSudoku to this kind of blocks.

[m_b_metcalf]

I'll look at the 16x16 problem very soon.

I think I've solved the problem. I quote from http://www.sudokuwiki.org/Intersection_Removal:

"A Pair or Triple in a box - if they are aligned on a row, n can be removed from the rest of the row."

Now examine the candidate values 3 in the top band of the 16x16 puzzle:

Code: Select all

  .  .  .  .  .  3  .  .  .  .  .  .  3  3  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  3  .  .  3
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .

In the normal course of events, the value 3 at r1c6 would be found as a naked single. However, we are suppressing singles so we pass into pointing. Your code finds box 2 in row 1 pointing to the two values in c13 and c14, and deletes them. But this is not the definition of pointing, which requires a pair or a triple to be aligned (in 9x9). There is no pointing here. Thus, my program doesn't make that elimination.

Hope we're converging.

Regards,

Mike Metcalf

[Pat]

I'll look at the 16x16 problem very soon.

I think I've solved the problem. I quote from http://www.sudokuwiki.org/Intersection_Removal:

"A Pair or Triple in a box - if they are aligned on a row, n can be removed from the rest of the row."

Now examine the candidate values 3 in the top band of the 16x16 puzzle:

Code: Select all

  .  .  .  .  .  3  .  .  .  .  .  .  3  3  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .  .  .  .  3  .  .  3
  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .

In the normal course of events,
the 3 at r1c6
would be found as a naked {correct to: hidden} single.
However, we are suppressing singles so we pass into pointing.
Your code finds box 2 in row 1 pointing to the two values in c13 and c14, and deletes them.

But this is not the definition of pointing, which requires a pair or a triple to be aligned (in 9x9). There is no pointing here. Thus, my program doesn't make that elimination.

Hope we're converging.

converging, yes.

for subsets, we already saw that you prefer the narrow definition
(excluding degenerate cases);
now we see the same idea for Pointing and Claiming.

ronk will be with you,
he wished the definition of fish to exclude degenerate cases---

whereas i prefer the broad definition
(as used by hkociemba)
-- for subsets, and for fish too.

[hkociemba]

I will try to put a condiditonal compiling directive into the code to to allow only pairs for pointing/claiming. But in the moment I am distracted by AL Zimmermann's programming contest http://azspcs.com/ which is much fun and which started yesterday and where I usually participate. But I intend to work in parallel on the Sudoku problem in the next weeks.

[hkociemba]

Hope we're converging.

I added the possibility to do pointing/claiming only if at least two candidates are involved. Now I get 731 candidates left which is still two less thant your 733. Here is the output:
block 3 candidates for number 5 all in row 3 (pointing): r3 c4 <> 5
block 3 candidates for number 9 all in row 2 (pointing): r2 c14c15c16 <> 9
block 2 candidates for number 6 all in column 8 (pointing): r5r7 c8 <> 6
block 2 candidates for number 11 all in column 5 (pointing): r11 c5 <> 11
block 2 candidates for number 13 all in column 8 (pointing): r14 c8 <> 13
block 13 candidates for number 15 all in column 2 (pointing): r9r11 c2 <> 15
block 15 candidates for number 14 all in column 11 (pointing): r9r10r11 c11 <> 14
row 3 candidates for number 3 all in block 4 (claiming): r1c13 r1c14 <> 3
row 5 candidates for number 6 all in block 5 (claiming): r7c1 r7c2 r8c1 r8c2 r8c3 r8c4 <> 6
row 5 candidates for number 15 all in block 6 (claiming): r6c6 r6c7 <> 15
row 6 candidates for number 9 all in block 8 (claiming): r5c13 r5c14 r5c16 <> 9
row 16 candidates for number 16 all in block 16 (claiming): r13c13 r13c14 r13c15 r13c16 r14c13 r14c15 r14c16 <> 16
column 3 candidates for number 5 all in block 5 (claiming): r5c4 r8c4 <> 5
column 7 candidates for number 15 all in block 10 (claiming): r9c6 r10c6 r11c5 <> 15
column 16 candidates for number 13 all in block 16 (claiming): r13c14 r15c14 <> 13
hidden tuple of size 2 with numbers 11, 12 in block 8: r5c16 <> 16 r6c15 <> 8,9

I hope it is not too difficult for you to see what still causes the difference.

[m_b_metcalf]

I hope it is not too difficult for you to see what still causes the difference.

It may not be too difficult, but I'm away most of the time for a week (3. Oktober!) and so can't run any tests. One difference is still the order of processing. I do claiming before pointing. Then also you appear to go through boxes looking along rows, and then go through the boxes again looking along the columns. I combine this. My algorithm is such that in each box I look for the extent of a value in its rows (rmin and rmax) and in its columns (cmin and cmax) and then have a construct

Code: Select all

     
   if(rmin == rmax .and. cmin  /= cmax) then
                  look along the columns outside the box
   else if(rmin /= rmax .and. cmin == cmax) then
                  look along the rows outside the box
   end if   

that does whichever is appropriate.

I would hope that the remaining small differences are due to that.

Regards,

Mike Metcalf

[hkociemba]

Ah, I used my order and not yours. I already have a routine that uses your order. Using your order I fortunately get 733 givens left:

hidden tuple of size 2 with numbers 11, 12 in block 8: r5c16 <> 9,16 r6c15 <> 8,9
block 3 candidates for number 5 all in row 3 (pointing): r3 c4 <> 5
block 3 candidates for number 9 all in row 2 (pointing): r2 c14c15c16 <> 9
block 2 candidates for number 6 all in column 8 (pointing): r5r7 c8 <> 6
block 2 candidates for number 11 all in column 5 (pointing): r11 c5 <> 11
block 2 candidates for number 13 all in column 8 (pointing): r14 c8 <> 13
block 13 candidates for number 15 all in column 2 (pointing): r9r11 c2 <> 15
block 15 candidates for number 14 all in column 11 (pointing): r9r10r11 c11 <> 14
row 3 candidates for number 3 all in block 4 (claiming): r1c13 r1c14 <> 3
row 5 candidates for number 6 all in block 5 (claiming): r7c1 r7c2 r8c1 r8c2 r8c3 r8c4 <> 6
row 5 candidates for number 15 all in block 6 (claiming): r6c6 r6c7 <> 15
row 16 candidates for number 16 all in block 16 (claiming): r13c13 r13c14 r13c15 r13c16 r14c13 r14c15 r14c16 <> 16
column 3 candidates for number 5 all in block 5 (claiming): r5c4 r8c4 <> 5
column 7 candidates for number 15 all in block 10 (claiming): r9c6 r10c6 r11c5 <> 15
column 16 candidates for number 13 all in block 16 (claiming): r13c14 r15c14 <> 13

Quite interesting that the order has an influence here. So I think the problem essentially is solved. I will work a bit more on the grid generation within the next weeks and then make my solver available.

[Pat]

all of this is very interesting when we disable "singles"

but we usually allow "singles"
-- and that's where the discrepancy arose
(in 144-squared)

degenarate case not possible,
order can't matter---

[Pat]

for diagnostics,
could you please post the known cells
at the point that your program stops?

then hkociemba could run his program
starting at that point---

That's a good idea that I'll come back to if my investigation gets no further.

My program---fails to complete the 144x144_triples puzzle,
stopping at the point as shown in the second attachment.

could you please provide
the list of possibilities
for each empty cell ?

then i'll try to sweet-talk hkociemba to accept this type of input---

my best guess is,
he will find a "hidden" trio
at the very first move

[m_b_metcalf]

I think you missed my post of Thu Sep 14, 2017 3:33 pm (CET). The 144x144 discrepancies are all long-since resolved.

M

[Pat]

right

actually i did see it --
and managed to miss
the significance of case 10