No new 17s within {-2+2}

Everything about Sudoku that doesn't fit in one of the other sections

Re: No new 17s within {-2+2}

Postby champagne » Tue Apr 29, 2014 12:35 pm

coloin wrote:Well done in completing that search. You have shown that there are no new 17s which have a maximum of 2 clues [ not 3] in all rows or columns or boxes in the puzzle.

Edit
unfortunatly it is not that easy - as usual
One would need to search all the max lex 18 clue patterns which begin with
11. ... ... and also max 2 clues in a box
one example ....
Code: Select all
+---+---+---+
|12.|...|...|
|...|34.|...|
|...|...|56.|
+---+---+---+
|7..|..1|...|
|..8|...|..2|
|...|.9.|..3|
+---+---+---+
|.4.|...|.9.|
|..5|...|8..|
|...|6.7|...|
+---+---+---+ 

which probably is a bigger task


C


Hi coloin,

I started with a different view on the patterns.
This is the split of existing patterns I gave earlier

Code: Select all
The split on row 1 (for the entire file) is the following
1111..1..   1
1111.....   387
111......   1847
11.11.1..   26
11.11....   1235
11.1..1..   6537
11.1.....   39031
11.......   86
1..1.....   2


In that split, I consider the max lexical canonical form of the pattern.
In that view, your example is part of the start 11....... 86

We have shown that the last start is fully covered.
In between, we could have puzzles with the start 1.. 1.. 1.. but none has been found so far.

I had 2 weeks off, and I was thinking before departure of ways to explore that part of the 17 (may be 18) clues field.

Likely to find nothing, but I think it makes sense to do it.

I drafted some code to go in that direction, but I am locked on other priorities for 2 or 3 days
champagne
2017 Supporter
 
Posts: 7336
Joined: 02 August 2007
Location: France Brittany

Re: No new 17s within {-2+2}

Postby coloin » Tue Apr 29, 2014 2:39 pm

Thanks for that - it has jogged me to clarify it furthur and it is doable.

Looking at my mock puzzle we see that this is just a 2-clue rookery template

