My solver / Looking for new strategies to implement

Programs which generate, solve, and analyze Sudoku puzzles

Re: My solver / Looking for new strategies to implement

Postby StrmCkr » Thu Nov 23, 2023 3:15 am

Eri's functions are scattered around here in many different places,
the entire thread was lost + didn't make sense to rebuild most of the "formations" as it was all covered under fish and garnered little interest.

{outside a few short and sweet easy shapes people could spot and some made its way into hodoku}


its a type of strong link for chaining : this part i kept alive here an there.
Code: Select all
 
 / x /
x * x
/ x /


in essence all the cells for a box are located on 1 row and 1 col. where the box has at least 2 cells, or a max of 5.
the centre cell may or may not be empty of x.

the centre cells is the key hence the * for linking chains around corners via row/col swaps, the * is the exact centre ie "intersection" row & col of the empty rectangle formation hence named ERi

the centre cell is also important to note as if its occupied when using nice-loops this cannot be used as a strong link and can only be used as a weak link because the * is both on and off.

aic's more care is needed for elimination rules as the centre cell is both on and off.

if the star is off then it can be used easily in nice loops as both strong or a weak node.

http://forum.enjoysudoku.com/strong-links-weaklinks-t34655.html?hilit=strong%20link

Oh then my solver does store these spaces actually
interesting, i ' ll have to double check as i didn't see the condensed spaces being used when i was looking at hidden sets. or fish
Code: Select all
  var pos = strategyManager.RowPositionsAt(row, number);
                if (pos.Count != 2) continue;

                if (lines.TryGetValue(pos, out var n))
                {
                    if (ProcessRow(strategyManager, pos, row, number, n)) return;
                }


okay i do see, but it seems to be running not how i was expecting
: i was expecting Rn[x,n] & Rn[x,n2] = power-set or bit-set or set where this version tags degenerative cases as its unionizes the numbers ie two singles is still a pair, or a single and a digit with 2 spots is still a pair.

current version looks up a number see if it has 2 spots, and then passes it to an analyzer and repeats passing hits to the analyzer.

I'm sorry but you totally lost me on the AIC vs Nice Loops part.
apologies: i tend to prattle on, this place moved on from nice-loops in 2010ish and focuses on the shorter easier language of a.i.c way less confusion since for discussions. {Same goes for APE/ATE evolved to Almost locked sets instead of analyzing pair matching of subsets tedious and time consuming }

I guess there is quite an experience gap between the two of us.
yes more then likely, I've been here a time.

I currently do the wiki editing on https://www.reddit.com/r/sudoku/wiki/index/ as well: lots of information all in 1 spot.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Re: My solver / Looking for new strategies to implement

Postby MAGREMENT » Thu Nov 23, 2023 1:49 pm

Okay thank's for ERI stuff, I'll look into it when I decide to implement it in my solver

StrmCkr wrote:okay i do see, but it seems to be running not how i was expecting
: i was expecting Rn[x,n] & Rn[x,n2] = power-set or bit-set or set where this version tags degenerative cases as its unionizes the numbers ie two singles is still a pair, or a single and a digit with 2 spots is still a pair.

current version looks up a number see if it has 2 spots, and then passes it to an analyzer and repeats passing hits to the analyzer.


I see what you mean but my solver doesn't check for degerative cases for hidden doubles for optimization purposes. You may have noticed there are multiple implementations for hidden sets (HiddenSingleStrategy, HiddenDoublesStrategy, HiddenSetsStrategy), because checking for theses cases for doubles doesn't really make sense as there would be a hidden single. This allows me to only have to check each RN space once and not compare each combination, which gives quite a good
speed boost when solving big sets of Sudoku's.

StrmCkr wrote:I currently do the wiki editing on https://www.reddit.com/r/sudoku/wiki/index/ as well: lots of information all in 1 spot.


Thanks for the useful links as always !
MAGREMENT
 
Posts: 62
Joined: 20 October 2023

Re: My solver / Looking for new strategies to implement

Postby StrmCkr » Thu Nov 23, 2023 8:28 pm

I have mine coded as a power set cycle (as sets) per type (1,2,3,4)
I just rip through specific combinations for the size and union the sector for speed up's it skips non active digit sets.

degenerative cases are included to skip steps by using a higher function

