The New Sudoku Players' Forum

[MAGREMENT]

Hey everyone !

I fairly recently started a new programming project which was a Sudoku solver. I learnt about Sudoku's and the different strategies to solve them during the same time period. I took great inspiration in Andrew Stuart's online solver (https://www.sudokuwiki.org) and when I finished implementing every strategy referenced there, I started coming here. Sadly, due to my lack of experience, I find it very hard to find documentation on strategies that are easy to understand and implement. Also, my solver has gone quite a long way so I wanted to share it. Please, keep in mind the project is still work in progress and there are quite a few area lacking.

Here is the github repository : https://github.com/MAGREMENT/SudokuSolver

Everything is written in c# in dotnet 6.0 with the help of WPF.

Here is the full list of strategies implemented :

Naked Single
Hidden Single
Naked Doubles
Hidden Doubles
Box-Line Reduction
Pointing Set
Naked Triple
Hidden Triple
Naked Quad
Hidden Quad
Gurth's Theorem
X-Wing
XY-Wing
XYZ-Wing
Swordfish
Jellyfish
Simple Coloring
BUG
Reverse BUG
Junior Exocet
Finned X-Wing
Finned Swordfish
Finned Jellyfish
Fireworks
SK-Loops
Unique Rectangles
Avoidable Rectangles
XY-Chain
3D Medusa
WXYZ-Wing
Sue-De-Coq
Aligned Pair Exclusion
Aligned Triple Exclusion
X-Cycles
Almost Hidden Sets
Almost Locked Sets
Death Blossom
Alternating Inference Chain
Set Equivalence
Digit Forcing Net
Cell Forcing Net
Unit Forcing Net
Nishio Forcing Net
Pattern Overlay
Brute Force

I'd really appreciate it if anyone could relay to me any bugs they found while using the solver or give me links and/or explanation on strategies I've not yet or only partially implemented.

Also note that english isn't my first language so sorry if there are grammar errors.

[MAGREMENT]

My post took a bit of time to get approved so I've had the time to work on my solver a bit since then.

I've added a first incomplete implementation of BUG-Lite.

Going to work on more complex BUG-Lite/UR-Chain patterns and whips/nrczt-chains

For people without developper tools wanting to test the project, go to the github page poster above and click on the latest release (should be on the column on the right). Then download the
SudokuSolver.exe and strategies.ini files, put them in the same folder and start the executable

It should work on windows, not sur for Linux/MacOS tho.

[creint]

It's pretty fast.
Hardcoded to 9x9 sudoku.
Without pasting pencilmarks it is hard to provide examples of which things are missing. Supporting hodoku like paste format would help.
A scan all function could help debug strategies.
Sudokuwiki has not documented every possible edge case. And has only documented known common strategies.
If you can implement one generic strategy than you only have to name the patterns. (Take a look at Xsudo.)

[MAGREMENT]

Thanks for your feedback creint !

Hardcoded to 9x9 sudoku.

Yes I plan to concentrate only on basic Sudoku's for now as there is already a lot to cover

Without pasting pencilmarks it is hard to provide examples of which things are missing. Supporting hodoku like paste format would help.

I can try implementing that

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 ?

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 can implement one generic strategy than you only have to name the patterns. (Take a look at Xsudo.)

This is not something I'm that interseted in right now, but I might try later on

[StrmCkr]

FYI Andrew stewards ScanRaid is compltly coded as niceloops and misses many things as it tries to act like aic which it cannot do, errors in his aic code are frequent as the chains don't line up to aic normal output
His code also only returns the first object found, instead of all or the best option.

All niceloop techniques are archaic and no longer used.

Which includes colouring, simple colouring, 3d Medusa
As all the elims are included under aic which is always shorter.

Ape and ate evolved into als thus no longer used

Bomans is a forcing chain depth based for contradictions as a 2 digit tempalte
Not used

Nisho single digit forcing chain looking for a contradiction ie 1 digit templating
Not used.

Foching chains pretty much a last resort

I'd add
Als xz, als xy, als chain and include the n rcc rule (2 fo als xz, 3 for als xy, where n = chain length)
3rcc is missing in scanraid

Xy, xyz, wxyz, wings& rings all the way up 8 cells with 9 digits (adding a character for each digit)
are classed under bent almost restricted set (barns)

which is specialized als xz functions of n digits in n cells over 2 sets.
2rcc is usable for these this is ommited in ScanRaid.

Next I'd scale up and add in disjointed distributed subsets (dds
This is where Sue de coqs, ànd death blossoms fall under and scale beyond 3 sectors
Coded as als with dof size 1-8

Almost DDS is possible as well.
Chaining DDs is possible, with my newly added rules.

Aals 2rcc mutual elimination fails under DDs but can be coded as is own

X-cycles dead technique evolved into aic x chains as x-cycles are niceloop based.
ScanRaid still tries to use this to replicate aic... Err.

X-chains are single digit aic
Short named techniques for these are ommited by scanraid

Xwing
Finned xwing
Sashimi x wing

Skyscraper

2 String kite
Grouped 2 string kite

Empty rectangle
Rec'k kite
Dual er
Linked dual er

Swordfish + Sashimi +finned
Jellyfish +Sashimi +finned

Nx Eri

Siamese fish (1 fish more then 1 set of cover option for extra elims)

All of these can be expanded as muti fish (2 or more digits 1 fish)

Nxn (standard fish rules using fins)
Nxn+k fish size 1-7, where k=1-2 and beyond depending on how u code)