There are 170 of these and you have searched some of them before
Hidden Text: Show
Code: Select all
.......XX....XX....XX.............XX....XX....XX.........X..X..X.....X..X..X.....
.......XX....XX....XX.............XX....XX...X.X.........X..X.....X..X..XX.......
.......XX....XX....XX.............XX....XX...X.X.........X..X...X....X..X..X.....
.......XX....XX....XX.............XX...X.X...X.X..........X.X.....X..X..XX.......
.......XX....XX....XX.............XX...X.X...X.X..........X.X...X....X..X..X.....
.......XX....XX....XX.............XX...X.X...X.X..........X.X...X.X.....X.....X..
.......XX....XX....XX.............XX..X..X....X..X.......X..X..X.....X..X..X.....
.......XX....XX....XX.............XX..X..X....X.X.........X.X..X.....X..X..X.....
.......XX....XX....XX.............XX..X..X....X.X........X..X..X.....X..X...X....
.......XX....XX....XX.............XX..X..X....X.X........XX....X.....X..X.....X..
.......XX....XX....XX.............XX..X..X...X..X.........X.X.....X..X..XX.......
.......XX....XX....XX.............XX..X..X...X..X.........X.X...X....X..X..X.....
.......XX....XX....XX.............XX..X..X...X..X........X..X...X..X....X.....X..
.......XX....XX....XX.............XX..XX......X.X..........XX..X.....X..X...X....
.......XX....XX....XX.............XX..XX......X.X.........XX...X.....X..X.....X..
.......XX....XX....XX.............XX..XX.....X....X.......X.X.....X..X..XX.......
.......XX....XX....XX.............XX..XX.....X....X.......X.X...X.X.....X.....X..
.......XX....XX....XX.............XX..XX.....X..X..........XX......X.X..XX.......
.......XX....XX....XX.............XX..XX.....X..X..........XX...X....X..X...X....
.......XX....XX....XX.............XX..XX.....X..X..........XX...X..X....X.....X..
.......XX....XX....XX.............XX..XX.....X..X.........XX....X....X..X.....X..
.......XX....XX....XX.............XXX..X.....X..X..........XX....X...X...X..X....
.......XX....XX....XX............X.X...X.X...X.X............XX....XX....XX.......
.......XX....XX....XX............X.X...X.X...X.X............XX..X..X....X..X.....
.......XX....XX....XX............X.X...X.X...X.X............XX..X.X.....X...X....
.......XX....XX....XX............X.X...X.X...X.X..........X..X..X....X..X..X.....
.......XX....XX....XX............X.X...X.X...X.X..........X.X...X.X.....X......X.
.......XX....XX....XX............X.X..X..X....X..X..........XX.X..X.....X..X.....
.......XX....XX....XX............X.X..X..X....X..X.......X...X.X.....X..X..X.....
.......XX....XX....XX............X.X..X..X....X.X...........XX.X...X....X..X.....
.......XX....XX....XX............X.X..X..X....X.X.........X..X.X.....X..X..X.....
.......XX....XX....XX............X.X..X..X....X.X.........X.X..X......X.X..X.....
.......XX....XX....XX............X.X..X..X....X.X........X...X.X.....X..X...X....
.......XX....XX....XX............X.X..X..X....X.X........X..X..X......X.X...X....
.......XX....XX....XX............X.X..X..X....X.X........XX....X......X.X.....X..
.......XX....XX....XX............X.X..X..X...X..X...........XX..X..X....X..X.....
.......XX....XX....XX............X.X..X..X...X..X.........X..X....X..X..XX.......
.......XX....XX....XX............X.X..X..X...X..X.........X..X..X....X..X..X.....
.......XX....XX....XX............X.X..X..X...X..X.........X.X.....X...X.XX.......
.......XX....XX....XX............X.X..X..X...X..X........X...X..X..X....X.....X..
.......XX....XX....XX............X.X..XX......X.X...........XX.X....X...X...X....
.......XX....XX....XX............X.X..XX......X.X..........X.X.X.....X..X...X....
.......XX....XX....XX............X.X..XX......X.X..........XX..X......X.X...X....
.......XX....XX....XX............X.X..XX.....X....X.........XX..X.X.....X...X....
.......XX....XX....XX............X.X..XX.....X....X.......X..X..X.X.....X.....X..
.......XX....XX....XX............X.X..XX.....X....X.......X.X.....X...X.XX.......
.......XX....XX....XX............X.X..XX.....X....X.......X.X...X.X.....X......X.
.......XX....XX....XX............X.X..XX.....X..X..........X.X..X....X..X...X....
.......XX....XX....XX............X.X..XX.....X..X..........X.X..X..X....X.....X..
.......XX....XX....XX............X.X..XX.....X..X..........XX...X.....X.X...X....
.......XX....XX....XX............X.X..XX.....X..X..........XX...X..X....X......X.
.......XX....XX....XX............X.XX..X.....X..X..........X.X...X...X...X..X....
.......XX....XX....XX...........X..X..X....X..X..X.......X..X..X.....X..X..X.....
.......XX....XX....XX...........X..X..X....X..X.X.........X.X..X.....X..X..X.....
.......XX....XX....XX...........X..X..X....X..X.X........X..X..X.....X..X...X....
.......XX....XX....XX...........X..X..X....X.X..X.........X.X...X....X..X..X.....
.......XX....XX....XX...........X..X..X....X.X..X........X..X...X..X....X.....X..
.......XX....XX....XX...........X..X..X...X...X.X.........X..X.X.....X..X..X.....
.......XX....XX....XX...........X..X..X...X...X.X........X..X..X......X.X...X....
.......XX....XX....XX...........X..X..X...X..X...X.......X...X..X....X..X..X.....
.......XX....XX....XX...........X..X..X...X..X...X.......X..X...X.X.....X......X.
.......XX....XX....XX...........X..X..X...X..X..X.........X..X..X....X..X..X.....
.......XX....XX....XX...........X..X..X...X..X..X........X..X...X..X....X......X.
.......XX....XX....XX...........X..XX......X.X...X.......X..X....X...X...X.X.....
.......XX....XX....XX...........X..XX......X.X..X.........X.X....X...X...X.X.....
.......XX....XX....XX...........X..XX......X.X..X........X..X....X...X...X..X....
.......XX....XX....XX...........XX....X...X...X.X........X....XX......X.X...X....
.......XX....XX....XX...........XX....XX.....X.......X....X.X...X.X.....X......X.
.......XX....XX....XX...........XX....XX.....X.......X...X...X..X....X..X...X....
.......XX..X..X.....X..X..........XX.X..X....X..X.........X.X.....X..X..XX.......
.......XX..X..X.....X..X..........XX.X..X....X..X.........X.X...X....X..X..X.....
.......XX..X..X.....X..X.........X.X.X..X....X..X...........XX..X..X....X..X.....
.......XX..X..X.....X..X.........X.X.X..X....X..X.........X..X....X..X..XX.......
.......XX..X..X.....X..X.........X.X.X..X....X..X.........X..X..X....X..X..X.....
.......XX..X..X.....X..X.......X...X...X...X.XX...........X.X...X....X..X..X.....
.......XX..X..X.....X..X.......X...X...X...X.XX..........XX.....X....X..X.....X..
.......XX..X..X.....X..X.......X...X...X..X..XX...........X..X..X....X..X..X.....
.......XX..X..X.....X..X.......X...X...X..X..XX..........X..X...X.....X.X...X....
.......XX..X..X.....X..X.......X...X...X..X..XX..........XX.....X.....X.X.....X..
.......XX..X..X.....X..X.......X...X.X.....X.X..X.........X.X.....X..X..XX.......
.......XX..X..X.....X..X.......X...X.X.....X.X..X.........X.X...X....X..X..X.....
.......XX..X..X.....X..X.......X...X.X.....X.X..X........X..X...X..X....X.....X..
.......XX..X..X.....X..X.......X...X.X....X..X..X.........X..X..X....X..X..X.....
.......XX..X..X.....X..X.......X...X.X....X..X..X........X..X...X..X....X......X.
.......XX..X..X.....X.X..........X.X.X...X...X...X..........XX..X.X.....X..X.....
.......XX..X..X.....X.X..........X.X.X...X...X...X.......X...X....X..X..XX.......
.......XX..X..X.....X.X..........X.X.X...X...X...X.......X...X..X....X..X..X.....
.......XX..X..X.....X.X..........X.X.X...X...X...X.......X..X...X.....X.X..X.....
.......XX..X..X.....X.X..........X.X.X...X...X..X...........XX..X..X....X..X.....
.......XX..X..X.....X.X..........X.X.X...X...X..X.........X..X....X..X..XX.......
.......XX..X..X.....X.X..........X.X.X...X...X..X.........X..X..X....X..X..X.....
.......XX..X..X.....X.X..........X.X.X...X...X..X.........X.X.....X...X.XX.......
.......XX..X..X.....X.X..........X.X.X...X...X..X.........X.X...X.....X.X..X.....
.......XX..X..X.....X.X..........X.X.X...X...X..X........X...X..X..X....X.....X..
.......XX..X..X.....X.X..........X.X.X...X...X..X........X..X...X..X....X......X.
.......XX..X..X.....X.X..........X.X.X...X...X..X........XX.....X.....X.X.....X..
.......XX..X..X.....X.X..........X.X.X...X...X..X........XX.....X....X..X......X.
.......XX..X..X.....X.X..........X.X.X.X.....X..X..........X.X.....X.X..XX.......
.......XX..X..X.....X.X..........X.X.X.X.....X..X..........X.X..X....X..X...X....
.......XX..X..X.....X.X..........X.X.X.X.....X..X..........XX...X.....X.X...X....
.......XX..X..X.....X.X.........X..X....X.X..XX..........X...X..X....X..X..X.....
.......XX..X..X.....X.X.........X..X....X.X..XX..........X..X...X.....X.X..X.....
.......XX..X..X.....X.X.........X..X...X...X.XX...........X.X...X....X..X..X.....
.......XX..X..X.....X.X.........X..X...X...X.XX..........X..X...X....X..X...X....
.......XX..X..X.....X.X.........X..X...X...X.XX..........XX.....X....X..X.....X..
.......XX..X..X.....X.X.........X..X...X..X..XX...........X..X..X....X..X..X.....
.......XX..X..X.....X.X.........X..X...X..X..XX..........X..X...X.....X.X...X....
.......XX..X..X.....X.X.........X..X...X..X..XX..........XX.....X.....X.X.....X..
.......XX..X..X.....X.X.........X..X.X.....X.X..X.........X.X.....X..X..XX.......
.......XX..X..X.....X.X.........X..X.X.....X.X..X........X..X...X..X....X.....X..
.......XX..X..X.....X.X.........X..X.X....X..X...X.......X...X..X....X..X..X.....
.......XX..X..X.....X.X.........X..X.X....X..X...X.......X..X...X.X.....X......X.
.......XX..X..X.....X.X.........X..X.X....X..X..X.........X..X..X....X..X..X.....
.......XX..X..X.....X.X.........X..X.X....X..X..X........X..X...X..X....X......X.
.......XX..X..X.....X.X.........X..X.X....X..X..X........XX.....X....X..X......X.
.......XX..X..X.....X.X.........XX......X.X..XX..........X....X.X.....X.X..X.....
.......XX..X..X.....X.X.........XX.....X....XXX...........X.X...X.....X.X..X.....
.......XX..X..X.....X.X.........XX.....X....XXX..........XX.....X.....X.X.....X..
.......XX..X..X.....X.X.........XX...X......XX...X.......X...X..X.X.....X.....X..
.......XX..X..X.....X.X.........XX...X......XX...X.......X..X...X.....X.X..X.....
.......XX..X..X.....X.X.........XX...X......XX..X.........X.X...X.....X.X..X.....
.......XX..X..X.....X.X.........XX...X......XX..X........X...X..X..X....X.....X..
.......XX..X..X.....X.X.........XX...X......XX..X........XX.....X.....X.X.....X..
.......XX..X..X.....X.X........XX....X......XX.....X.....X...X..X.X.....X.....X..
.......XX..X..X.....X.X........XX....X......XX.....X.....X..X...X.....X.X..X.....
.......XX..X..X.....X.X........XX....X....X..X.....X.....X....X...X...X.XX.......
.......XX..X..X.....X.X.......X....X.X....X..X....X......X...X..X....X..X...X....
.......XX..X..X.....X.X.......X....X.X....X..X....X......XX.....X....X..X......X.
.......XX..X..X.....X.X.......X..X...X......XX....X......X..X...X.....X.X...X....
.......XX..X..X.....X.X.......X..X...X......XX....X......XX.....X.....X.X.....X..
.......XX..X..X.....X.X.......X.X....X......XX.....X.....XX.....X.....X.X.....X..
.......XX..X..X....X..X..........X.X..X..X....X..X.......X...X.X.....X..X..X.....
.......XX..X..X....X..X..........X.X..X..X....X.X.........X..X.X.....X..X..X.....
.......XX..X..X....X..X..........X.X..X..X....X.X.........X.X..X......X.X..X.....
.......XX..X..X....X..X..........X.X..X..X...X..X...........XX..X..X....X..X.....
.......XX..X..X....X..X..........X.X..X..X...X..X.........X..X....X..X..XX.......
.......XX..X..X....X..X..........X.X..X..X...X..X.........X..X..X....X..X..X.....
.......XX..X..X....X..X..........X.X..X..X...X..X.........X.X.....X...X.XX.......
.......XX..X..X....X..X..........X.X..XX.....X...X..........XX..X.X.....X....X...
.......XX..X..X....X..X..........X.X..XX.....X...X.........X.X....X..X..XX.......
.......XX..X..X....X..X..........X.X..XX.....X...X.........X.X..X.X.....X.....X..
.......XX..X..X....X..X..........X.X..XX.....X...X.........XX.....X...X.XX.......
.......XX..X..X....X..X..........X.X..XX.....X...X.........XX...X.X.....X......X.
.......XX..X..X....X..X.........X..X....X.X..X.X.........X...X..X....X..X..X.....
.......XX..X..X....X..X.........X..X....X.X..X.X.........X..X...X.X.....X......X.
.......XX..X..X....X..X.........X..X....X.X..XX..........X...X...XX.....X.....X..
.......XX..X..X....X..X.........X..X...X..X..X.X..........X..X..X....X..X..X.....
.......XX..X..X....X..X.........X..X...X..X..X.X.........X..X...X..X....X......X.
.......XX..X..X....X..X.........X..X...X..X..X.X.........XX.....X....X..X......X.
.......XX..X..X....X..X.........X..X...X..X..XX...........X..X...XX.....X.....X..
.......XX..X..X....X..X.........X..X...X..X..XX..........X..X....X....X.X...X....
.......XX..X..X....X..X.........X..X..X...X...X.X.........X..X.X.....X..X..X.....
.......XX..X..X....X..X.........X..X..X...X...X.X........X..X..X......X.X...X....
.......XX..X..X....X..X.........X..X..X...X..X...X.......X..X...X.X.....X......X.
.......XX..X..X....X..X.........X..X..X...X..X..X.........X..X..X....X..X..X.....
.......XX..X..X....X..X.........X..X..X...X..X..X........X..X...X..X....X......X.
.......XX..X..X....X..X.........X..X.X..X....X.....X.....X...X...XX.....X.....X..
.......XX..X..X....X..X.........X..X.X..X....X.....X.....X..X....X....X.X..X.....
.......XX..X..X....X..X.........X..X.X.X.....X.....X......X..X...XX.....X.....X..
.......XX..X..X....X..X.........X..X.X.X.....X.....X.....X..X....X....X.X...X....
.......XX..X..X....X..X.........XX.....X....XXX...........X.X....XX.....X......X.
.......XX..X..X....X..X.........XX.....X....XXX..........X...X...X...X..X...X....
.......XX..X..X....X..X.........XX.....X....XXX..........XX......X...X..X......X.
.......XX..X..X....X..X.........XX...X..X....X.......X...X...X...X...X..X..X.....
.......XX..X..X....X..X.........XX...X.X.....X.......X....X.X....XX.....X......X.
.......XX..X..X....X..X.........XX...X.X.....X.......X...X...X...X...X..X...X....
.......XX..X..X....X..X.......X....X..X..X...X.....X.....X...X..X..X....X.....X..
.....X..X..X....X..X..X.........X..X..X...X..X..X.........X..X..X....X..X..X.....  - searched
.....X..X..X....X..X..X.........XX...X.X.....X......X.....X.X....XX.....X.......X  - searched
.....X..X..X....X..X..X........X.X....XX.....X.......X...X...X..X....X..X....X...  - searched