Like a quad =triple +singles or 2 pairs etc and my elims are als based instead of 1 sector elims and use Blr for cleanup
( Elim per digit for the set instead of whole set)

So instead of two+ seperate moves and post Blr cleanup it hits everything at the same time.
For rapid solving grids instead of hierachy sequencing,

Same thing for fish cycles 2 singles is still an x wing etc.

Either way, diffrent ways to do things.
example
The way yours is coded it would miss the 135 triple, 15 pair, and only spot the single 1 (for 3 cycles of singles)
as Bn space is (1) has 1 cell, (3) has 2 cells, (5) has 2 cells and non of them are identical
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Re: My solver / Looking for new strategies to implement

Postby creint » Sat Nov 25, 2023 9:54 am

MAGREMENT wrote:
creint wrote:A scan all function could help debug strategies.


I guess you mean a function to get every solution/elimination possible for each strategy given a grid. Would it be better to put it in the UI solver or as a separate command line application ?

I mean the function "Find all steps" from Hodoku. So displaying the steps without applying them. So you can test if you solver can find them without previous exclusions.

MAGREMENT wrote:
creint wrote:Sudokuwiki has not documented every possible edge case. And has only documented known common strategies.


I know that's why I've been coming here a lot more recently but, as I said, I sometimes find it a bit hard to find what I want or understand everything

If you understand the generic logic behind the exclusions then you can discover new strategies.
Hardcoding many known strategies does not make you find unknown strategies.
Here are the 3 rules I know of:
• Subset leads to contradiction
• Deadly patterns (Only valid in single solution puzzles)
• Symmetry (Only in rare cases, puzzles that support it)


Now that pasting is supported, here is an UR your solver does not find:
-4r1c4 (4r1c4 - 1r3c4 - 4r3c1 - 1r1c1)
Code: Select all
.--------------------------------.--------------------------------.---------------------------------.
| 12        123456789  123456789 | 1234      123456789  123456789 | 123456789  123456789  123456789 |
| 23456789  123456789  123456789 | 23456789  123456789  123456789 | 123456789  123456789  123456789 |
| 1234      12356789   12356789  | 1234      12356789   12356789  | 12356789   12356789   12356789  |
:--------------------------------+--------------------------------+---------------------------------:
| 23456789  123456789  123456789 | 23456789  123456789  123456789 | 123456789  123456789  123456789 |
| 23456789  123456789  123456789 | 23456789  123456789  123456789 | 123456789  123456789  123456789 |
| 23456789  123456789  123456789 | 23456789  123456789  123456789 | 123456789  123456789  123456789 |
:--------------------------------+--------------------------------+---------------------------------:
| 23456789  123456789  123456789 | 23456789  123456789  123456789 | 123456789  123456789  123456789 |
| 23456789  123456789  123456789 | 23456789  123456789  123456789 | 123456789  123456789  123456789 |
| 23456789  123456789  123456789 | 23456789  123456789  123456789 | 123456789  123456789  123456789 |
'--------------------------------'--------------------------------'---------------------------------'

Placing one leads to forced UR using only the forcings inside the UR. If you start to use outside the UR then you can combine every strategy then it will be the combination of both that result in seeing exclusions.

You can check out some different SK-loops here:
https://philsfolly.net.au/Sudoku/loops_help.htm
This one is only found with Set Equivalance
Code: Select all
.----------------------.--------------------.----------------------.
| 34568  34578  346789 | 1      679    2    | 34679  56789   34589 |
| 2568   2578   6789   | 3      679    4    | 1679   156789  1589  |
| 3468   3478   1      | 689    5      6789 | 2      6789    3489  |
:----------------------+--------------------+----------------------:
| 1238   6      378    | 2589   239    3589 | 139    4       12359 |
| 234    234    5      | 7      23469  1    | 8      269     239   |
| 9      12348  348    | 24568  2346   3568 | 136    1256    7     |
:----------------------+--------------------+----------------------:
| 7      13458  348    | 2459   12349  359  | 149    1289    6     |
| 1346   134    2      | 469    8      3679 | 5      179     149   |
| 14568  9      468    | 2456   12467  567  | 147    3       1248  |
'----------------------'--------------------'----------------------'
creint
 
Posts: 397
Joined: 20 January 2018

Re: My solver / Looking for new strategies to implement

