sunnieshine / sudoku Goto Github PK

Step to repro

1. Open the program and generate a puzzle.
2. Click "Get all steps".
3. The all steps found, now we paste a puzzle from clipboard.
4. Click "Get all steps" again.
5. The last step list will be displayed rather than the correct one (the step list from this newer puzzle).

The technique Unique Loop is powerful and fun, but the code is copied from the project Sudoku Explainer, so I haven't used GridMap in my own code. In addition, there is a bug in UL type 3.
I wanna re-write this technique and implement four types. Type 5 in UR will be regarded as type 2.

Reference: https://blog.walterlv.com/post/get-gray-reversed-color.html

I don't know why this bug appears, but this bug can be fixed easily.

We have changed a new algorithm to search for all basic UR and AR types (type 1 to 6, and type 4 and 6 does not exist in ARs). However, UR contains about 20 different types in total, so we should implement them one by one. Previous to-do issue is #6.

Extended UR patterns (To-do list):

• URs:
  • UR + 2:
    • UR + 2D
    • UR + 2B/1SL
    • UR + 2D/1SL
  • UR + 3:
    • UR + 3X
    • UR + 3x/1SL
    • UR + 3X/1SL
    • UR + 3X/2SL
    • UR + 3N/2SL
    • UR + 3U/2SL
    • UR + 3E/2SL
  • UR + 4:
    • UR + 4x/1SL
    • UR + 4X/1SL
    • UR + 4x/2SL
    • UR + 4X/2SL
    • UR + 4X/3SL
    • UR + 4C/3SL
  • Other types:
    • UR-XY-Wing
    • UR-XYZ-Wing
    • UR-WXYZ-Wing

