SudokuFP

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: SudokuFP

Postby Mathimagics » Sat Jan 12, 2019 1:09 pm

.
Things go such better when you have a working fast solver!

Found a 3-clue NC+:
Code: Select all
 +-------+-------+-------+
 | . 1 . | . . . | . . . |
 | . . 4 | . . . | . . . |
 | . . . | . . . | . . . |
 +-------+-------+-------+
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | 5 . . | . . . | . . . |
 +-------+-------+-------+
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 +-------+-------+-------+
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby tarek » Sat Jan 12, 2019 2:50 pm

Mathimagics wrote:.
Found a 3-clue NC+:
Code: Select all
 +-------+-------+-------+
 | . 1 . | . . . | . . . |
 | . . 4 | . . . | . . . |
 | . . . | . . . | . . . |
 +-------+-------+-------+
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | 5 . . | . . . | . . . |
 +-------+-------+-------+
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 +-------+-------+-------+

Confirmed & congratulations. Solution:
Code: Select all
+-------+-------+-------+
| 6 1 8 | 4 2 9 | 5 7 3 |
| 3 7 4 | 1 8 5 | 9 2 6 |
| 9 5 2 | 6 3 7 | 4 8 1 |
+-------+-------+-------+
| 2 8 6 | 9 7 4 | 1 3 5 |
| 7 4 1 | 3 5 2 | 8 6 9 |
| 5 9 3 | 8 1 6 | 2 4 7 |
+-------+-------+-------+
| 8 3 5 | 2 6 1 | 7 9 4 |
| 1 6 9 | 7 4 8 | 3 5 2 |
| 4 2 7 | 5 9 3 | 6 1 8 |
+-------+-------+-------+
User avatar
tarek
 
Posts: 3097
Joined: 05 January 2006

Re: SudokuFP

Postby tarek » Sat Jan 12, 2019 3:02 pm

So I'm guessing that you would have had to go through (18,569 x 81 x 80 x 79 / 6 ) 3 clue puzzles !!

It means that you have already done the same process for 2 clue cases & the 1 clue cases as well


tarek
User avatar
tarek
 
Posts: 3097
Joined: 05 January 2006

Re: SudokuFP

Postby coloin » Sat Jan 12, 2019 5:25 pm

Well ... i couldnt solve the 5 clue puzzle by hand ...... didnt want to guess.
Suppose it really was an ER=12.0 :roll:
coloin
 
Posts: 1813
Joined: 05 May 2005

Re: SudokuFP

Postby Mathimagics » Sat Jan 12, 2019 7:01 pm

tarek wrote:So I'm guessing that you would have had to go through (18,569 x 81 x 80 x 79 / 6 ) 3 clue puzzles !!

More or less. Well, less, I think. I am not sure where that 18,569 figure comes from. 3-cell selections is done 81*80*79/6 ways, yes, but surely 3 clues can only have 729 = 9^3 different value settings?

Anyhow, there are definitely no 2-clue NC+ puzzles, so 3 is definitely the minimum.

And if 2-clue puzzles don't exist for NC+ then they certainly won't be found for NC.

I tried adding a dimension (eg SudokuP), even 1.2 dimensions (SudokuPX), but no cigar! We just get increasing numbers of 3-clue puzzles.


PS: nobody needs to tell me that the cell-selection and value-selections are mostly invalid, and that there are clever ways to reduce the number of puzzles that are actually tested. I prefer to let the solver deal with that nonsense, it's a lot smarter than me. This, ladies and gentlemen, is brute force in its most primitive form, and it ain't pretty! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby tarek » Sat Jan 12, 2019 7:40 pm

Mathimagics wrote:
tarek wrote:So I'm guessing that you would have had to go through (18,569 x 81 x 80 x 79 / 6 ) 3 clue puzzles !!