Postby MAGREMENT » Sat Nov 25, 2023 2:32 pm

creint wrote:I mean the function "Find all steps" from Hodoku. So displaying the steps without applying them. So you can test if you solver can find them without previous exclusions.


I did implement something a bit similar. If you go to "Tools" and click "Full scan" you'll be able to see every elimination/solution proposed by each strategy. Sadly, my strategies lack step descriptions so I can't really print every steps for now. This is definetly something I'll implement in the future.

creint wrote:If you understand the generic logic behind the exclusions then you can discover new strategies.
Hardcoding many known strategies does not make you find unknown strategies.


The things is, I don't really care about finding new strategies. What I like is programming algorithms like Sudoku's strategies, not discover them.

creint wrote:Now that pasting is supported, here is an UR your solver does not find:
-4r1c4 (4r1c4 - 1r3c4 - 4r3c1 - 1r1c1)


Wow ok that is one weird UR :D. My solver indeed doesn't find these for now but I recently found a post about all the types of UR and I'm gonna implement them when I have time.

creint wrote:This one is only found with Set Equivalance


That is weird because I just tested it and my solver does find the SK-Loop
MAGREMENT
 
Posts: 62
Joined: 20 October 2023

Re: My solver / Looking for new strategies to implement

Postby MAGREMENT » Sat Nov 25, 2023 10:23 pm

MAGREMENT wrote:That is weird because I just tested it and my solver does find the SK-Loop


Nevermind that. My solver did find the SK-Loop but only if the hidden single before it wasn't found. My conditions were too strict and this should be corrected for the next update
MAGREMENT
 
Posts: 62
Joined: 20 October 2023

Re: My solver / Looking for new strategies to implement

Postby MAGREMENT » Sun Nov 26, 2023 12:15 am

StrmCkr wrote:example
The way yours is coded it would miss the 135 triple, 15 pair, and only spot the single 1 (for 3 cycles of singles)
as Bn space is (1) has 1 cell, (3) has 2 cells, (5) has 2 cells and non of them are identical


Indeed my solver would only find the singles through 3 cycles, but I don't actually mind that as singles are extremely fast to check up for and don't need much cleanup. I still believe that checking 3 times for singles is faster than checking for triples + degenerative cases. I do see your point tho and I might code up something that does things more your way and compare.
MAGREMENT
 
Posts: 62
Joined: 20 October 2023

Re: My solver / Looking for new strategies to implement

Postby StrmCkr » Sun Nov 26, 2023 4:19 am

Sure, à single is Rn, with size 1 = 9 canddiates to match against or 27 cycles for the 3
(Worste case scenario)

Yes the triple would be slower in a worse case scenario (3x slower)

Compared to 84 combinations for size 3
Which includes degenerative cases:
A= 1 2
B = 1 3
C = 3

Union (a+b+c) = [123]

as a union of each of the 3 digits the result = 3 or it dosent if it does you matched the powerset and your gold.

I'd have it as condition sensing checking: for > 0 and < n+1
(where n is the set size)

As a find all output: people like Me use /or want to ensure the code finds everything I could use for the type of move I selected.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Re: My solver / Looking for new strategies to implement

Postby MAGREMENT » Sun Nov 26, 2023 5:37 am

StrmCkr wrote:I'd have it as condition sensing checking: for > 0 and < n+1
(where n is the set size)


I might indeed add this in the future but it is not my priority for now.

As a side note, my full scan does find your example :

StrmCkr wrote:Which includes degenerative cases:
A= 1 2
B = 1 3
C = 3

Union (a+b+c) = [123]


Code: Select all
FULL SCAN :

+-----------------------------+-----------------------------+-----------------------------+
|12        123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
|13        123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
|3         123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
+-----------------------------+-----------------------------+-----------------------------+
|123456789 123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
|123456789 123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
|123456789 123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
+-----------------------------+-----------------------------+-----------------------------+
|123456789 123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
|123456789 123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
|123456789 123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
+-----------------------------+-----------------------------+-----------------------------+

Naked Single--------------------------------------

r3c1 == 3

Naked Triple--------------------------------------

