## SudokuFP

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: SudokuFP

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    -    7SX      2    1    - |  1    -    -SP      1    2    6 |  1    -    2PX      1    1    - |  1    -    -`

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: Truth tables

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

tarek

Posts: 3745
Joined: 05 January 2006

### Re: SudokuFP

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: 61538472984792615339257148697425386153861729426184953748316297572649531815973864210: 53816249726179483594753826179425361835281697418647935281394752647962518362538174911: 58379246192716483564153829716825397479481635235247961883592714627964158341638572912: 17539482662857139439482615784926357126371594851794826375148263993615748248263971513: 92738514658364172914692738579425386135281649761847925346179253883516497227953861414: 71538692496274135838492571684725316962941758315386924753869247129617483547153869215: 57148293693615728428463975184926351736271584971594836215739462849382617562857149316: 52694718374938152618362574961825397497481635235247961883579246129716483546153829718: 526947183749381526183625749618253974974816352352479618835794261497162835261538497Total grids by NFP:nfp =  9, ng =  63714nfp = 10, ng =   2544nfp = 11, ng =   2602nfp = 12, ng =  19786nfp = 13, ng =    733nfp = 14, ng =    648nfp = 15, ng =   2999nfp = 16, ng =   5528nfp = 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>GenMinimalS715386924962741358384925716847253169629417583153869247538692471296174835471538692NC modeSingles modeClues = 1613: ...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 x715386924962741358384925716847253169629417583153869247538692471296174835471538692FP mode, NFP = 14Singles mode07: ..........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 …

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuFP

.
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 (6.57 KiB) Viewed 358 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 | +-------+-------+-------+`

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Sudoku No8kN8 and Latin Square Tennis

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)EasyNo 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

Hint: Show
Code: Select all
`1 * 8 = 81 + 7 = 88 / 1 = 89 - 1 = 82 * 4 = 82 + 6 = 83 + 5 = 84 + 4 = 8Only + - * / 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:EasyLatin 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

Hint: Show
Code: Select all
`Don't forget 7-5 7-6 8-6 9-7`

tarek

Posts: 3745
Joined: 05 January 2006

### Re: SudokuFP

.
Struth, tarek !!

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 ...

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuFP

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

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

m_b_metcalf
2017 Supporter

Posts: 11193
Joined: 15 May 2006
Location: Berlin

### Re: SudokuFP

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

tarek

Posts: 3745
Joined: 05 January 2006

### Re: SudokuFP

.
Are we having fun or what?

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

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuFP

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

m_b_metcalf
2017 Supporter

Posts: 11193
Joined: 15 May 2006
Location: Berlin

### Re: SudokuFP

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!

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuFP

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!

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

m_b_metcalf
2017 Supporter

Posts: 11193
Joined: 15 May 2006
Location: Berlin

### Re: No8kN8 & No tennis solutions

Code: Select all
`No8kN8167385924284769315953214768312947586849652137576138492738596241495821673621473859+-------+-------+-------+| 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 = 81 + 7 = 88 / 1 = 89 - 1 = 82 * 4 = 82 + 6 = 83 + 5 = 84 + 4 = 8FP Knight (1,7)(1,8)(1,9)(2,4)(2,6)(3,5)(4,4)LS No tennis1234789653721896544873965127189652432496513788965241379658437216517324895342178961 2 3 4 7 8 9 6 53 7 2 1 8 9 6 5 44 8 7 3 9 6 5 1 27 1 8 9 6 5 2 4 32 4 9 6 5 1 3 7 88 9 6 5 2 4 1 3 79 6 5 8 4 3 7 2 16 5 1 7 3 2 4 8 95 3 4 2 1 7 8 9 6FP Adjacent (1,6)(2,6)(3,6)(4,6)(5,7)(6,7)(6,8)(7,9)`

tarek

Posts: 3745
Joined: 05 January 2006

### Re: SudokuFP

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")?

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: SudokuFP

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")?
Surly you can see how DLX can tell you that a puzzle is solvable by singles or not!!!

tarek

Posts: 3745
Joined: 05 January 2006

PreviousNext