Ahs xz
Ahs xy
Ahs chain
Ahs DDS, ahs adds

Xy chain
Hidden xy chain
Remote pair
Remote pair with eri
Hidden remote pair

Aic chain
Aic +als
Aic+ ahs
Aic+als+ahs
Aic+fish
Aic+als+fish
Aic+ahs+fish
Aic +fish+als+ahs

Alc - sos ie fireworks but not specific.

Alc pair, tripple, quad

Named aic chains
W wing/ring
Split wing/ring
M2 wing/ring
M3 wing/ring
Hybrid wing/ring , H wings types 4-6
Local (123) wing/ring
Inverted w wing/ring
Strong wing/ring

Muti-fish
SK loop nKed
Sk loop hidden
Msls older and is easier to use the sets!

Thors hammer
Exceots Jr, sr

Uniqueness arguments
Bug
Bug+n
Bug lite

Rêverse bug
Reverse. Bug lite

Mug
Mug+n
Pug
Ucc

UR types 1-7
Aur any Ur type exposed via any chain.

Avoidable rectangles types 1-2
Hidden rectangle types 1-2

NAMED MOVES AGAIN

Transport als xz (ADDS 1 STRONG LINK)
Transport als xy (ADDS 1 STRONG LINK)

Hybrid als xz, (ADD 1 CELL)
Hybrid als xy (ADD 1 CELL)

(THE FOLLOWING ECPANDS THE NAME MOVE TO LARGER ALS)
Als w wing/RING.
Als s wing/ring
Als M wing/rinG

Ahs M wing/ring
AHS W WING/RING
AHS S WING/RING


Subset notes
Subsets can be degenerative, scan raid dosent do this.
Subsets should be able to turn on or off.
Hidden subs are found first by human players as we use Rn, Cn, Bn space naturally with no pms
Naked are seen first by machine code due to rc space as a union of rn, Cn, Bn space per square.
Naked pair/hidden pair when found in a box on 1 sector are named locked pairs
Naked tripple/hidden tripple when found in a box on 1 sector are named locked tripples

Blr has 2 types and is also a size 1 fish some times called locked candidates or pointing canddiates

Ps.
Avoid ScanRaids a-j, 1-9 and use standard rc notation
Pls use Aic written language Eureka
ScanRaid still uses niceloop output pain to read.

A full list of every technique I know
https://reddit.com/r/sudoku/w/techniques?utm_medium=android_app&utm_source=share

I'm also presently developing a full Gui in Java with the master list as techniques
if your interested, its à rebuild of my pascal solver

The more helpers I have the easier it will be to launch this hodoku inspired rebuild


