help

Programs which generate, solve, and analyze Sudoku puzzles

help

Postby StrmCkr » Thu Apr 13, 2017 5:58 pm

i'm trying to build a chain walking algorithm to implement Nice-loops{discontinuous,continuous}, Aic chains,

currently I'm stuck at is how to build the initial tree {i've never built or used search trees before so this is new to me. }

this is how i see it working:

build a list of all viable non solved cells, from a grid

cell[0-80]
for each of these cells
we have: Digits [1-9]

which are found in 1 of three sector options:
Sector: Row,Col,Box [27

which can contain

Peer digit cells of the selected cell and digit as:

Strong link:
bivalve cell
only 2 positions for R,C,B {naked}
only 2 R,C,B position in Sector {hidden}
=>>
save Cell position

Empty Rectangle intersection:
all the cells of Box Sector are found only on an intersecting Mini Row & Mini Col within a box,
where Mini Row or Mini Col do not hold all cells with in box sector.
=>>
Save intersection [miniRow * MiniCol ] cell.

note: not sure if there is a "hidden" version of an ERI as I've never considered that option before

Weak-Link:
starting cell see all except 1 cell in a R,C,B {naked}
Starting cell see's all except 1 R,C,B position in Sector {hidden}
=>> Save intersection of starting Cells sector and sector of weak link
{gives a grouped node on, row,col,box}


which generates:

cells[0..80]
digits [1..9]
Sector(Row,Col,Box) [0..2]
Link( Strong, Weak, ERI) [0..2]

for each Link cell saved we create a child that searches and saves identical as the above , {noting that it cannot reuse already saved data points on that tree branch}

start:
digit 1
Col
sector 2
Link cell 9
makes a new tree {showing how cell 9 is linked to other digits}


is this correct?
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 627
Joined: 05 September 2006

Re: help

Postby JasonLion » Fri Apr 14, 2017 1:10 am

There are many ways to approach this problem, who is to say which is "correct". What you describe sounds plausible, though it is somewhat different from what I do.

The way I approach this problem is to make a list of everything that could be a strong link in a chain and then iterate through every possible valid way of combining those links into chains, checking to see if any of the discovered chains result in an elimination.

Empty Rectangle is a special case of grouped links. I suggest looking at the more general case, rather than just the special case.

Allowing ALS to be links in the chain greatly expands the power of this approach. More generally, nearly every known solving technique can be used as a link in a chain if you restate them slightly.
User avatar
JasonLion
2017 Supporter
 
Posts: 621
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: help

Postby StrmCkr » Fri Apr 14, 2017 5:07 pm

thanks jason,
i am considering adding: locked sets{hidden,naked, and Almost locked sets {hidden,naked} as expansion options
moreover I'll need get the basics covered before i add to it.

grouped weak links are covered as outlined.
Code: Select all
|. A . | . . . | . . .     <= {starting point}
|A A  A| / / / | / A / 
mini Row in box {weak to starting point}     =====  strong linked to group node on Row


grouped strong links are missed {as suggested}
Code: Select all
|. A . |. . . | . . .     <= {starting point}
|A A  A| / / / | A A A 
mini Row in box {weak to starting point}     ===== Grouped strong linked to group node on Row
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 627
Joined: 05 September 2006


Return to Software

cron