The New Sudoku Players' Forum

[Mathimagics]

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


[tarek]

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

[Mathimagics]

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 …

[Mathimagics]

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


[tarek]

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

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

Hint: Show

Code: Select all

Don't forget 7-5 7-6 8-6 9-7

[Mathimagics]

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

[m_b_metcalf]

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

[tarek]

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

[Mathimagics]

.
Are we having fun or what?

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

[m_b_metcalf]

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

[Mathimagics]

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!

[m_b_metcalf]

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.

I will work on NC+X soon.

Of course, as I've realised, an impossible task

[tarek]

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)

[Mathimagics]

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

[tarek]

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