EDIT

except that there are other patterns of 2 clues per box/row/colunm
Code: Select all
+---+---+---+
|12.|...|...|
|...|12.|...|
|...|...|12.|
+---+---+---+
|...|2.x|...|
|21.|...|...|
|...|...|21.|
+---+---+---+
|..1|...|..2|
|..2|..1|...|
|...|.x.|..1|
+---+---+---+

One can see that a 2 rookery doent fit in this pattern ......
hmmm not sure how many there will be now at all

The object is to find all 18-puzzles with distribution [box, row and column] 222222222 and by inference all 17-puzzles with [brc] distribution 222222221

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby Afmob » Fri May 02, 2014 5:40 am

I started analyzing those patterns but the progress so far is quite slow since these patterns have a lot of ED puzzles and the computers are also doing other stuff. I'll edit this post when I get new puzzles or the computation is finished.

Edit: Computation is finished. It took longer than expected which is due to the large number of ED puzzles per pattern.

Valid 18 clue puzzles of the first 167 patterns: Show
.......12....34....56.............34..7..8....9.6........1..5..2.....8..4...2....
.......12....34....56.............37..5..2...7..1.........7.6.....8..2..24.......
.......12....34....35.............46..7..2...8..4.........5.7...4....2..6..7.....
.......12....34....56.............36..7..8...6..2.........6.7...3....8..4..5.....
.......12....34....56.............36..7..1...6..8........5..1...3..6....4.....8..
.......12....34....56.............67..32.....8..7..........63...7..5....9.....4..
.......12....34....56............5.7..4..8....7.6.........2..3.5.....4..2..7.....
.......12....34....56............7.8..9..6....8.5.........8.4..4......6.2..7.....
.......12....13....45............6.7..8..5....3.4........8...5.7.....8..2...7....
.......12....34....56............3.7..8..6....7.5........6...5.3.....4..2...7....
.......12....34....56............3.4..7..8...9..2.........6..7..4....8..8..7.....
.......12....34....56............5.4..7..1...8..4.........6..7..4....6..3..2.....
.......12....34....56............5.4..7..2...8..4.........6..7..4....6..3..2.....
.......12....34....56............5.3..3..1...7..2.........5.6.....1...8.34.......
.......12....34....56............5.3..3..2...7..8.........5.6.....9...8.34.......
.......12....34....56............4.5..1..7...2..4........6...7..4..5....3.....8..
.......12....34....56............5.4..17.....7....8.......5.6...8.2.....4......8.
.......12....34....56............5.4..21.....7....2.......5.6...2.8.....4......9.
.......12....34....56............5.4..27.....1....8.......5.6...8.1.....4......8.
.......12....34....56............7.5..81.....4....7.......5.6...7.2.....8......4.
.......12....34....56............5.3..72.....8..3..........6.7..3....6..4...2....
.......12....34....56............5.4..71.....8..4..........87...4.....2.3...7....
.......12....34....56............5.6..17.....6..3..........61...3.....7.8...2....
.......12....34....56............4.37..1.....8..3..........8.7...3...1...2..9....
.......12....34....56...........5..3..4....7..8.1.........7.6..5.....4..3..2.....
.......12....34....56...........7..8..3....9..1.4........2..1..7.....4..8...1....
.......12....34....56...........5..4..7....5.8..7........5..7...3..6....1.....8..
.......12....34....56...........2..6..7...8..2...5.......7..1...2.6.....1......3.
.......12....34....56...........2..6..7...8..2...5.......7..4...2.6.....1......3.
.......12....34....35...........2..1..3...6..6..7.........6..7..4....8..2..1.....
.......12....34....35...........2..1..3...6..6..7.........6..7..8....4..2..1.....
.......12....34....56...........7..4..8...3..6..1.........8..6..4....7..7..9.....
.......12....34....56...........1..5..7...8..9..5........6..7...1..2....3......9.
.......12....34....56...........1..6..7...8..8..2........7..6...4..8....1......4.
.......12....32....45...........6..34......7.1..8.........4.2....3...6...8.1.....
.......12....34....56...........3..65......4.7..8.........5.8....4...3...1.7.....
.......12....34....56...........3..67......4.8..2.........7.2....4...3...1.5.....
.......12....34....15...........26....3...4...2.7........5....73......8.6...4....
.......12....34....25...........36....7...4...8.6........5....73......4.8...7....
.......12....34....56...........27....3...4...8.6........5....63......5.7...4....
.......12....34....56...........37....8...4...2.7........6....83......4.9...8....
.......12....23....45...........46....16.....7.......8....1.5...6.8.....3......4.
.......12....34....56...........13....27.....8.......4...9...6..4....1..3...2....
.......12....34....56...........14....15.....7.......3...6...5..3....8..4...7....
.......12....34....56...........17....15.....2.......4...6...5..8....9..4...2....
.......12....34....56...........35....21.....7.......4...2...5..4....3..8...9....
.......12....34....56...........35....76.....2.......4...8...5..3....4..1...2....
.......12....34....56...........35....78.....2.......4...9...5..3....4..1...2....
.......12....34....56...........53....76.....8.......4...7...6..3....5..4...1....
.......12....34....56...........56....12.....7.......3...6...5..8....4..3...1....
.......12..2..3.....4..5.........3.6.7..5....1..4.........2..4..3....5..8..6.....
.......12..2..3.....4..5.........4.6.7..8....2..1.........2..4..9....5..7..6.....
.......12..2..3.....4..5.........5.6.7..3....1..4.........2..4..5....3..8..6.....
.......12..3..4.....5..6.........3.6.3..1....7..2.........5..3..6....4..2..8.....
.......12..3..2.....4..5.......3...6...7..2..14...........8..4..5....3..2..6.....
.......12..3..4.....5..6.......4...3...7..2..17...........5..6..8....4..2..3.....
.......12..3..1.....4..5.......6...4...7..6..13..........4..3...8.....9.2...7....
.......12..3..2.....4..5.......2...6...7..5..54..........3..4...2.....8.6...7....
.......12..3..2.....4..5.......3...6...7..8..51..........8..4...2.....5.6...2....
.......12..3..1.....4..5.......6...3.5.....4.1..7.........8.7.....2..1..23.......
.......12..3..4.....5..6.......3...4.7.....6.1..5.........6.5.....8..1..29.......
.......12..3..4.....5..6.......3...4.7.....6.1..5.........6.5.....8..1..82.......
.......12..3..4.....5..6.......3...4.7.....6.1..5.........6.5.....8..1..92.......
.......12..2..3.....4..5.......4...3.6.....5.7..2.........5.2...1....7..8..1.....
.......12..3..4.....5..6.......2...3.3.....4.7..8.........5.3...4....6..1..7.....
.......12..3..4.....5..6.......3...5.4.....6.7..8.........6.3...5....8..2..9.....
.......12..3..4.....5..6.......4...5.7.....4.1..8.........5.3...6....4..8..2.....
.......12..3..4.....5..6.......4...5.7.....8.1..5.........5.9...6....4..3..2.....
.......12..3..4.....5..6.......3...5.7.....6.1..4........8..1...5..2....2.....4..
.......12..3..4.....5..6.......3...5.4....6..1..7.........6..7..5....4..2..8.....
.......12..3..4.....5..6.......1...3.7....2..1..4........8..5...3..2....6......4.
.......12..3..4.....5..6.......1...3.7....2..1..6........8..5...3..2....4......6.
.......12..3..4.....5..6.......1...7.4....6..5..8........3..5...9..8....8......6.
.......12..3..4.....5.6..........5.7.1...2...7...8.......5..3...2.....4.4..7.....
.......12..3..4.....4.5..........6.1.5...7...1..6...........37..8..1....7..2.....
.......12..3..4.....1.5..........4.5.6...7...8..2.........4..9....1..3..27.......
.......12..3..4.....5.3..........6.7.8...2...7..1.........7..4....6..5..24.......
.......12..3..4.....5.6..........7.8.9...1...7..2.........7..4....8..5..14.......
.......12..1..3.....4.5..........6.3.7...5...8..1.........6..8..3....5..7..2.....
.......12..1..3.....4.5..........6.5.5...6...7..1.........8..7..3....5..6..2.....
.......12..3..1.....4.5..........5.4.1...6...7..2.........4..6..2....1..8..3.....
.......12..3..4.....2.5..........5.3.4...6...7..1.........8..4..1....6..3..2.....
.......12..3..4.....2.5..........6.5.5...6...7..1.........8..7..4....5..6..2.....
.......12..3..4.....5.6..........5.4.7...8...2..1.........5..9..4....8..8..2.....
.......12..3..4.....1.5..........3.5.5...6...4..2.........7.8.....1...3.26.......
.......12..3..4.....1.5..........3.5.6...7...8..2.........8.6.....1...8.27.......
.......12..3..4.....1.5..........6.5.5...7...4..2.........8.3.....1...6.27.......
.......12..3..4.....5.1..........6.1.7...8...6..2.........6.5.....9...8.28.......
.......12..3..4.....5.6..........6.5.6...7...8..1.........5.4.....9...7.17.......
.......12..3..4.....5.6..........7.3.8...1...7..2.........7.4.....9...5.14.......
.......12..3..4.....5.6..........7.5.8...1...7..2.........7.4.....9...3.14.......
.......12..3..4.....5.6..........7.6.6...2...4..1.........7.5.....3...8.21.......
.......12..3..4.....5.6..........7.6.6...2...8..1.........7.8.....3...9.21.......
.......12..3..4.....5.6..........7.6.8...1...7..2.........7.4.....3...5.14.......
.......12..3..2.....4.5..........4.5.6...7...8..1.........3.5...2.....8.6..4.....
.......12..3..4.....4.5..........6.5.3...2...6..1.........6.7...1.....3.2..8.....
.......12..3..4.....5.6..........3.4.5...2...7..1.........3.5...1.....8.2..6.....
.......12..3..4.....5.6..........3.5.7...2...8..1.........5.6...1.....7.2..9.....
.......12..3..4.....5.6..........3.6.6...7...2..1.........5.4...1.....7.7..8.....
.......12..3..4.....5.6..........3.6.6...7...8..1.........5.4...1.....7.7..8.....
.......12..3..4.....5.6..........4.6.7...2...3..1.........5.7...2.....4.1..8.....
.......12..3..4.....5.6..........5.3.7...2...8..1.........3.6...1.....7.2..9.....
.......12..3..4.....5.6..........5.6.2...7...4..1.........3.6...1.....8.9..5.....
.......12..3..4.....5.6..........5.6.2...7...4..2.........3.6...1.....8.9..5.....
.......12..3..4.....5.6..........5.6.2...7...8..1.........3.6...1.....8.4..5.....
.......12..3..4.....5.6..........5.6.2...7...8..1.........3.6...1.....8.9..5.....
.......12..3..4.....5.6..........5.6.2...7...8..1.........3.6...9.....8.7..5.....
.......12..3..4.....5.6..........5.6.7...2...8..1.........5.4...1.....8.2..9.....
.......12..3..4.....5.6..........5.7.6...2...7..1.........7.6...4.....2.2..8.....
.......12..3..4.....5.6..........6.3.1...6...7..8.........3.5...4.....6.8..2.....
.......12..3..4.....5.6..........6.3.1...6...7..8.........3.5...4.....6.9..2.....
.......12..3..4.....5.6..........6.3.7...1...6..8.........3.5...1.....8.8..2.....
.......12..3..4.....5.6..........6.5.4...1...6..7.........5.8...1.....7.7..2.....
.......12..3..4.....5.6..........6.5.7...1...6..8.........5.3...1.....8.8..2.....
.......12..3..4.....5.6..........6.5.7...2...1..7.........3.5...4.....8.2..6.....
.......12..3..4.....5.6..........6.5.7...2...8..9.........3.5...4.....8.2..6.....
.......12..3..4.....5.6..........7.3.5...8...4..1.........3.5...8.....9.1..2.....
.......12..3..4.....5.6..........7.3.8...2...7..1.........7.9...4.....2.2..9.....
.......12..3..4.....5.6..........7.5.3...8...4..1.........5.3...8.....9.1..2.....
.......12..3..4.....5.6..........7.5.3...8...6..1.........5.3...4.....6.7..2.....
.......12..3..4.....5.6..........7.5.3...8...6..1.........5.3...8.....6.7..2.....
.......12..3..4.....5.6..........7.5.3...8...7..1.........5.3...9.....8.1..2.....
.......12..3..4.....5.6..........7.6.6...2...8..1.........7.3...2.....5.1..9.....
.......12..3..4.....2.5..........3.6.2...1...7..8........2...3..8..6....5.....4..
.......12..3..4.....2.5..........5.6.7...8...3..7........2...3..4..6....8.....4..
.......12..3..4.....2.5..........5.6.7...8...3..9........2...3..4..6....8.....4..
.......12..3..4.....5.3..........6.7.8...1...7..2........6...5..4..7....1.....4..
.......12..3..4.....5.6..........6.4.7...8...3..1........2...3..2..4....6.....5..
.......12..3..4.....5.6..........6.4.7...8...5..1........2...5..2..4....6.....3..
.......12..3..4.....5.6..........7.6.8...3...7..9........8...3..2..7....6.....4..
.......12..3..4.....5.6..........7.8.9...2...7..1........8...3..4..7....2.....4..
.......12..3..4.....5.6..........7.8.9...2...8..1........7...3..4..8....2.....4..
.......12..3..4.....5.6..........2.4.7...8...5..7........3..5...4..2....8......6.
.......12..3..4.....5.6..........6.7.1...2...7..8........5..3...2..7....6......4.
.......12..3..4.....5.6..........7.8.5...2...7..1........9..5...4..7....2......4.
.......12..3..2.....4.5.........6..7....3.8..15..........8..4...7.....5.2..1.....
.......12..2..3.....4.5.........5..6...7...8.27...........2.4...3....5..9..6.....
.......12..3..4.....2.5.........6..7...1...8.85...........8.3...4....5..7..2.....
.......12..3..4.....5.6.........1..3...2...7.87..........3..5...1....4..4...7....
.......12..3..4.....5.1.........5..6...7..8..13...........2..3..8....4..2..6.....
.......12..3..4.....5.6.........7..4...1..3..18...........8..6..4....7..7..2.....
.......12..3..4.....5.6.........7..6...8..3..26...........2..8..9....7..7..1.....
.......12..3..2.....4.5.........3..6...7..8..51..........8..4...2.....5.6...2....
.......12..3..4.....5.3.........5..6...7..8..37..........3..5...2.....4.6...2....
.......12..3..4.....5.6.........1..7...3..5..61..........7..8...4.....6.7...2....
.......12..3..4.....5.6.........7..6...8..5..62..........1..7...7.....8.4...2....
.......12..3..4.....5.6.........7..6...8..5..62..........1..8...7.....4.4...2....
.......12..3..4.....5.1.........5..6...7..8..31..........62.....2.....3.9.....4..
.......12..3..1.....4.5.........4..3.5.....6.7..8.........7.4.....5..8..41.......
.......12..3..4.....1.5.........6..3.1.....7.4..2........1..2...8..7....5.....9..
.......12..3..4.....5.1.........6..3.1.....5.7..4........1..3...2..5....8.....4..
.......12..3..4.....5.1.........6..3.1.....5.7..4........1..4...2..5....8.....3..
.......12..3..4.....5.6.........5..3.6.....4.1..7........2..1...8..1....5.....7..
.......12..3..4.....5.6.........7..3.6.....5.8..4........6..4...1..5....9.....3..
.......12..3..4.....5.6.........3..5.7....4..1...8.......4..3...5.7.....6......7.
.......12..3..4.....5.6.........5..3.7....6..8...1.......1..4...2.7.....4......5.
.......12..3..1.....4.5.........4..3.5....6..6..7.........6..5..8....4..1..2.....
.......12..3..4.....4.5.........6..7.5....3..1..2.........1..2..8....6..6..9.....
.......12..3..4.....4.5.........6..7.5....8..1..2.........1..2..4....6..6..7.....
.......12..3..4.....4.5.........6..7.8....5..1..2.........1..2..4....6..6..7.....
.......12..3..4.....5.6.........2..1.5....7..7..8.........7..6..6....5..2..1.....
.......12..3..4.....5.6.........2..1.6....7..7..8.........7..9..4....8..2..1.....
.......12..3..4.....5.6.........2..5.6....7..7..1.........7..8..4....6..1..2.....
.......12..3..4.....5.6.........2..7.6....8..8..1.........8..7..4....6..1..2.....
.......12..3..4.....1.5.........6..3.7....2..1..5........4..1...3..2....8......5.
.......12..3..4.....1.5.........6..3.7....2..1..5........8..1...3..2....4......5.
.......12..3..4.....5.6.........1..3.6....4..1..7........5..3...8..4....9......7.
.......12..3..4.....5.6.........1..5.7....8..8..2........9..5...4..8....1......4.
.......12..3..4.....5.6.........3..5.6....4..1..2........7..3...7..1....8......2.
.......12..3..4.....5.6.........3..7.6....8..8..1........7..5...7..8....4......6.
.......12..3..4.....5.6.........5..3.7....4..1..7........3..8...5..4....6......7.
.......12..3..4.....1.5.........6..1.5....4..7..3........74.....7....5..2......8.
.......12..3..4.....4.5.........6..7.5....8..1..2........61.....7....9..6......2.
.......12..3..4.....5.6.........7..8.6....9..9..1........89.....8....5..4......6.
.......12..2..3.....4.5.........52.....1....637...........4.3...8.....5.6..2.....
.......12..3..4.....5.2.........67.....5....814...........8.3...9.....4.2..1.....
.......12..3..4.....5.2.........35...1......67...5.......6...7..2.1.....8.....3..
.......12..3..4.....5.6.........35...1......77...8.......7...3..2.1.....9.....8..
.......12..3..4.....5.6.........73...6......51...2.......5...7..2.6.....8.....4..
.......12..3..4.....5.6.........73...6......54...2.......5...7..2.6.....8.....1..
.......12..3..4.....5.6.........73...6......58...1.......5...7..2.6.....4.....1..
.......12..3..4.....5.6.........73...6......58...2.......5...7..2.6.....4.....1..
.......12..3..4.....5.6.........73...8......52...1.......3..4...6.....2.1..5.....
.......12..3..4.....5.6.........35...7......68..1.........7.8...5.....3.1..2.....
.......12..3..4.....5.6.........76...6......82..1.........8.4...7.....5.8..2.....
.......12..2..3.....4.5.........56...1......78..2........1...8..6..7....5.....3..
.......12..3..1.....4.5.........65...5......73..8........2...3..2..7....9.....4..
.......12..3..4.....5.2.........35...1......64..7........6...3..2..1....8.....7..
.......12..3..4.....5.6.........35...1......62..7........2...3..6..1....4.....8..
.......12..3..4.....5.6.........35...1......67..8........2...3..6..1....5.....7..
.......12..3..4.....5.6.........35...7......86..2........1...3..2..8....8.....4..
.......12..3..4.....5.6.........53...7......89..1........7...5..2..1....5.....9..
.......12..3..4.....5.6.........73...6......42..8........3...5..4..2....6.....7..
.......12..1..3.....4.5.........65...1......47..1........24.....3.....7.8.....6..
.......12..3..4.....5.1.........35...1......67..4........62.....2.....8.3.....4..
.......12..3..4.....5.1.........65...1......77..4........27.....6.....4.3.....8..
.......12..2..3.....1.4.......1....5.3....4..6....7......8...7..7....3..1...2....
.......12..3..4.....4.5.......1....6.6....7..1....8......3...8..4....3..2...6....
.......12..1..3.....4.5.......1....6.6....5..4....7......26.....7....1..8......4.
.......12..3..1.....4.5.......6....3.7....5..1....8......23.....2....1..9......8.
.......12..2..3.....4.5.......2..4...1......65....1......7..8...3.....5.8...6....
.......12..2..3.....4.5.......2..6...1......75....1......8..4...3.....5.4...7....
.......12..2..3.....4.5.......2..6...1......75....1......8..9...3.....5.9...7....
.......12..3..2.....4.5.......3..4...1......65....1......6..7...2.....5.8...3....
.......12..3..2.....4.5.......3..6...1......75....1......7..4...2.....5.8...9....
.......12..3..2.....4.5.......6..3...1......75....1......7..4...2.....5.8...9....
.......12..3..2.....4.5.......6..7...1......85....1......8..4...2.....5.7...6....
.......12..3..4.....5.6.......1..7...8......66....2......7..3...2.....4.4...8....
.......12..3..4.....5.6.......3..2...1......76....1......8..5...4.....6.2...7....
.......12..3..4.....5.6.......5..3...6......41....7......8..1...2.....7.4...2....
.......12..3..2.....4.5.......6..4...3......57....1......34.....8.....7.2.....1..
.......12..3..2.....4.5.......6..7...1......85....1......96.....2.....5.8.....4..
.......12..3..4....4..5..........2.5..5..3....6.7.........2..8.4.....5..7..1.....
.......12..3..4....1..5..........6.5..7..8...6..2.........6..3....1..9..45.......
.......12..3..4....5..6..........2.7..5..2...1..8.........3..5..4....6..2..7.....
.......12..3..4....5..6..........5.4..7..6...1..2.........3..8..4....6..2..9.....
.......12..3..4....1..5..........6.3..5..7...8..2.........8.3.....1...8.72.......
.......12..3..4....5..1..........4.3..62.....1...7.........3.7..8.5.....2.....1..
.......12..3..4....5..6..........4.3..71.....2...8.........3.7..8.2.....1.....6..
.......12..1..3....4..5..........6.3..72.....3...8.........69.....1...7.82.......
.......12..3..4....1..5..........4.6..71.....5...7.........83.....2...9.45.......
.......12..3..4....2..5..........4.5..67.....1...8.........23.....1...8.85.......
.......12..3..4....4..5..........5.6..71.....8...6.........97.....2...8.26.......
.......12..3..4....5..6..........4.6..71.....8...2.........53.....8...2.26.......
.......12..3..4....5..6..........4.6..72.....1...8.........53.....9...8.86.......
.......12..2..1....3..4..........3.1..56.....7...8.........59...1.2.....6......8.
.......12..2..3....4..5..........4.6..17.....8...3.........68...6.2.....5......3.
.......12..2..3....4..5..........4.6..71.....8...3.........69...6.2.....5......3.
.......12..3..4....2..5..........6.5..72.....4...8.........73...8.1.....2......7.
.......12..2..3....4..5.........4..6....7.3..1.8.........2...8..3....7..6..8.....
.......12..2..3....4..5.........4..6....7.3..1.8.........2...8..3....9..6..8.....
.......12..2..3....4..5.........5..6....4.7..1.8.........2...8..7....3..4..8.....
.......12..3..4....5..6.........3..5....7.6..47..........2...7...25.....8.....4..
.......12..3..4....5..6.........3..5....7.6..78..........2...7...25.....9.....8..
.......12..3..4....5..1.........6..7...7..3..2.8..........2..8..6....4..1..5.....
.......12..2..3....4..5.........1..6...2..7..1.5.........8..4...6..9....3......5.
.......12..2..3....4..5.........1..6...2..7..1.5.........8..4...9..6....3......5.
.......12..3..4....5..1.........3..6...7..8..1.5.........5..3...6..2....2......4.
.......12..3..4....5..6.........7..3...8..5..1.9.........1..7...1..9....7......4.
.......12..3..4....2..5.........6..4...7..3..18...........1..8...62.....4.....6..
.......12..3..4....5..6.........3..5...7..2..17...........8..7...51.....2.....4..
.......12..3..4....5..6.........3..7...8..2..26...........2..6...91.....8.....5..
.......12..3..4....5..6.........7..4...8..3..12...........1..5...72.....4.....7..
.......12..3..4....5..6.........7..5...3..2..18...........8..6...25.....3.....7..
.......12..3..1....4..5.........3..4...6..5..27..........4..7....8....3.1...7....
.......12..3..1....4..5.........3..4...6..5..78..........4..8....2....3.1...8....
.......12..3..2....4..5.........3..4...6..5..17..........4..7....8....3.2...7....
.......12..3..2....4..5.........3..4...6..5..17..........4..7....8....9.2...7....
.......12..3..4....5..1.........3..5...6..4..17..........5..7....8....3.2...7....
.......12..3..4....5..6.........3..5...7..6..18..........5..8....9....3.2...8....
.......12..3..4....5..6.........5..7...3..8..16..........1..5....2....4.7...2....
.......12..3..4....5..6.........7..3...2..8..19..........1..7....7....4.3...9....
.......12..3..4....5..6.........7..4...3..2..18..........5..3....7....6.4...2....
.......12..3..4....5..6.........7..4...3..2..68..........5..3....7....6.4...2....
.......12..3..4....5..6.........7..4...3..2..89..........5..3....7....6.4...2....
.......12..3..4....1..5.........1..6..5...3...7.8........5..4..6......8.1...2....
.......12..3..4....1..5.........1..6..5...7...4.8........5..4..6......8.1...2....
.......12..3..4....1..5.........6..5..7...6...8.2........1..8..5......4.6...7....
.......12..3..4....1..5.........6..7..5...4...8.2........1..3..6......4.4...7....
.......12..3..4....2..3.........5..3..6...7...8.1........2..6..3......4.5...7....
.......12..3..4....5..6.........3..7..6...8...8.1........7..5..3......6.7...8....
.......12..3..4....5..6.........3..7..6...8...8.1........7..5..4......6.7...8....
.......12..3..4....5..6.........7..8..6...4...1.2........7..3..7......2.8...1....
.......12..3..4....5..6.........7..8..6...9...9.1........8..5..4......6.8...9....
.......12..1..3....4..5.........4..1..6...7..8...2.......7..5...1.2.....5......8.
.......12..3..2....4..5.........6..3..4...7..8...1.......4..3...6.7.....2......6.
.......12..3..4....5..2.........6..7..7...5..1...8.......5..3...9.7.....2......8.
.......12..1..3....4..5.........6..3..4...5..2..1.........7..4..5....8..6..2.....
.......12..3..2....4..5.........6..3..4...5..1..7.........3..4..6....1..8..2.....
.......12..3..4....5..6.........2..1..5...7..7..8.........7..6..6....5..2..1.....
.......12..3..4....5..6.........2..1..6...7..7..8.........7..3..4....5..2..1.....
.......12..3..4....5..6.........5..3..7...2..1..6.........7..5..3....4..2..8.....
.......12..3..4....5..6.........5..3..7...2..8..6.........7..5..3....4..2..9.....
.......12..3..4....5..6.........5..7..6...8..8..3.........8..6..7....5..2..7.....
.......12..3..4....5..6.........6..4..7...5..1..2.........7..3..4....6..2..8.....
.......12..3..4....5..6.........6..4..7...8..1..2.........7..3..4....6..2..8.....
.......12..2..3....4..5.........6..4..7...5..1..2........8..7...1..4....3......2.
.......12..3..4....4..5.........6..7..7...5..1..2........7..3...2..3....8......4.
.......12..3..4....5..2.........6..4..7...8..9..1........7..3...2..1....6......7.
.......12..3..4....5..6.........1..5..7...6..2..3........5..7...1..2....8......3.
.......12..3..4....5..6.........3..7..6...8..8..1........7..5...7..8....4......6.
.......12..3..4....5..6.........7..4..8...3..1..8........6..7...4..2....2......8.
.......12..3..4....5..6.........7..8..6...4..3..1........2..3...4..8....7......4.
.......12..3..4....5..6.........7..8..8...6..1..2........8..3...2..3....9......5.
.......12..3..4....5..6.........7..8..8...9..1..2........8..3...2..3....9......4.
.......12..3..2....4..5.........3..4.6..1....7.....5.....4..6....1....8.2..6.....
.......12..3..4....5..6.........1..7.1..3....5.....8.....7..4....8....3.7..2.....
.......12..3..4....5..6.........7..3.8..3....2.....6.....2..8....9....3.1..6.....
.......12..3..4....5..6.........1..4.7.8.....6.....7.....2..5....4....6.9...7....
.......12..3..4....5..6.........2..4.7.8.....6.....7.....1..5....4....6.9...7....
.......12..3..4....5..6.........3..4.7.1.....6.....7.....2..5....4....6.8...7....
.......12..3..4....5..6.........3..7.1.8.....8.....6.....2..3....4....8.1...7....
.......12..3..4....5..6.........5..3.1.7.....6.....4.....8..3....5....6.2...4....
.......12..1..3....4..5.........45.....1....647...........7.4....62.....3......8.
.......12..2..3....4..5.........62.....1....783...........9.4....72.....6......3.
.......12..2..3....4..5.........63.....2....718...........8.4....71.....9......5.
.......12..2..3....4..5.........67.....2....318...........8.4....31.....4......5.
.......12..2..3....4..5.........67.....2....318...........8.4....31.....6......5.
.......12..2..3....4..5.........67.....2....819...........9.3....81.....3......5.
.......12..2..3....4..5.........67.....2....819...........9.4....81.....3......5.
.......12..2..3....4..5.........67.....2....819...........9.4....81.....6......5.
.......12..3..1....4..5.........53.....6....785...........3.4....72.....2......5.
.......12..3..1....4..5.........56.....3....478...........8.4....24.....1......5.
.......12..3..2....4..5.........53.....6....715...........8.4....97.....2......5.
.......12..3..4....4..5.........62.....7....815...........1.5....82.....7......4.
.......12..3..4....4..5.........67.....1....318...........8.5....62.....9......8.
.......12..3..4....5..1.........63.....7....819...........9.4....72.....2......6.
.......12..3..4....5..1.........63.....7....819...........9.4....72.....2......8.
.......12..3..4....5..1.........65.....7....819...........9.3....72.....2......4.
.......12..3..4....5..1.........65.....7....819...........9.4....72.....2......8.
.......12..3..4....5..1.........67.....8....519...........9.4....82.....2......3.
.......12..3..4....5..3.........16.....2....784...........5.4....68.....1......5.
.......12..2..3....4..5.........46.....2....371..........1...5...3...4..8...7....
.......12..2..3....4..5.........63.....2....671..........1...5...3...8..6...7....
.......12..2..3....4..5.........64.....2....371..........1...5...3...6..8...7....
.......12..2..3....4..5.........64.....2....781..........1...5...7...3..3...8....
.......12..2..3....4..5.........65.....2....471..........1...8...4...3..9...7....
.......12..2..3....4..5.........67.....2....318..........1...5...3...6..4...8....
.......12..3..2....4..3.........52.....1....667..........8...4...5...9..2...6....
.......12..3..2....4..3.........52.....1....667..........8...9...5...4..2...6....
.......12..3..2....4..5.........62.....1....778..........9...3...6...4..2...7....
.......12..3..4....4..5.........67.....8....325..........2...5...8...6..3...1....
.......12..3..4....5..3.........36.....2....781..........8...6...4...5..2...1....
.......12..3..4....5..3.........67.....2....381..........8...9...4...6..2...1....
.......12..3..4....5..3.........67.....2....418..........8...5...4...6..2...1....
.......12..3..4....5..3.........67.....2....481..........8...5...4...6..2...1....
.......12..3..4....5..6.........56.....2....718..........8...5...7...4..2...1....
.......12..3..4....5..6.........56.....2....781..........8...5...7...4..2...1....
.......12..3..4....5..6.........57.....3....816..........1...6...4...5..8...2....
.......12..3..4....5..6.........57.....8....326..........2...6...8...5..3...1....
.......12..3..4....5..6.........73.....8....921..........2...5...7...4..4...1....
.......12..3..4....5..6.........75.....2....318..........8...6...4...7..2...1....
.......12..3..4....5..6.........75.....2....381..........8...6...4...7..2...1....
.......12..3..4....5..6.........75.....2....819..........9...6...4...7..2...1....
.......12..3..4....5..6.........75.....2....891..........9...5...4...6..2...1....
.......12..1..3....4..5.........26.....1....471..........87......3...5..6......7.
.......12..1..3....4..5.........26.....1....471..........87......3...5..8......7.
.......12..3..2....4..5.........56...7..4....1.......7...4...3...6...8..2..7.....
.......12..3..4....2..5.........63...5..7....8.......4...5...9...6...4..3..2.....
.......12..3..4....4..5.........36...2..7....1.......8...8...3...9...7..8..2.....
.......12..3..4....4..5.........63...2..7....1.......8...8...3...5...7..8..2.....
.......12..3..4....5..2.........35...6..5....1.......7...7...6...8...3..2..1.....
.......12..3..4....5..3.........56...2..7....8.......1...8...6...7...5..2..1.....
.......12..3..4....5..6.........32...7..5....1.......8...7...5...4...3..2..1.....
.......12..3..4....5..6.........52...4..3....1.......7...1...4...2...3..8..7.....
.......12..3..4....5..6.........52...7..3....1.......8...7...4...4...5..2..1.....
.......12..3..4....5..6.........53...2..7....8.......6...2...3...5...4..7..8.....
.......12..3..4....5..6.........56...7..3....1.......7...2...8...8...3..2..7.....
.......12..3..4....5..6.........56...7..8....1.......7...2...3...9...8..2..7.....
.......12..1..2....3..4.........45...4.1.....6.......7....8.3....97.....2......4.
.......12..1..3....4..5.........65...7.1.....5.......8....9.4....82.....1......6.
.......12..1..3....4..5.........65...7.1.....2.......3...7...4...6...8..3...2....
.......12..1..3....4..5.........67...2.1.....8.......3...8...4...7...5..3...2....
.......12..3..4....1..3.........56...2.1.....7.......3...2...5...6...8..9...7....
.......12..3..4....1..5.........35...2.6.....7.......8...8...3...5...4..6...2....
.......12..3..4....1..5.........35...2.6.....7.......8...9...3...5...4..6...2....
.......12..3..4....1..5.........63...2.1.....4.......7...2...3...6...4..8...7....
.......12..3..4....1..5.........63...7.1.....2.......6...2...7...6...4..5...8....
.......12..3..4....1..5.........63...7.2.....5.......4...1...3...4...6..2...8....
.......12..3..4....1..5.........64...2.1.....7.......3...2...6...8...7..3...7....
.......12..3..4....1..5.........64...2.1.....7.......8...2...6...5...9..8...4....
.......12..3..4....1..5.........64...2.1.....7.......8...2...6...7...9..8...4....
.......12..3..4....1..5.........67...2.1.....4.......3...2...6...7...8..9...3....
.......12..3..4....1..5.........67...2.1.....8.......3...2...6...7...9..4...3....
.......12..3..4....1..5.........67...2.1.....8.......4...2...6...5...4..7...8....
.......12..3..4....1..5.........67...2.1.....8.......4...2...6...9...4..7...8....
.......12..3..4....1..5.........67...2.1.....8.......4...2...6...9...4..7...9....
.......12..3..4....1..5.........67...2.3.....5.......4...1...3...4...8..7...2....
.......12..3..4....2..5.........53...6.1.....1.......7...2...6...5...4..3...8....
.......12..3..4....2..5.........63...5.7.....8.......4...5...9...6...4..3...2....
.......12..3..4....2..5.........64...7.1.....6.......8...2...7...4...9..8...7....
.......12..3..4....2..5.........67...1.3.....5.......4...2...3...4...8..7...1....
.......12..3..4....4..5.........65...7.3.....1.......8...1...7...8...3..2...8....
.......12..3..4....5..6.........13...2.3.....6.......7...5...8...1...4..7...2....
.......12..3..4....5..6.........13...2.3.....7.......8...9...5...1...4..8...2....
.......12..3..4....5..6.........13...2.7.....6.......4...5...7...4...6..8...2....
.......12..3..4....5..6.........17...2.3.....6.......4...5...3...4...8..7...2....
.......12..3..4....5..6.........32...7.1.....6.......7...5...3...8...4..2...7....
.......12..3..4....5..6.........35...2.1.....6.......7...5...3...8...4..7...2....
.......12..3..4....5..6.........35...2.7.....6.......4...8...3...9...7..4...2....
.......12..3..4....5..6.........35...2.7.....6.......8...5...3...9...4..7...2....
.......12..3..4....5..6.........35...7.8.....1.......6...2...3...5...7..6...1....
.......12..3..4....5..6.........36...7.5.....1.......8...1...7...8...4..2...8....
.......12..3..4....5..6.........36...7.8.....1.......9...1...7...9...8..2...9....
.......12..3..4....5..6.........37...1.8.....6.......4...5...3...7...8..4...1....
.......12..3..4....5..6.........37...2.8.....6.......1...5...3...8...4..1...2....
.......12..3..4....5..6.........37...2.8.....6.......4...5...3...9...8..4...2....
.......12..3..4....5..6.........37...4.1.....2.......6...2...3...7...4..8...9....
.......12..3..4....5..6.........37...8.1.....2.......5...2...3...6...4..7...5....
.......12..3..4....5..6.........37...8.1.....6.......8...2...3...6...4..2...8....
.......12..3..4....5..6.........52...7.3.....1.......8...1...7...6...5..2...8....
.......12..3..4....5..6.........53...1.2.....4.......6...7...3...5...8..6...1....
.......12..3..4....5..6.........53...1.7.....6.......4...8...6...5...9..4...1....
.......12..3..4....5..6.........53...2.1.....6.......7...3...5...8...4..9...2....
.......12..3..4....5..6.........53...2.1.....6.......7...8...3...5...4..7...2....
.......12..3..4....5..6.........53...2.7.....6.......4...1...3...5...7..8...2....
.......12..3..4....5..6.........53...4.7.....1.......6...1...4...5...8..2...3....
.......12..3..4....5..6.........53...4.7.....2.......6...2...4...5...8..1...3....
.......12..3..4....5..6.........53...7.4.....6.......8...1...3...5...4..1...7....
.......12..3..4....5..6.........56...4.3.....2.......7...2...4...5...8..1...7....
.......12..3..4....5..6.........56...4.7.....1.......8...1...4...8...7..2...8....
.......12..3..4....5..6.........56...7.3.....1.......8...1...7...8...3..2...8....
.......12..3..4....5..6.........56...7.3.....2.......8...2...7...5...4..1...8....
.......12..3..4....5..6.........56...7.8.....1.......9...1...7...9...8..2...9....
.......12..3..4....5..6.........57...6.1.....8.......4...8...5...5...4..2...1....
.......12..3..4....5..6.........73...1.2.....2.......4...1...5...7...4..3...8....
.......12..3..4....5..6.........73...1.8.....9.......4...5...7...7...4..2...1....
.......12..3..4....5..6.........73...2.1.....6.......4...8...5...7...6..4...2....
.......12..3..4....5..6.........73...2.6.....1.......4...2...5...7...4..3...8....
.......12..3..4....5..6.........73...8.3.....1.......6...2...8...7...5..2...1....
.......12..3..4....5..6.........74...7.1.....2.......8...2...7...9...5..4...8....
Afmob
 