More or less. Well, less, I think. I am not sure where that 18,569 figure comes from. 3-cell selections is done 81*80*79/6 ways, yes, but surely 3 clues can only have 729 = 9^3 different value settings?
That is True. 18,569 was the the number of ED grids you provided but 729 looks much better :D it just tells how well placed these clues need to be!

coloin wrote:Well ... i couldnt solve the 5 clue puzzle by hand ...... didnt want to guess.
Suppose it really was an ER=12.0 :roll:


There was a disclaimer about approaching with caution!!! I did post later down that page some Easy ones.

Mathimagics wrote:PS: nobody needs to tell me that the cell-selection and value-selections are mostly invalid, and that there are clever ways to reduce the number of puzzles that are actually tested. I prefer to let the solver deal with that nonsense, it's a lot smarter than me. This, ladies and gentlemen, is brute force in its most primitive form, and it ain't pretty! 8-)

Because of the 8 way symmetries amongst others ;)


Tarek
User avatar
tarek
 
Posts: 3097
Joined: 05 January 2006

Re: SudokuFP

Postby Mathimagics » Sat Jan 12, 2019 8:26 pm

You just couldn't help yourself, tarek, could you!!!

You just earned a Sybil Fawlty Award nomination 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby Mathimagics » Sat Jan 12, 2019 10:52 pm

.
Ok, I made one final attempt to find a 2-givens NC+ puzzle.

This is one of just 29 14 grids in the NC+ ED catalog (18,569 grids 12,263) that is both SudokuPX and has toroidal adjacency property. Toroidal simply means (R1, R9) are adjacent, as are (C1, C9). Thus every cell has 4 adjacent cells. Note that this extended adjacency is generic, ie can be applied to any FP case.
Code: Select all
 +-------+-------+-------+
 | 1 3 6 | 2 8 5 | 7 9 4 |
 | 8 5 2 | 9 4 7 | 3 6 1 |
 | 4 7 9 | 6 1 3 | 5 2 8 |
 +-------+-------+-------+
 | 9 4 7 | 3 6 1 | 8 5 2 |
 | 6 1 3 | 5 2 8 | 4 7 9 |
 | 2 8 5 | 7 9 4 | 1 3 6 |
 +-------+-------+-------+
 | 5 2 8 | 4 7 9 | 6 1 3 |
 | 7 9 4 | 1 3 6 | 2 8 5 |
 | 3 6 1 | 8 5 2 | 9 4 7 |
 +-------+-------+-------+


Here is a 3-given puzzle, but not for the same grid. tarek clearly has nothing better to do, so he can P&P it and post the solution. No assistance please! :lol:
Code: Select all
 +-------+-------+-------+
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | 8 . . | . . . |
 +-------+-------+-------+
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 +-------+-------+-------+
 | . . . | . . . | . . . |
 | . . . | . 3 . | . . 5 |
 | . . . | . . . | . . . |
 +-------+-------+-------+


Now we have fewer ED grids in this set, only 29, but every one of them has 3-clue puzzles galore.

And still there are no 2-clue puzzles! :cry:

That's it for NC, I think.

Now we just want a truth-table. But can we handle the truth-table? (settle down, Jack) 8-)
Last edited by Mathimagics on Thu Jan 31, 2019 6:01 pm, edited 2 times in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby tarek » Sun Jan 13, 2019 2:27 am

Mathimagics wrote: tarek clearly has nothing better to do, so he can P&P it and post the solution. No assistance please! :lol:

Maybe if you made it symmetrical 8-)

Code: Select all
cNC PX Toroid
 +-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . 1 |
+-------+-------+-------+
| . . . | . . . | . . . |
| 2 . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . 7 |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+

+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . 1 . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . 4 . | . . . | . 6 . |
| . . . | . . . | . . . |
+-------+-------+-------+

+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . 1 |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . 3 . |
| . . . | . 7 . | . . . |
+-------+-------+-------+


tarek
User avatar
tarek
 
Posts: 3097
Joined: 05 January 2006

Re: SudokuFP

