SudokuFP

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: SudokuFP

Postby Mathimagics » Tue Jan 15, 2019 10:55 am

We now know more about those 3 TT18 types.

Firstly, all solutions to each TT are of a type - they have the same automorphism count:

  • AG14 solutions are all MC (648)
  • AG15 solutions all have 12 automorphisms
  • AG16 solutions all have 54 automorphisms


ED grid counts for various puzzle types. For this exercise we DO normalise the grid, since each TT18 can be permuted to correspond to any labelling. Counts are given for both normal adjacency rules and the Toroidal case:
Code: Select all
-----------------------------------
AG:    14   15   16 | 14T  15T  16T
--------------------+--------------
SS     13   14   26 |  2    -    7
SX      2    1    - |  1    -    -
SP      1    2    6 |  1    -    2
PX      1    1    - |  1    -    -
User avatar
Mathimagics
2017 Supporter
 
Posts: 1262
Joined: 27 May 2015
Location: Canberra

Re: Truth tables

Postby tarek » Tue Jan 15, 2019 1:56 pm

1st of all what great work and nice displays over the past few threads. Well done.

All varieties of NC and anti-chess are now subsets of the FP and can be handled with the truth table.

I’m going -when I have time- to add an option to my solver to use these tables most likely in this way:

Code: Select all
for (r = 0; r < N; r++)
 for (c = r; c < N; c++)
  If ( i[ r * N + c]) ....


I will most likely use the pre-compiler to use my current code while developing the Truth tables as a replacement code when I feel it is a better option

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

Re: SudokuFP

Postby Mathimagics » Tue Jan 15, 2019 11:36 pm

Ok, let's consider the puzzle creation process. How do we create a "nice" FP puzzle from scratch?

By "nice" I would imagine that we want something like an NC puzzle, only with additional FP's that we can exploit to reduce the givens.

For this example I will work with minimal-singles puzzles. These are minimal puzzles wrt the "solvable by singles only" property. Removal of any clue might still leave a valid puzzle, but not one that is singles-only.

An excellent place to start is with a known NC grid. I scanned the NC catalog and counted how many FP's could be applied to each, and reported the first instance of any grid with NFP = 9 … 18. The results were:
NC grid scan: Show
Code: Select all
 9: 615384729847926153392571486974253861538617294261849537483162975726495318159738642
10: 538162497261794835947538261794253618352816974186479352813947526479625183625381749
11: 583792461927164835641538297168253974794816352352479618835927146279641583416385729
12: 175394826628571394394826157849263571263715948517948263751482639936157482482639715
13: 927385146583641729146927385794253861352816497618479253461792538835164972279538614
14: 715386924962741358384925716847253169629417583153869247538692471296174835471538692
15: 571482936936157284284639751849263517362715849715948362157394628493826175628571493
16: 526947183749381526183625749618253974974816352352479618835792461297164835461538297
18: 526947183749381526183625749618253974974816352352479618835794261497162835261538497

Total grids by NFP:
nfp =  9, ng =  63714
nfp = 10, ng =   2544
nfp = 11, ng =   2602
nfp = 12, ng =  19786
nfp = 13, ng =    733
nfp = 14, ng =    648
nfp = 15, ng =   2999
nfp = 16, ng =   5528
nfp = 18, ng =  15352

As you can see there is an ample supply. I think the Goldilocks zone is NFP = 11 to 14. Too high and the solutions get too close to looking like the MC grid, too low and we don't have enough "spare" FP's to play with.

I chose the first reported NFP = 14 case.
Selected grid: Show
Code: Select all
 +-------+-------+-------+
 | 7 1 5 | 3 8 6 | 9 2 4 |
 | 9 6 2 | 7 4 1 | 3 5 8 |
 | 3 8 4 | 9 2 5 | 7 1 6 |
 +-------+-------+-------+
 | 8 4 7 | 2 5 3 | 1 6 9 |
 | 6 2 9 | 4 1 7 | 5 8 3 |
 | 1 5 3 | 8 6 9 | 2 4 7 |
 +-------+-------+-------+
 | 5 3 8 | 6 9 2 | 4 7 1 |
 | 2 9 6 | 1 7 4 | 8 3 5 |
 | 4 7 1 | 5 3 8 | 6 9 2 |
 +-------+-------+-------+