Posts: 132
Joined: 28 June 2011

Postby Afmob » Wed May 07, 2014 7:09 am

The computation is over and it yielded a lot of valid puzzles. Using gsf's handy software I did a {-2+1} on the valid puzzles and got 5 valid puzzles with 17 clues which are already known.

On another note, I wondered whether we've already checked all known grids which contain a 17 clue valid puzzle, maybe we can find new puzzles this way and it shouldn't take too long (rough estimate: 2-3 days on the cluster I use). Another idea would be to check all known patterns (~34,000 patterns). Do you know if this has already been done?
Afmob
 
Posts: 132
Joined: 28 June 2011

Re: No new 17s within {-2+2}

Postby coloin » Fri May 09, 2014 5:11 pm

Ver well done ....
As far as i recollect - only the grids with 29,20, ... etc puzzles were completly searched
I am sure no one has searched the patterns [ more than {-2+2} ] ?
I could easily run a +3 on the patterns using gridchecker - if it hasnt been done already .....

It seems that 2 of your 18-puzzles are non-minimal - unfortunatly there are patterns which we havent listed [see last post] which have yet to be searched. There are a total of 8 known 17-puzzzles which have box/row/col of 222222221.

i am still exploring how far we can take this .....
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Re: No new 17s within {-2+2}