Postby Mathimagics » Sun Jan 13, 2019 6:14 am

Symmetry is SO last year … :?
=======================

Ok, you want the truth about tables?

Some basic facts …

No row can have more than 5 x 1's in it (4 FPs + the diagonal entry). Here's a TT that restricts the value 1 to neighbours {7,8,9}, so there are 6 FPs, ie 6 x 1's in row 1 and col 1. Now you can make a Latin Square that conforms to these restrictions, as shown in the 2nd grid, but you can`t make a Sudoku!

In fact you can add one more FP in row 1 and still make a LS, in which 1 is only adjacent to two pairs of values (7 x 1's in row 1 if the TT), as shown in the 3rd grid. The added FP is (1,8).

Code: Select all
 1 1 1 1 1 1 0 0 0   |   1 7 2 3 4 5 6 8 9   |   1 7 2 3 4 5 6 8 9
 1 1 0 0 0 0 0 0 0   |   7 1 9 2 3 4 5 6 8   |   7 8 6 2 3 4 5 9 1
 1 0 1 0 0 0 0 0 0   |   5 8 6 9 2 3 4 7 1   |   6 4 5 8 2 3 9 1 7
 1 0 0 1 0 0 0 0 0   |   4 6 3 5 9 2 8 1 7   |   4 2 3 5 6 9 1 7 8
 1 0 0 0 1 0 0 0 0   |   2 3 8 4 6 7 1 9 5   |   8 3 4 6 9 1 7 2 5
 1 0 0 0 0 1 0 0 0   |   3 9 1 8 5 6 7 2 4   |   2 5 8 9 1 7 3 4 6
 0 0 0 0 0 0 1 0 0   |   6 5 7 1 8 9 2 4 3   |   5 6 9 1 7 2 8 3 4
 0 0 0 0 0 0 0 1 0   |   9 2 4 7 1 8 3 5 6   |   3 9 1 7 5 8 4 6 2
 0 0 0 0 0 0 0 0 1   |   8 4 5 6 7 1 9 3 2   |   9 1 7 4 8 6 2 5 3


Since the table is symmetric about the diagonal, that means we can have at most 18 FP`s all up.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby Mathimagics » Sun Jan 13, 2019 9:04 am

Note that the # of ED NC+ grids reported previously was incorrect. The true figure is 12,263. This was spotted by blue (thanks!). It seems that I had omitted one of the relabelling symmetries in the CF function. :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby tarek » Mon Jan 14, 2019 12:20 am

Mathimagics wrote:.
This is one of just 29 grids in the NC+ ED catalog (18,569 grids) that is both SudokuPX and has toroidal adjacency property.

As your cNC ED grid number were revised, I think I've got the cNC PX Toroid ED grids revised to 14
User avatar
tarek
 
Posts: 3097
Joined: 05 January 2006

FP Truth-Tables

Postby Mathimagics » Mon Jan 14, 2019 12:31 am

I have found a 2-clue FP puzzle for a SudokuX.

2-clue SudokuX-FP: Show
Code: Select all
 +-------+-------+-------+
 | . . . | . . 9 | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 +-------+-------+-------+
 | . . . | . . . | . . . |
 | . . . | . . . | 6 . . |
 | . . . | . . . | . . . |
 +-------+-------+-------+
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 +-------+-------+-------+

Solution: Show
Code: Select all
 +-------+-------+-------+
 | 3 2 1 | 4 6 9 | 8 7 5 |
 | 8 7 5 | 1 2 3 | 9 6 4 |
 | 9 6 4 | 5 7 8 | 3 2 1 |
 +-------+-------+-------+
 | 6 4 8 | 9 5 7 | 2 1 3 |
 | 7 5 9 | 3 1 2 | 6 4 8 |
 | 2 1 3 | 8 4 6 | 7 5 9 |
 +-------+-------+-------+
 | 1 3 2 | 7 8 4 | 5 9 6 |
 | 5 9 6 | 2 3 1 | 4 8 7 |
 | 4 8 7 | 6 9 5 | 1 3 2 |
 +-------+-------+-------+


It is perhaps of interest to describe the search process, as it involves a little Graph Theory, and I happen to like that very much! 8-)

As I mentioned above, the 18-FP truth-table seemed the obvious place to start looking. This is the maximum number of FP's that can be used, and so gives the maximum potential for restricting the applicable grid solution space.

The first question to answer was, how many TT18's are there, or more importantly, how many ED flavours are there? Consider this example:
Code: Select all
   . . . . . 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 X X . . . . .


Now if we invert the dots and the X's (excluding the main diagonal), then this becomes an adjacency table (as against a forbidden pair table), and one that has the same properties. There are still 4 X's in each row and column. Adjacency tables are just graphs in another form. And since each vertex has 4 edges joining it to other vertices, our TT is a 9V 4-regular graph, and we know quite a bit about these guys.

There are only 16 ED graphs in this category, and so there are just 16 flavours of TT18's. In my list the TT above is #5.
AG5 graph: Show
09_4_3-5.gif
Adjacency Graph AG5
09_4_3-5.gif (2.68 KiB) Viewed 146 times


Now, it turns out that only 3 of these 16 adjacency graphs can be used, since the rest do not correspond to any Sudoku grids. 9 of them do not allow the completion of a 3x3 box, and 4 more are found to be incompletable, that is, there are boxes but they can't be assembled to form a valid grid. The only valid ones are the final 3 in my list, ie AG14, AG15, and AG16. (Note: validity here refers to satisfying the TT, not just getting a valid Sudoku grid).

The valid AGs: Show
AG14-15-16.png
Valid AG's
AG14-15-16.png (18.69 KiB) Viewed 146 times


It is interesting to note how "regular" these are compared to AG5, and there is probably something more to be learned there. But now we have just 3 TT18's as candidates, and so can use the brute-force clue-pattern method to search for low-clue puzzles for each case.

AG14 disappoints, it produces no 3-clue puzzles, but both AG15 and AG16 produce 3-clue puzzles in standard Sudoku form. Since we already know that the NC case has no 3-clue puzzles, this is progress! We find millions of 3-clue puzzles for AG15 and AG16, but alas, no 2-clue puzzles. So we look to add constraints, and by starting with SudokuX, are rewarded with an abundance of 2-clue puzzles (53,088).

None for AG16 though. AG15 is the only TT18 which yields 2-clue puzzles.

The next step is to consider other TT's with less than 18 FP's. Can they produce 2-clue puzzles?

And does the 1-clue puzzle exist in this FP form?

Watch this space 8-)
Last edited by Mathimagics on Tue Jan 15, 2019 10:34 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby Mathimagics » Mon Jan 14, 2019 3:53 pm

tarek wrote:As your cNC ED grid number were revised, I think I've got the cNC PX Toroid ED grids revised to 14


Thank you, tarek. The bug in my CF function means that any figure I had previously involving NC+ was wrong. I have corrected the figures above.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby Mathimagics » Tue Jan 15, 2019 8:53 am

.
A little diversion, a puzzle if you like. Consider this run log:
Code: Select all
D:\SudokuFP\FindMCX 2

01:14:15:  <start>
01:14:25:  2C combns =  3240
01:14:25:  <done> np = 53088

D:\SudokuNC>FindMCX 2

00:15:32:  <start>
13:19:51:  2C combns =  3240
13:19:53:  <done> np =  1056


FindMC is my little brute-force clue pattern tester. FindMCX is simply the version that uses SudokuX mode. We are testing here just for 2-clue puzzles, so exactly 3240 x 9^2 solver invocations are involved.

Now, why do you think the first job takes only 10 seconds, but the second one takes 13 excruciating hours (nearly 5000 times longer)?

A virtual cigar for the first correct answer (NB: blue is excluded 8-) )
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

PreviousNext

Return to Sudoku variants