r4c1 <> 1
r5c1 <> 1
r6c1 <> 1
r7c1 <> 1
r8c1 <> 1
r9c1 <> 1
r4c1 <> 2
r5c1 <> 2
r6c1 <> 2
r7c1 <> 2
r8c1 <> 2
r9c1 <> 2
r4c1 <> 3
r5c1 <> 3
r6c1 <> 3
r7c1 <> 3
r8c1 <> 3
r9c1 <> 3
r1c2 <> 1
r1c3 <> 1
r2c2 <> 1
r2c3 <> 1
r3c2 <> 1
r3c3 <> 1
r1c2 <> 2
r1c3 <> 2
r2c2 <> 2
r2c3 <> 2
r3c2 <> 2
r3c3 <> 2
r1c2 <> 3
r1c3 <> 3
r2c2 <> 3
r2c3 <> 3
r3c2 <> 3
r3c3 <> 3
MAGREMENT
 
Posts: 62
Joined: 20 October 2023

Re: My solver / Looking for new strategies to implement

Postby StrmCkr » Sun Nov 26, 2023 4:19 pm

Try that as a hidden tripple
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Re: My solver / Looking for new strategies to implement

Postby MAGREMENT » Sun Nov 26, 2023 5:26 pm

StrmCkr wrote:Try that as a hidden tripple


It also finds it

Code: Select all
FULL SCAN :

+-----------------------------+-----------------------------+-----------------------------+
|12456789  456789    456789   |123456789 123456789 123456789|123456789 123456789 123456789|
|13456789  456789    456789   |123456789 123456789 123456789|123456789 123456789 123456789|
|3456789   456789    456789   |123456789 123456789 123456789|123456789 123456789 123456789|
+-----------------------------+-----------------------------+-----------------------------+
|123456789 123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
|123456789 123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
|123456789 123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
+-----------------------------+-----------------------------+-----------------------------+
|123456789 123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
|123456789 123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
|123456789 123456789 123456789|123456789 123456789 123456789|123456789 123456789 123456789|
+-----------------------------+-----------------------------+-----------------------------+

Hidden Single-------------------------------------

r1c1 == 2

Pointing Set--------------------------------------

r4c1 <> 1
r5c1 <> 1
r6c1 <> 1
r7c1 <> 1
r8c1 <> 1
r9c1 <> 1
r1c4 <> 2
r1c5 <> 2
r1c6 <> 2
r1c7 <> 2
r1c8 <> 2
r1c9 <> 2
r4c1 <> 3
r5c1 <> 3
r6c1 <> 3
r7c1 <> 3
r8c1 <> 3
r9c1 <> 3

Hidden Triple-------------------------------------

r1c1 <> 4
r1c1 <> 5
r1c1 <> 6
r1c1 <> 7
r1c1 <> 8
r1c1 <> 9
r2c1 <> 4
r2c1 <> 5
r2c1 <> 6
r2c1 <> 7
r2c1 <> 8
r2c1 <> 9
r3c1 <> 4
r3c1 <> 5
r3c1 <> 6
r3c1 <> 7
r3c1 <> 8
r3c1 <> 9


My solver actually does implement your bitset union method starting from triples so it does find degenerative case for those but it would not find :

A : 1
B : 12

As a hidden double because, again, the implementation is different for doubles and singles for speed reasons.
MAGREMENT
 
Posts: 62
Joined: 20 October 2023

Re: My solver / Looking for new strategies to implement

Postby StrmCkr » Mon Nov 27, 2023 2:22 am

Alrighty :)
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Re: My solver / Looking for new strategies to implement

Postby BJGenius » Mon Nov 27, 2023 1:57 pm

@ MAGREMENT:

I'am also coding my own Sudoku solver for a couple of months right now (currently based on EXCEL VBA), and it would be nice to compare the methods implemented. If you need some input, please let me know. I would be glad to be of assistance.