Postby blue » Fri May 09, 2014 5:16 pm

There's this, in the McGuire group's paper:

8.3 Ensuring the correctness of our programme checker

Certainly the most important aspect of this project is correctness. At first glance, it may appear difficult to verify the correctness of our programme checker on the grounds of the lack of available test cases (no sudoku grids containing any 16-clue puzzles). To be able to do some testing anyway, we produced a version of checker that searches for 17-clue puzzles. This version had minimal changes over the version that searches for 16-clue puzzles—we made only those changes that were absolutely necessary. We ran this checker on all known grids having at least one 17-clue puzzle, and with every such grid, all the 17-clue puzzles that grid was known to contain were found by checker.

(...)

Unfortunately it doesn't make an explicit statement about nothing new being found.

In another spot in the paper, there's a mention of there being 49151 known 17's with 46294 ED solution grids.
I know I checked the grids for #'s 49153-7, but I don't remember about #49152.
blue
 
Posts: 975
Joined: 11 March 2013

Re: No new 17s within {-2+2}

Postby Serg » Sun May 11, 2014 9:30 am

Hi, blue!
blue wrote:In another spot in the paper, there's a mention of there being 49151 known 17's with 46294 ED solution grids.
I know I checked the grids for #'s 49153-7, but I don't remember about #49152.