I think I may re-write BUG type 3... :(

Sometimes, an SdC cannot be found, and rendering of SdCs sometimes wrong. Although I give a solution to replace some of SdCs, this problem is not solved.
I will re-write SdC and add a new feature to search Cannibalistic SdCs.

SdC:

.---------------------------------.---------------------------------.---------------------------------.
|  259        257        79       |  678        4          5-68     |  13         167        137      |
|  1          57         6        |  3          57         9        |  2          8          4        |
|  3          8          4        |  1          67         2        |  5          9          67       |
:---------------------------------+---------------------------------+---------------------------------:
|  457        1          3        |  B79        B579       B45      |  6          2          8        |
|  6          45         2        |  B78        13-5       C3458    |  17         157        9        |
|  57         9          8        |  26-7       12-5       C56      |  4          3          157      |
:---------------------------------+---------------------------------+---------------------------------:
|  29         3          1        |  5          269        7        |  8          4          26       |
|  8          267        5        |  4          23         1        |  9          67         237      |
|  249        2467       79       |  269        8          A36      |  137        1567       1235     |
'---------------------------------'---------------------------------'---------------------------------'

Cannibalistic SdC:

.---------------------------------.---------------------------------.---------------------------------.
|  126        5          469      |  7          24         8        |  14         3          B29      |
|  7          38         238      |  1          45         9        |  45         B28        6        |
|  A12       A-189       A24      |  A345       6          A23      |  7          C1-289     C58      |
:---------------------------------+---------------------------------+---------------------------------:
|  3          2          789      |  469        4789       47       |  689        5          1        |
|  4          789        1        |  569        258        27       |  3          689        28       |
|  5          6          89       |  39         189        123      |  289        4          7        |
:---------------------------------+---------------------------------+---------------------------------:
|  1268       17         267      |  49         3          147      |  25689      189        2589     |
|  9          13         2367     |  8          17         5        |  126        126        4        |
|  18         4          5        |  2          19         6        |  189        7          3        |
'---------------------------------'---------------------------------'---------------------------------'

This issue will introduce a new sudoku data structure SudokuGrid using structs to implement. The methods should be implemented are:

public unsafe struct SudokuGrid
{
    public static readonly SudokuGrid Undefined;
    public static readonly SudokuGrid Empty;
    
    private fixed int _values[81];
    
    public SudokuGrid(short* masks);
    public SudokuGrid(short[] masks);
    public SudokuGrid(ReadOnlySpan<T> masks);
    
    public readonly bool HasSolved { get; }
    public readonly int CandidatesCount { get; }
    public readonly int GivensCount { get; }
    public readonly int ModifiablesCount { get; }
    public readonly int EmptiesCount { get; }
    
    public static delegate* managed<ref SudokuGrid, in ValueChangedArgs, void> ValueChanged { get; }
    public static delegate* managed<ref SudokuGrid, void> RecomputeCandidates { get; }
    
    public int this[int cell] { readonly get; set; }
    public bool this[int cell, int digit] { readonly get; set; }
    
    public readonly bool SimplyValidate();
    public override readonly bool Equals(object? obj);
    public readonly bool Equals(SudokuGrid other);
    public override readonly int GetHashCode();
    public readonly int[] ToArray();
    public readonly short GetMask(int offset);
    public readonly short GetCandidateMask(int cell);
    public override readonly string ToString();
    public readonly string ToString(string? format);
    public readonly string ToString(string? format, IFormatProvider? formatProvider);
    public readonly CellStatus GetStatus(int cell);
    public readonly IEnumerable<int> GetCandidates(int cell);
    public readonly IEnumerator<short> GetEnumerator();
    readonly IEnumerator IEnumerable.GetEnumerator();
    public void Fix();
    public void Unfix();
    public void Reset();
    public void SetStatus(int cell, CellStatus status);
    public void SetMask(int cell, short mask);
    
    public static ref SudokuGrid Parse(ReadOnlySpan<char> str);
    public static ref SudokuGrid Parse(string str);
    public static ref SudokuGrid Parse(string str, bool compatibleFirst);
    public static ref SudokuGrid Parse(string str, GridParsingOption gridParsingOption);
    public static bool TryParse(string str, out SudokuGrid result);
    public static bool TryParse(string str, GridParsingOption gridParsingOption, out SudokuGrid result);
    public static SudokuGrid CreateInstance(int[] gridValues);
    
    public static bool operator ==(in SudokuGrid left, in SudokuGrid right);
    public static bool operator !=(in SudokuGrid left, in SudokuGrid right);
    
    
    private struct Enumerator : IEnumerator<short>
    {
        public Enumerator(short* arr);
        
        private readonly short* _start;
        private short* _currentPointer;
        private int _currentIndex;
        
        public Enumerator(short* arr);
        public short Current;
        object? IEnumerator.Current;
        
        public void Dispose();
        public void Reset();
        public bool MoveNext();
    }
    
    private readonly struct ValueChangedArgs
    {
        public ValueChangedArgs(int cell, short oldMask, short newMask, int setValue);
        
        public int Cell { get; }
        public short OldMask { get; }
        public short NewMask { get; }
        public int SetValue { get; }
        
        public void Deconstruct(out int cell, out short oldMask, out short newMask, out int setValue);
    }
    
    private ref struct GridParser
    {
        public GridParser(string parsingValue);
        public GridParser(string parsingValue, bool compatibleFirst);
        
        public string ParsingValue { readonly get; }
        public readonly bool CompatibleFirst { get; }
        
        public ref SudokuGrid Parse();
        public ref SudokuGrid Parse(GridParsingOption gridParsingOption);
    }
    
    private ref struct GridFormatter
    {
        public GridFormatter(bool multiline);
        
    	public char Placeholder { readonly get; set; }
        public readonly bool Multiline { get; }
        public bool WithModifiables { readonly get; set; }
        public bool WithCandidates { readonly get; set; }
        public bool TreatValueAsGiven { readonly get; set; }
        public bool SubtleGridLines { readonly get; set; }
        public bool HodokuCompatible { readonly get; set; }
        public bool Sukaku { readonly get; set; }
        public bool Excel { readonly get; set; }
        
        public readonly string ToString(in SudokuGrid grid);
        public readonly string ToString(in SudokuGrid grid, string? format);
        
        public static ref readonly GridFormatter Create(GridOutputOptions gridOutputOption);
        public static ref readonly GridFormatter Create(string? format);
    }
}

[Test issue]

Is your feature request related to a problem? Please describe.
Extended Subset Principles is always the subset of the technique ALS-XZ, so the program will use ALS-XZ searcher to search for them. However, the view of the ESPs may be the same as those of ALS-XZs.
I would like to add a feature to add a new look for ESPs, the region of the bi-value ALS should not be displayed finally.

Describe the solution you'd like
Add a feature that displaying the ESPs different with normal ALS-XZs. For instance, the highlight region of the bi-value ALS should not be displayed, or else all highlight regions can be removed.
In addition, the name of the technique can be 'Extended Subset Principle', where the text 'subset' can be replaced by the subset name of the number of the cells in this structure.

I found sometimes Exocets may contain the conjugate pairs as eliminations, terrible...

Sometimes death blossom is too costly-memory and high-complexity, so we can change into another algorithm to enhance and optimize the performance.

Pseudo code:

Searcher Death blossom:
collect all ALSes
for each candidate in all candidates
    try to set candidate
    for each ALS combinations in all combinations for all ALSes when relative
        try to eliminate candidate in these ALSes
        for each digit in all digits in these ALSes
            if a certain cell cannot contain any possibilities because of these ALSes
                Death blossom found

Searcher Complex fish:
for each digit in 1 to 9
    eliminations = POM search eliminations
    if eliminations is not an empty set
        for each size in 2 to 5
            for each base set in all subsets in all sets whose size is size
                for each elimination in these eliminations
                    try to set elimination
                    for each cover sets in all subsets in structure whose size is size - 1
                        set = new set of same set in eliminations that contains elimination
                        if set is not empty
                        cover sets += set
                        complex fish found

A friend told that "A broken wing can be found using reversal calculation idea."
The pesudo code is below:

for each digit in 0 to 8 // 1 to 9
    if pom.Eliminations.Count != 0
        for each elimintion in pom.Eliminations
            try set elimination into grid
            search for conjugate pairs in grid about digit
            if conjugate pairs can forms a cycle && (length of cycle & 1) != 0
                Broken wing found

In details:
SsteCannot find source: System.Windows.Data Error: 4 : Cannot find source for binding with reference 'RelativeSource FindAncestor, AncestorType='System.Windows.Controls.ItemsControl'...

Describe the bug
If I use painting tools to draw candidates, the coordinates will always be calculated incorrectly.

To Reproduce
Steps to reproduce the behavior:

1. Click a position on the grid.
2. The candidate drawn may be wrong.

UR is an important technique in sudoku. However, there are almost 20 different patterns of sudoku (You can find them at this post). If using the older algorithm, the code can be made ugly and very difficult to debug.

Now we use a new algorithm to re-write UR searching.

To-do list:

• URs
  • UR type 1/UR + 1
  • UR type 2/UR + 2b
  • UR type 3:
    • UR type 3/UR + 2X with naked subsets (up to size 4)
    • UR type 3 with hidden subsets (up to size 4)
  • UR type 4/UR + 2X/1SL
  • UR type 5/UR + 2d
  • UR type 6, special case of UR + 2D/1SL
  • Hidden UR, UR + 3C/2SL
• ARs
  • AR type 1
  • AR type 2
  • AR type 3
  • AR type 5
  • Hidden AR

AR type 4 and 6 does not exist.

The instance of a Continuous Nice Loop with Locked Candidates sometimes wrong. Sometimes, the instance eliminates the candidates that the normal logic cannot eliminate, even they are wrong eliminations.

To-do list:

• Basic checks (target).
• X-Rule (Bi-Bi pattern).
• Mirror checking.

Chains are usually powerful, but slow, which is the reason why I write (or re-write) code for chains and forcing chains. To be honest, I am not familiar with the algorithm to processing (forcing) chains / dynamic (forcing) chains, the previous version of chaining algorithm is implemented by me without any references or copying. Unfortunately, Hodoku is to hard to understand the processing logic for chains because of TOO LARGE.
I will write them later, thanks for your patience.

The region rendering are almost white :(

Sometimes, I find that some puzzle will use several minutes to solve, which makes me sad :(
I want to optimize the algorithm for searching ALSes!!!

To-do list:

• ALS searcher and RCC searcher
• ALS-XZ rule
• ALS-XY-Wing
• ALS-W-Wing
• Empty Rectangle Intersection Pair (Do not consider on this technique)
• Death Blossom (Do not consider)

Hobiwan's fish is an extremely and main sudoku technique, aiming for a single digit. However, with the size larger of each fish, the complexity of searching for fishes will be larger. Using Hodoku, the program provides us with UI for searching for fishes. For example, Hodoku provides the option "searching one fish for each elimination (candidate)" to accelerate the running.
I think that my algorithm of searching for them has not been optimized yet. For example, we can use a faster searcher to gather all single-digit eliminations, then check whether the cover sets found contains these eliminations. If not, skip the loop to find another one.

Consider the code:

abstract record R { public override string ToString() { ... } }

record S : R;

S instance cannot output correctly.

Some nightmare techniques are useful and powerful but rare. I think they are important.

To-do list:

• Exocets
  • Junior Exocets
  • Senior Exocets
  • Complex Senior Exocets (with new region, i.e. Franken/Mutant SEs)
  • Siamese Exocets (JE4)
• Multi-sector Locked Sets
  • SdC
  • 3D SdC
  • Domino Chain
  • Stephen Kurzhal's Loop (Domino Loop)
  • Normal
• Complex Fishes
  • Franken Fishes
  • Mutant Fishes
  • Kraken Fishes
    • Kraken Fish Type 1 (Fish + AICs).
    • Kraken Fish Type 2 (Fish + Forcing Chains).
• Complex Deadly Patterns
  • Reverse Patterns
    • Reverse Extended Rectangle
    • Reverse Unique Rectangle / Loops
  • Other Deadly Patterns
    • Extended Rectangle
    • Unique Loop
    • Borescoper's Deadly Pattern
    • Qiu's Deadly Pattern
    • Unique Square
    • Complex patterns, e.g. Unique Loop + Extended Rectangle

The speed of AICs and CNLs will be so slow because the algorithm does not use any cache to process or save the strong or weak relations (strong or weak links). In addition, the algorithm can be replaced with BFS, which reduces some unnecessary backtracking.
If using BFS, the searching will be faster than DFS, or use same time with DFS used.

This issue lists all operations that should finish.

• Apply C# 9 features:
  • Records:
    • Change into records syntax.
    • init setters on class properties and read-only structs.
    • C# 9 Preview: Add class IsExternalInit manually.
    • Apply in modifier on some structs.
  • Top-level Main method.
  • Pattern matching Version 3 (and, or and not patterns).
  • Native integers (nint and nuint).
  • Function pointers.
  • SkipLocalsInitAttribute: Ignores initializations on locals.
  • Target-typed new.
  • static anonymous functions (lambdas).
  • Target-typed condition expressions.
  • Co-variant returns.
  • Extension GetEnumerator.
  • Lambda discards.
  • Attributes on local functions.
  • ModuleInitializerAttribute.
  • Extending partial methods to all valid methods if need.
• Apply C# 8+ features:
  • Unconstrainted nullable generic type: T?.
• Apply project file:
  • <TargetFramework>net5.0</Targetframework>.
  • WPF project: <TargetPlatformIdentifier>Windows</TargetPlatformIdentifier>.
• Fix bugs raised after upgrading to .NET 5.

The previous issues are here: #3 #5 #14 .

To-dos:

• Alternating Inference Chains / Loops
• Grouped Alternating Inference Chains / Loops
  • + Locked Candidates
  • + Almost Locked Subsets
  • + Almost Unique Rectagles
  • ...
• Forcing Chains
  • Cell Forcing Chains
  • Region Forcing Chains
• Dynamic Chains / Loops
  • Dynamic Alternating Inference Chains / Loops (Too slow, not considered)
  • Dynamic Grouped Alternating Inference Chains / Loops (Too slow, not considered)
  • Dynamic Forcing Chains

Sometimes UR type 5 removes some wrong candidates.

To-do list:

• Fix issue (#6)
• Re-write UR/AR type 5.

Is your feature request related to a problem? Please describe.
Hidden Rectangles always eliminates some candidates that UR type 4 eliminates, which makes the UR type 4 after this instance uncompleted, even if the technique is not an error.

Describe the solution you'd like
UR type 1 to 6 first, and then search for Hidden Rectangles.

To-do list:

• Fix issue (#6).
• Sort all UR/AR instance by the specified sort key (type code).