Its FP list as a TT: Show
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 .

The FP's additional to the standard NC set are: {1,8}, {1,9}*, {2,8}, {3,6}, {4,6}, {5,9} (* so it's really an NC+ with 5 extra FP's).

Then I did a random reduction to a minimal-singles NC puzzle. This one has 13 givens:
Reduction NC: Show
Code: Select all
d:\SudokuFP\Solver>GenMinimalS
715386924962741358384925716847253169629417583153869247538692471296174835471538692
NC mode
Singles mode
Clues = 16
13: ...3..9..962...........5.1........................924.....9...1.9................

Then I used the full FP set, and from the 13-given puzzle obtained a list of 8 minimal-singles puzzles with 6/7 givens:
Reduction FP: Show
Code: Select all
d:\SudokuFP\Solver>GenMinimalS x
715386924962741358384925716847253169629417583153869247538692471296174835471538692
FP mode, NFP = 14
Singles mode
07: ..........62...........5.1................................9...1.9................
06: ..........62...........5.1.........................2............9................
06: .........9.2...........5.1.........................2..........1..................
06: .........9.2...........5.1........................9.4............................
06: .........9.2...........5.1........................92.............................
06: .........962...........5.1.........................2.............................
06: ......9..96............5.1.........................2.............................
06: ...3.....9.2...........5.1.........................2.............................

I could have skipped the first reduction altogether and simply reduced in FP mode directly, but I wanted to demonstrate that a minimal NC puzzle would have further redundancies when the grid had additional FP's.

If for some reason we wanted to obscure this grid's NC origins, we can simply rearrange the TT so it matches any chosen relabelling of the original grid. To do this is simple, if we want to swap values 3 and 7, we just swap rows 3,7 and cols 3,7 in the TT.

Next to consider is the direct construction method. Can we simply generate a random TT with, say, 11 or 12 entries and expect to get an equally good result? Or do we actually need those long NC chains …
User avatar
Mathimagics
2017 Supporter
 
Posts: 1262
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby Mathimagics » Wed Jan 16, 2019 5:31 am

.
A printer-ready sample of the above process (without all the boring details). Different grid of course, different parameters.

But still minimal-singles.

Puzzle Image: Show
SudokuFP-002.png
SudokuFP-002.png (6.57 KiB) Viewed 182 times

Non-Consecutive Sudoku with additional Forbidden Pairs: {1,9}, {2,4}, {6,8}, {6,9}

Solution: Show
Code: Select all
 +-------+-------+-------+
 | 1 7 5 | 3 9 4 | 8 2 6 |
 | 6 2 8 | 5 7 1 | 3 9 4 |
 | 3 9 4 | 8 2 6 | 1 5 7 |
 +-------+-------+-------+
 | 8 4 9 | 2 6 3 | 5 7 1 |
 | 2 6 3 | 7 1 5 | 9 4 8 |
 | 5 1 7 | 9 4 8 | 2 6 3 |
 +-------+-------+-------+
 | 7 5 1 | 4 8 2 | 6 3 9 |
 | 9 3 6 | 1 5 7 | 4 8 2 |
 | 4 8 2 | 6 3 9 | 7 1 5 |
 +-------+-------+-------+
User avatar
Mathimagics
2017 Supporter
 
Posts: 1262
Joined: 27 May 2015
Location: Canberra

Sudoku No8kN8 and Latin Square Tennis

Postby tarek » Thu Jan 17, 2019 12:02 pm

Here is my 1st puzzle using an FP truth table. Thanks for qiuyanzhe's knowledge about popular FP puzzles, I even managed to find a name to go with it.

Code: Select all
Sudoku No8kN8  (No 8 Knight)
Easy
No 2 cells a Knight move apart can give you 8 through simple arithmatic operations

......................1.....12..7................3..9.7.....241...8..............
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . 1 . | . . . |
+-------+-------+-------+
| . 1 2 | . . 7 | . . . |
| . . . | . . . | . . . |
| . . . | . 3 . | . 9 . |
+-------+-------+-------+
| 7 . . | . . . | 2 4 1 |
| . . . | 8 . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+

Puzzle image: Show
Image