Maybe I misunderstood you ...
If you asked about 17-clue puzzle #49152, see starting page of this thread (Page 1).

Serg
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: No new 17s within {-2+2}

Postby blue » Sun May 11, 2014 2:24 pm

Hi Serg,

Serg wrote:Maybe I misunderstood you ...
If you asked about 17-clue puzzle #49152, see starting page of this thread (Page 1).

I was trying to say that the solution grid for #49252, might be the only one that hasn't been checked for other 17s.
I've checked it too, now. Nothing new.

Blue.
blue
 
Posts: 975
Joined: 11 March 2013

Re: No new 17s within {-2+2}

Postby champagne » Tue May 13, 2014 7:28 am

I had a look to patterns starting in max lexical form by 1.. 1.. 1..

We have to many patterns for a full scan.

I tried a vicinity search out of the 18's clues puzzles found with the start 1.. 1.. ... but no new 17 clues appeared.
champagne
2017 Supporter
 
Posts: 7336
Joined: 02 August 2007
Location: France Brittany

Re: No new 17s within {-2+2}

Postby dobrichev » Wed May 14, 2014 3:29 am

champagne wrote:I tried a vicinity search out of the 18's clues puzzles found with the start 1.. 1.. ... but no new 17 clues appeared.

A journey of a thousand miles begins with a single step.
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