Reviewing your code
Your missing
RC, Rn, Cn, Bn space

which is key for setting up subsets, aic strong links, and fishing, als sets, ahs sets. Etc

Most of your code cycles the grid and builds the stuff thèses 4 spaces sets up. So 8t could be much faster then it currently is



anything als and ahs

[yzfwsf]

Unfortunately, after installing the 6.0.25 runtime, I was unable to run the program on my Dell laptop. After the cursor circled for a while, nothing happened.

Processor 12th Gen Intel (R) Core (TM) i5-1240P 1.70 GHz
Machine with RAM 16.0 GB (15.7 GB available)
System type 64 bit operating system, based on x64 processor

[MAGREMENT]

Hey all !

I'd really to reply to you all faster but my posts take days to get approved and it's quite inconvenient.

Is there a way to avoid that ?

Edit : its fine now

[MAGREMENT]

FYI Andrew stewards ScanRaid is compltly coded as niceloops and misses many things as it tries to act like aic which it cannot do, errors in his aic code are frequent as the chains don't line up to aic normal output
His code also only returns the first object found, instead of all or the best option.

I might look stupid for this but I'll ask it anyway as you use it a lot, what is a "SacnRaid".
Also I know that AS solver is not perferct, that's why I didn't reproduce it 1 to 1 and I now come here way more often. It was just a good introduction into the Sudoku world for a complete beginner like me.
As for only return the first object found, I actually made that an option in my solver ! You need to go the Settings and change "On instance found" :
-> Return = return the first one
-> Wait for all = will apply all instance found in order
-> Choose best -> will choose the best instance
-> Default -> default for each strategy
-> Customized -> You can customize this in the strategies.ini file

For all the strategies not used, I know. I don't want my solver to only have the top, super generalized strategies. I intended my project to be more of a "strategy library" (even old ones) and let anyone choose which one they want to use.