Hint: Show
Code: Select all
1 * 8 = 8
1 + 7 = 8
8 / 1 = 8
9 - 1 = 8
2 * 4 = 8
2 + 6 = 8
3 + 5 = 8
4 + 4 = 8

Only + - * / are basic arithmatic operations so 2 ^ 3 = 8 is not included

And my second with an Australian open flavour

Code: Select all
Latin square No Tennis:
Easy
Latin square Puzzle, adjacent cells combination can't be an Australian Tennis Open final set result score
.234.........8.....8.....1............9..13............6.....2.....3......42.7.9.
. 2 3 4 . . . . .
. . . . 8 . . . .
. 8 . . . . . 1 .
. . . . . . . . .
. . 9 . . 1 3 . .
. . . . . . . . .
. 6 . . . . . 2 .
. . . . 3 . . . .
. . 4 2 . 7 . 9 .

Puzzle image: Show
Image

Hint: Show
Code: Select all
Don't forget 7-5 7-6 8-6 9-7
User avatar
tarek
 
Posts: 2962
Joined: 05 January 2006

Re: SudokuFP

Postby Mathimagics » Thu Jan 17, 2019 4:54 pm

.
Struth, tarek !! :lol:

How about "no 6 can be adjacent to X or Y", where:

  • X is the number of AFL premierships St Kilda has won the Grand Final in the past 125 years
  • Y is their greatest winning margin in a Grand Final

Sob ... :cry:
User avatar
Mathimagics
2017 Supporter
 
Posts: 1262
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby m_b_metcalf » Wed Jan 23, 2019 2:41 pm

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:

I couldn't resist getting into this game. I have modified my random grid generator and my solvers to handle NC+, which I understand to be the horizontal and vertical forbidden pairs 1-2,2-3,3-4,4-5,5-6,6-7,7-8,8-9,9-1.

I tested the solvers on the puzzles published here, finding unique solutions and the difficulty indication shown:

Code: Select all
tarek
..28........3.1.................................................................. SE > 9
......2...........................1.........................3...........1...2.... SE > 9
.......................5.........7......9......1.........6....................... SE > 9
.....................1...2...8...6...2.............3...7.........2............... singles
........1....2.......................3..1.58..............5........3....6........ singles

Code: Select all
Mathimagics
.1.........4.................................5................................... SE > 9


I then generated some new puzzles of my own. I didn't reach down to only 3 clues, but found these which might be of interest.

Code: Select all
 . . . . . 5 . . .
 . . . . . . . . .
 . . . . . . . . .
 . . . . . . . . .
 . 6 . . 7 . . 3 .
 . . . . . . . . .
 . . . . . . . . .
 . . . . . . . . .
 . . . 5 . . . . .     NC+, 5 clues, symmetric, SE > 9

Code: Select all
 . . . . . . . . .
 . . . . . . . . .
 . . . . . . . . .
 . . . . . . . . .
 . . . . . . . . .
 . . . . . . . . .
 . . . . . . . . .
 . . . . . 9 . . .
 . . 6 . 2 . . . 5     NC+, 4 clues on just two rows, SE > 9


I will work on NC+X soon. Two massive puzzles that I've generated I'm posting on a separate thread.

Regards,

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

Re: SudokuFP

Postby tarek » Wed Jan 23, 2019 7:10 pm

m_b_metcalf wrote:I couldn't resist getting into this game. I have modified my random grid generator and my solvers to handle NC+, which I understand to be the horizontal and vertical forbidden pairs 1-2,2-3,3-4,4-5,5-6,6-7,7-8,8-9,9-1

Excellent :D
User avatar
tarek
 
Posts: 2962
Joined: 05 January 2006

Re: SudokuFP

Postby Mathimagics » Wed Jan 23, 2019 7:52 pm

.
Are we having fun or what? 8-)

Mike, I'm curious to know, how did you go about rating that 3-clue puzzle of mine?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1262
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby m_b_metcalf » Thu Jan 24, 2019 7:43 am

Mathimagics wrote:Mike, I'm curious to know, how did you go about rating that 3-clue puzzle of mine?