Re: No new 17s within {-2+2}

Postby coloin » Wed May 14, 2014 4:21 pm

Well ...... it certainly would be a long journey.

I have been looking into how feasable it is to extend a search

specifically i have been looking at 18 clue puzzles. [minimal and non-minimal]
18 clue can have max clues in a box or row of 2,3,4,5 or 6.
In the unlikely event of ever generating all of these - we would by nature of it have all the 17clue puzzles ..... [max 2,3,4,5 clues]

However - unless its a complete search - we can bever be sure that we have found them all .... and because the 18 clue puzzles arn't closed to a {-1+1} it would mean that a {-2+2} would probably suffice - exxcept that would be too much to do.

Breaking the search down doesnt help much
6plus12s - 400 found
5plus13s - ? 2 000 000
4plus14s - ? 300 000 000

Filling the box [or row] [temporarily] to 9 clues helps in some ways in reducing the total puzzles from the same solution grids, although there may be more 9plus-x puzzles which cant be reduced to 18 clues. "Symmetry" will tend to put more puzzles near each other - although i had hoped the 9plus14s would be closed with a {-1+1} [ignore the 9 from the {-1}] this is also not the case.

Combining the results of 4plus14s generated from all found 9plus14s [box9plus14s and row9plus14s] might give addditional puzzles