At present, my solver encompasses the following approaches:
- Full House
- Last Digit
- Naked Single
- Hidden Single
- Locked Candidates Type 1 (Pointing Pair/Triple)
- Locked Candidates Type 2 (Claiming)
- Naked Pair
- Hidden Pair
- Naked Triple (incl. Locked Triple)
- Hidden Triple
- Naked Quad
- Hidden Quad
- Magic Triple
- Magic Quad
- X-Wing
- Finned X-Wing
- Sashimi Finned X-Wing
- Finned Mutant X-Wing
- Swordfish
- Finned Swordfish
- Sashimi Finned Swordfish
- Franken Swordfish
- Mutant Swordfish
- Finned Mutant Swordfish
- Jellyfish
- Finned Jellyfish
- Rectangle Elimination (substituting Empty Rectangle, but more efficient)
- Skyscraper
- Two-String Kite
- Turbot Fish
- Simple Coloring (Color Wrap and Color Trap) (extended version)
- Muli Coloring (extended version)
- 3D Medusa (Rule 1 to 6)
- Supercoloring (Contradiction Rule and Identity Rule)
- Unique Rectangle (incl. UR with missing candidates, Avoidable Rectangle)
- UR Type 1 To Type 6 (incl. Forbidden Pattern)
- Hidden UR Type 1, 2, 3
- BUG + 1
- BUG + 2 incl. Forcing Chain
- BUG + 3 incl. Forcing Chain
- Unique Loop (self-developed generalization of Unique Rectangle)
- UL Type 1 To 6 (in accordance to UR)
- X-Chain (incl. Grouped Nodes, Discontinuous Loop With Strong/Weak Links, Continuous Loop)
- XY-Chain
- Remote Pairs
- SK Loops
- Alternate Inference Chain (incl. Continuous Loop)
- XY-Wing
- W-Wing (incl. Grouped Nodes, Doubly Linked W-Wing)
- XYZ-Wing
- WXYZ-Wing
- VWXYZ-Wing
- UVWXYZ-Wing
- ALS-XZ
- ALS-XY-Wing
- Death Blossom
- ALS-XY-Chain (currently deactived due to ineffectiveness)
- Junior Exocet (incl. JE+/++ variants, Rule 1, 2, 3, 4, 5, 6 (+6b), 7, 8, 9, 10, 11, 12, JE+/++ Target Cell Simulation, Incompatible Base Pairs, Double JEs)
- Pattern Overlay Method
- Aligned Pair Exclusion
- Aligned Triple Exclusion
- Subset Exclusion (up to 3 unfilled cells, currently deactivated)
- Set Equivalence Theory
- Phistomefel Ring (generalized)
- Aad's Theorem (generalized)
- Aad's Tetro Trick (generalized)
- My own Tetro Trick
- Row-Column SET
- Line-Block SET
- Checkerboard SET (2x2, 3x3, 4x4)
- Forcing Chains (Type 1 to 4)
- Dual Cell Forcing Chain
- Triple Cell Forcing Chain
- Quad Cell Forcing Chain
- Digit Forcing Chain
- House Forcing Chain
- Swami Approaches
- Swami Quad Loop
- Swami Offset Quad Loop
- Swami Quad Snake
- Swami Split Quad Loop
- Swami Split Offset Loop
- Swami Sandwich
- Swami Butterfly
- Sue De Coq (Type 1, 2)
- TriDagon (Type 1, 2, 3)
- Firework (Double Firework, Triple Firework, Quadruple Firework)
- Brute Force (currently deactivated)
BJGenius
 
Posts: 1
Joined: 27 November 2023

Re: My solver / Looking for new strategies to implement

Postby MAGREMENT » Mon Nov 27, 2023 5:59 pm

v1.1.0 is out !

Quite a big release today.

- New "Strategy Manager" UI interface :
No need to modify the strategies.ini file by hand, you can now do it in the app ! You can search any strategy implemented in the search bar and drag them to the strategy list to add them. You can also shuffle around strategies order and remove them by draging them to the bin. If you click on a strategy in the strategy list, its properties will show up in the central rectangle and you'll be able to modify them.

-Strategies added :
a) 2-String Kite
b) Skyscraper
c) Fish Generalization (Only perfects one for now, Finned and Cannibalistic fishs will arrive later)

-Bug fixes :
a) In the settings, the solving and given cell color didn't match their actual color
b) SK-Loops would not be found in certain conditions (thanks creint)
MAGREMENT
 
Posts: 62
Joined: 20 October 2023

Re: My solver / Looking for new strategies to implement

Postby MAGREMENT » Wed Nov 29, 2023 12:20 am

v1.1.1 is out !

-Strategies added :
a)ALS-Chains
b)AHS-Chains

-Bug fixes :
a)Shuffling a strategy would change it's enabled property
MAGREMENT
 
Posts: 62
Joined: 20 October 2023

PreviousNext

Return to Software