Mathimagics, I have sets of solvers that can handle, at the lowest level, various basic techniques, and beyond that solvers that correspond, empirically, to various SE ranges. Above ~9.9 a brute force solver kicks in, and that's what's needed to solve your puzzle. The two massive ones I posted are solved in the SE range from about 8.5 to 9.8.

Please note that every line of code I use I've written myself (apart from SE, of course) so my potting around is totally independent of other popular programs (for good or for ill).

Regards,

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

Re: SudokuFP

Postby Mathimagics » Thu Jan 24, 2019 10:50 am

Ok, good to know!

You might already know this, but apparently your Samurai-X (the one with the lonely "7" in the central grid) drove JSudoku totally nuts, and left Broughton's SudokuSolver begging for mercy … Nice going! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1262
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby m_b_metcalf » Thu Jan 24, 2019 12:11 pm

Mathimagics wrote:You might already know this, but apparently your Samurai-X (the one with the lonely "7" in the central grid) drove JSudoku totally nuts, and left Broughton's SudokuSolver begging for mercy … Nice going! 8-)


Thanks for the information; I didn't know.
m_b_metcalf wrote:I will work on NC+X soon.

Of course, as I've realised, an impossible task :idea:
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10011
Joined: 15 May 2006
Location: Berlin

Re: No8kN8 & No tennis solutions

Postby tarek » Thu Jan 24, 2019 2:18 pm

Code: Select all
No8kN8
167385924284769315953214768312947586849652137576138492738596241495821673621473859
+-------+-------+-------+
| 1 6 7 | 3 8 5 | 9 2 4 |
| 2 8 4 | 7 6 9 | 3 1 5 |
| 9 5 3 | 2 1 4 | 7 6 8 |
+-------+-------+-------+
| 3 1 2 | 9 4 7 | 5 8 6 |
| 8 4 9 | 6 5 2 | 1 3 7 |
| 5 7 6 | 1 3 8 | 4 9 2 |
+-------+-------+-------+
| 7 3 8 | 5 9 6 | 2 4 1 |
| 4 9 5 | 8 2 1 | 6 7 3 |
| 6 2 1 | 4 7 3 | 8 5 9 |
+-------+-------+-------+
1 * 8 = 8
1 + 7 = 8
8 / 1 = 8
9 - 1 = 8
2 * 4 = 8
2 + 6 = 8
3 + 5 = 8
4 + 4 = 8
FP Knight (1,7)(1,8)(1,9)(2,4)(2,6)(3,5)(4,4)

LS No tennis
123478965372189654487396512718965243249651378896524137965843721651732489534217896
1 2 3 4 7 8 9 6 5
3 7 2 1 8 9 6 5 4
4 8 7 3 9 6 5 1 2
7 1 8 9 6 5 2 4 3
2 4 9 6 5 1 3 7 8
8 9 6 5 2 4 1 3 7
9 6 5 8 4 3 7 2 1
6 5 1 7 3 2 4 8 9
5 3 4 2 1 7 8 9 6
FP Adjacent (1,6)(2,6)(3,6)(4,6)(5,7)(6,7)(6,8)(7,9)
User avatar
tarek
 
Posts: 2962
Joined: 05 January 2006

Re: SudokuFP

Postby Mathimagics » Thu Jan 24, 2019 2:37 pm

m_b_metcalf wrote:Thanks for the information; I didn't know.


I posted it at RB's forum before I had figured out how to get RB's SudokuSolver working, and Ed responded.

It is rather ironic that a simple DLX solver can solve this with minimal fuss, but Solver/Helper/Anayser software struggles with it.

But as I said over there, comparison on this basis (ability to solve puzzles) is pretty futile. After all, what can a DLX solver tell you about a puzzle other than ("Bingo!" XOR "No cigar")? 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1262
Joined: 27 May 2015
Location: Canberra

Re: SudokuFP

Postby tarek » Thu Jan 24, 2019 2:46 pm

Mathimagics wrote:But as I said over there, comparison on this basis (ability to solve puzzles) is pretty futile. After all, what can a DLX solver tell you about a puzzle other than ("Bingo!" XOR "No cigar")? 8-)
Surly you can see how DLX can tell you that a puzzle is solvable by singles or not!!! :idea: ;)
User avatar
tarek
 
Posts: 2962
Joined: 05 January 2006

PreviousNext

Return to Sudoku variants