At present I am doing this with the more manageable 9plus13s/5plus13s ...... unfortunatly sheer numbers of 4plus14s prevents me even thinking about it.

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby Afmob » Fri Sep 26, 2014 7:35 am

I've checked all known patterns having a 17-clue puzzle and it yielded no new 17-cue Sudokus. Therefore, if we haven't found all 17-clue puzzles new ones must have different patterns.
Afmob
 
Posts: 132
Joined: 28 June 2011

Re: No new 17s within {-2+2}

Postby eleven » Fri Sep 26, 2014 1:55 pm

Impressive result. Would you please post some details about the number of patterns and the computing times ?

I have not really followed the discussion about excluding/finding 17's by means of patterns (different to going through the solution grids, as it was done for the 16 clue proof).
But i have the feeling, that still there can be nothing said about the big majority of possible 17 clue patterns, though many could be excluded (by proving impossible subpatterns and now Afmob's result).
Is that right ?
eleven
 
Posts: 3082
Joined: 10 February 2008

Re: No new 17s within {-2+2}

Postby Afmob » Sat Sep 27, 2014 8:36 am

The 49157 puzzles have 33883 different patterns. The number of essentially different puzzles per patterns varies between just 100 million and up to 3 billion. As a solver I use Jason's adaption of ZhouSolver which solves about 400-600 million of puzzles per hour. The computation took about 3-4 month on 32 cores where 31 cores where used for solving which was definitely longer than I expected.
Afmob
 
Posts: 132
Joined: 28 June 2011

Re: No new 17s within {-2+2}

Postby dobrichev » Sun Sep 28, 2014 1:28 pm

Congratulations to Afmob for this impressive work! Well done!

Examining the patterns at {-1,+1} could give some new 17s but is very costly.
Exhaustive search grid by grid is still not achievable too.
Most productive should be collecting huge number of 19s and looking around them.

Some calculations on eventual {-3,+3} search, which I don't believe is very productive, but just for the record.
The 49157 17s consist of 30 302 691 essentially different 14s.
Each 14 should be tried by
- adding first additional clue at one of the 67 possible positions with 9 possible values, factor = 67 * 9 = 603
- same for the secondary clue, factor = 66 * 9 = 594, accumulated factor = 603 * 594 = 358182
- same for the last third clue, factor = 65 * 9 = 585, accumulated factor = 358182 * 585 = 209,536,470

Assuming some of the 9 possible values are invalid and are checked earlier at least at direct eliminations level, I am expecting the factor to be reduced to < 100 000 000.

A single core solves at least 500 000 000 puzzles per hour, so that about 5 14s per hour per core could be checked.
If 64 cores are used, 320 14s per hour can be checked.
For 30 000 000 14s this is about 10 000 hours = 417 days.

If the average possible values per position is 5, then instead of 9 * 9 * 9 / 2 = 364 factor, a 5 * 5 * 5 = 125 factor reduces the time by 3 to about 140 days calculations on a 64-core machine.

Consolidation of the intermediate 15s and 16s would also reduce the number of essentially different puzzles for processing at the latest stage, maybe by 20%.

My solver rate when solving up to the second solution is 960 millions puzzles per hour for the valid 17s, but it degrades to 488 millions/hour for the derivative multiple-solution 15s. From other side, the rate is drastically higher for the invalid puzzles, 9 000 millions/hour for the Jason's gen_puzzles, but it isn't clear if this estimation is applicable to the expected majority of invalid and multiple-solution 17s that should be checked.

An optimistical view over the above estimations gives hope that {-3,+3} could be performed with about twice more calculations than these done by Afmob for his pattern checking exercise - 3-4 months but on a 64-core machine.
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

PreviousNext

Return to General