The strategy list and the reddit links are very useful though, so thanks for that ! (Even if i've already added some)

Skyscraper

Are Skyscraper's different than Finned-fishs ?

Next I'd scale up and add in disjointed distributed subsets (dds

I've never heard of that, do you have any link ?

Avoid ScanRaids a-j, 1-9 and use standard rc notation
Pls use Aic written language Eureka

Yeah taht part is a bit lacking in my solver I'll admit, I have to work on it

Reviewing your code
Your missing
RC, Rn, Cn, Bn space

What do you mean by this ? how do you implement it ?

[MAGREMENT]

I'm also presently developing a full Gui in Java with the master list as techniques
if your interested, its à rebuild of my pascal solver

The more helpers I have the easier it will be to launch this hodoku inspired rebuild

I'm more focused on my solver foor now but I'll gladly help. Do you want my contact infos ?

[MAGREMENT]

Unfortunately, after installing the 6.0.25 runtime, I was unable to run the program on my Dell laptop. After the cursor circled for a while, nothing happened.

Processor 12th Gen Intel (R) Core (TM) i5-1240P 1.70 GHz
Machine with RAM 16.0 GB (15.7 GB available)
System type 64 bit operating system, based on x64 processor

That is weird. There is only 3 things I believe would do that, either :
-You're not on windows, which I highly doubt as you're on a Dell
-Your antivirus is blocking the application because it is from an unkown editor
-The program doesn't find the strategies.ini files, which makes it crash. This is much more likely and I should probably change that

Anyways you shouldn't even have to install dotnet 6.0 if you use the executable in the release section on github. I've already posted how to do this in a previous comment but it has not been approved yet.

I'll repeat for convenience :
First, go to the Github page. Then, in the release section (supposedly in the right column), click on "latest realease". You now just need to download the SudokuSolver.exe and strategies.ini files and put them in the same folder.

I've just test this method on my sister pc, which doesn't have any developpers tools and it works. Contact me again if it doesn't work even after this

[urhegyi]

Unfortunately, after installing the 6.0.25 runtime, I was unable to run the program on my Dell laptop. After the cursor circled for a while, nothing happened.

Processor 12th Gen Intel (R) Core (TM) i5-1240P 1.70 GHz
Machine with RAM 16.0 GB (15.7 GB available)
System type 64 bit operating system, based on x64 processor

The exe Runtime was not enough to run, after I copied the .ini file too it was working nice.

[yzfwsf]

Hi urhegyi：
Thank you for providing the solution, It runs normally.

YZF

[MAGREMENT]

Hi !

Version v1.0.2 is out !

Strategies added :
-Rectangle Elimination (from Andrew Stuart Solver)
-NRC(Z)(T)-Chains (will probably try to improve their implementation later)

Functionalities added :
-Copy / Paste grid (In the edit tab)
-A Full scan of the grid for every elimination/solution proposed by each strategy (In the tools tab)
-A way to see all strategies implemented for now to make modifying the .ini file easier (In the tools tab also)

Github : https://github.com/MAGREMENT/SudokuSolver

[StrmCkr]

Google ScanRaid it will redirect you to sudoku wiki

when sudoku wiki domain lapsed and came up for grabs Andrew steward took the opertunity to rebrand his website to draw more attention to it by taking the more popular search terms.

Skyscraper is two Sashimi X-wings, as both strong links qualify as missing canddiates
Àn example of

(1)R1c1=r1c5 - r6c5=r6c3
=> r23c3, r45c1<> 1


Rc space is the 81 cells of a grid

Rn stores on positions for each digit listing cols
Cn stores on positions for each digit listing rows
Bn stores on position for each digit listing square

Squares are stored per box as this listing
123
456
789

Pencilmarks for RC space is the union of digits 1-9 active in Rn*Bn*Cn space

So to find a hidden subset for example we'd call
Rn space for a powerset(size 2) and match it to rn space for the 2 digits of the power set
À match has only 2 cols left.
Repeat for Cn, Bn space.

Which means subsets are actually x wings.(thats a hint)

Fair point wanting mutiple techniques if your doing that utilize the niceloop Notation for niceloop techniques
and eureka for aic based techniques , adds another layer of complexity and might cause issues for users not savvy in both.

Its also going to double your search space storage methods as niceloops use cellular Atama for bivavle bilocal plotting

Were aic use digits of mini sector to mini sector.

Stronglinks nomiclature is vastly diffrent between the two
Niceloops use cell to cell relation ships so a or b can be true but not both
And each part is an individual weaklink

Aic stronglink is a XOR logic gate of (a &! A) or( b &! B) where ! A=B &! B =A
As a singular structure.

aic use weakinferences between nodes so that 2 position edges canot be true at the same time
nice loops weaklinks is every cell is a weaklink (is true ôr it's not)
and strong links can substitute a weaklink, as it's comprised of two weaklinks.

The diffrence is the breaking point for niceloops to replicate aic,
as they start and end on eliminations (contradictions) so it's the ommishion of start and end links yields the internal aic.

They replicate aic directly when the loop asserts its self as true, again it has extra links compared to aic

DDS I'll grab a link for this later today, I should have direct links to it in my solver page which is in my tag if you beat me to it.
http://forum.enjoysudoku.com/distributed-disjoint-subsets-t5423.html

Ps eri concepts for empty rectangle are from me since you referenced it. The majority of topic was lost in the crash.

It goes beyond what he talks about

Nx Eri are applicable

dual eri with grouped strong links is applicable for a rect kite (think empty rectangle +two string kite) as a entry level example.

Pss the approval post is set to around 5~ to help stop bots pain but worth it compared to the bot wars that plagued crashed our original forum back in 2008~

My project Gui Java I'll dm you the info if you want to add to it or learn from it either way.

[MAGREMENT]

Rc space is the 81 cells of a grid

Rn stores on positions for each digit listing cols
Cn stores on positions for each digit listing rows
Bn stores on position for each digit listing square

Squares are stored per box as this listing
123
456
789

Oh then my solver does store these spaces actually

I'm sorry but you totally lost me on the AIC vs Nice Loops part. I guess there is quite an experience gap between the two of us.

Ps eri concepts for empty rectangle are from me since you referenced it. The majority of topic was lost in the crash.

That's quite sad. Is there still documentation somewhere ?