SE rating for overlapping Sudoku puzzles - suggestion

Programs which generate, solve, and analyze Sudoku puzzles

SE rating for overlapping Sudoku puzzles - suggestion

Postby Hajime » Tue Sep 10, 2019 12:58 pm

In the thread of Tarak about "Revision of SE ratings and resolution rules" a new rating system is born for single Sudoku's and Sakaku's.
I would like to suggest a method for SE rating for overlapping Sudoku's, like Twins, Samurai, Kazaguruma etc.
Upwards compatible with the new SE rating for singles, and based on the Pythagoras length in n-dimensions.
So it leads always to a rating (slightly) higher then the maximum of each individual SE.

A Twin consists of 2 Sudoku's, each with a SE rating, say 3.0 en 4.0 eg.
The SE rating of the Twin is based on sqrt(sqr(3.0)+sqr(4.0))=5.0 but that is too high (says my feeling).

So make it a bit more difficult... The SE ratings starts at 1.0 and not 0.0 . Subtract 1.0 from the SE values and add 1.0 at the end.
Now the SE rating for a Twin is sqrt(sqr(3.0-1.0)+sqr(4.0-1.0)) + 1.0 = 4.61
Better but still too high... Especially when considering a Samurai with 5 Sudoku's.
Eg let each Sudoku have 3.0 rating then the Samurai ends up with a rating sqrt(5 * sqr(3.0-1.0))+1.0 = 5.47. That's almost double.

One step further : divide the sum of sqr's with sqrt(n), where n is the number of Sudoku's (Pythagoras dimensions).
That leads to sqrt(5 * sqr(3.0-1.0)/sqrt(5))+1.0= 3.99 . Acceptable?

In general the formula would be:
SE puzzle = sqrt([sum of sqr(each single SE - 1.0)]/sqrt(n))+1.0, where n is the number of Sudoku's in the puzzle

Is this something (or another can of worms)?
User avatar
Hajime
 
Posts: 83
Joined: 20 April 2018
Location: Netherlands

Re: SE rating for overlapping Sudoku puzzles - suggestion

Postby creint » Tue Sep 10, 2019 5:48 pm

My suggestion is see it as one whole puzzle instead of single puzzles.
If you don't do that you can miss some tactics that uses both puzzles at the same time.
The only thing you can do is adjust the rating based on how visible the logic is, but that is more a player rating than a solver rating. Player rating is harder to define.

Another problem with rating is still the ordering of tactics. Sometimes you need only 1 pointing/claiming but if you can find four others before you find the one that solves it with singles.
Rating could be lowest score required to solve.
On larger variants, the same tactic is harder to find so this should affect player rating.
And requiring the same tactic should increase the rating. If n tactics has same rating as m other tacics in the same puzzle, which one will have an easier solving path in the end? You can't do that in one single solve/is many times slower than normal solving. Highest rating/first placement rating/first exclusion rating is not enough to determine total difficulty.
Even a 49x49 variant with singles only is hard for manual solvers without assistance, so cellcount could adjust the player rating.
creint
 
Posts: 122
Joined: 20 January 2018

Re: SE rating for overlapping Sudoku puzzles - suggestion

Postby tarek » Thu Sep 12, 2019 6:34 am

It all depends on puzzle design.

If each subgrid is closed (info needed to solve subgrid are within the subgrid) then having a rating system that combines separate ratings for each subgrid is logical.

The fact is that many gattai puzzles can't be solved like that and should be considered as 1 huge puzzle making rating subgrids individually more difficult

tarek
User avatar
tarek
 
Posts: 3145
Joined: 05 January 2006

Re: SE rating for overlapping Sudoku puzzles - suggestion

Postby 1to9only » Fri Sep 13, 2019 10:27 am

Many months ago (about the time I did the sukaku changes!), I spent a little time trying to get SE to solve a samurai - I got as far as reading the 5 grids, and did not get to start the solving loop! No further work was done.

[Essentially, each sudoku (1-5) is passed (as a sukaku) to SE to solve (as far as possible), and (re)cycling through 1-5 until the samurai is solved.]

The intention was to produce an SE rating for each sudoku, e.g. (numbers below are made up!)
Code: Select all
sudoku1 ED=5.4/2.0/1.5 <- hidden quad
sudoku2 ED=1.5/1.5/1.5 <- hidden single
sudoku3 ED=5.2/2.3/1.2 <- jellyfish
sudoku4 ED=3.0/2.0/2.0 <- naked pair
sudoku5 ED=3.2/2.3/2.3 <- x-wing

To give the samurai a rating of:
Code: Select all
samurai ED=5.4/1.5/1.2

The overall rating indicating the most difficult SE technique needed to solve.
.
1to9only
 
Posts: 1187
Joined: 04 April 2018

Re: SE rating for overlapping Sudoku puzzles - suggestion

Postby Hajime » Fri Sep 13, 2019 3:23 pm

Exactly what I meant, 1to9only. Only the total rating is not the max of all subgrid ratings, but the formula, because it is a bit more difficult.
User avatar
Hajime
 
Posts: 83
Joined: 20 April 2018
Location: Netherlands

Re: SE rating for overlapping Sudoku puzzles - suggestion

Postby tarek » Fri Sep 13, 2019 6:07 pm

Can I see if I got it correct?

Code: Select all
Samurai grids: 1-5
Rating{ X to X + number of rules (for the sake of understanding)]

Rating = X
:Top
Check if Grids solved (1-5)
if Grid is solved and Grid has no rating then Grid rating = Rating
If All grids solved then Overall rating = Average Grid
   rating (or other like top rating), Exit
Rating = X
:Start
if (Rating > X + number of rules) and grid unsolved then Grid rating = 200
   Overall Rating is "Unsolvable", Exit after checking all grids
Attempt solve EACH grid with Rule equal to Rating
If any grid advances goto Top.
Rating = Rating + 1
goto Start


What is new in the above is knowing the highest rating for each grid
There is a Grid selection bias which can be reduced by applying all moves with same rating to all grids.
There is always a chance of missing an easier technique that spans more than one grid and therefore over rate some grids or even over rate the entire puzzle
User avatar
tarek
 
Posts: 3145
Joined: 05 January 2006

Re: SE rating for overlapping Sudoku puzzles - suggestion

Postby m_b_metcalf » Sun Sep 15, 2019 12:52 pm

tarek wrote:It all depends on puzzle design.

If each subgrid is closed (info needed to solve subgrid are within the subgrid) then having a rating system that combines separate ratings for each subgrid is logical.

The fact is that many gattai puzzles can't be solved like that and should be considered as 1 huge puzzle making rating subgrids individually more difficult


Quite. Many moons ago, here, I noted that the coupling between the five puzzles of a samurai can fall into three classes:

    none: the five individual puzzles can each be solved without reference to one another;

    weak: at least one puzzle can be solved only by sharing solved clues with a neighbouring puzzle;

    strong: at least one puzzle can be solved only by sharing pencil marks with a neighbouring puzzle.
In my opinion, any samurai puzzle worthy of the name should have strong coupling.

But, in fact, there are some very difficult puzzles that cannot be solved just by cycling around the five constituent puzzles, and that has to taken into account in any rating scheme. For these, one needs a 21x21 solver of some sort (SAT?), or good guessing.

The hardest samurai I know of is from ruud's collection (source forgotten):
Code: Select all
..9.7..8....6...2.6.5.4.....6.5.3...8.1.....7...8..9.4.....4...95...........65... TL   
8.9....1.....4...8..1.62....2.5..43.37..8.........6.........3.5...6.3.......7.8.. TR
.............1........6..........5.1.62..5.......9..32...4..........1......3.2... M 
6...4.......57....2.7.........8...4..73.9...2..6..5.9....3..5.91..6......8....2.. BL 
...7...4......2.9....5....37.2.6.......37.....9....35......4..628...3.....1...5.. BR


and the hardest x-samurai I know of is ruud's Ronin:
Code: Select all
.1.6.8....9..3...........2...5...........6...4.83.7.....................9..8.4... TL
...3.8.9.....1..3..4.............7.....4........7.28.1.....................2.3..5 TR
....7.......................61...72...........28...35.......................9.... M
9..5.4.....................5.18.2........7.....7.............6..5..6.....7.3.9... BL 'Ronin', an
...1.6..7.....................9.27.3...3...........4...1...........9..2....6.5.3. BR X-samurai from ruud

How to rate these?

Regards,

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10250
Joined: 15 May 2006
Location: Berlin

Re: SE rating for overlapping Sudoku puzzles - suggestion

Postby tarek » Mon Sep 16, 2019 10:47 am

1to9only wrote:Many months ago (about the time I did the sukaku changes!), I spent a little time trying to get SE to solve a samurai - I got as far as reading the 5 grids, and did not get to start the solving loop! No further work was done

Any work done like this can be done on a branch or fork from the current project on sukaku explainer. You can do it in your own time or allow others to add/modify from the nucleus of work that you've done. The work will remain there for people to continue later if your circumstances do not allow further development. I hope that lksudoku knows that his work which was done years ago and saved in a repository that was nearly forgotten has now been integrated in our project so that others may enjoy it.

tarek
User avatar
tarek
 
Posts: 3145
Joined: 05 January 2006

Re: SE rating for overlapping Sudoku puzzles - suggestion

Postby 1to9only » Mon Sep 16, 2019 11:13 am

The SE samurai solver code is incomplete: copy serate.java to samurai.java, modify to read 5 sudokus, generate 5 sukakus accounting for overlapped nonets, project stalled - because it is a samurai solver (only). :idea: An SE gattai solver would be better... Don't think I've given this much thought since...
1to9only
 
Posts: 1187
Joined: 04 April 2018

Re: SE rating for overlapping Sudoku puzzles - suggestion

Postby tarek » Mon Sep 16, 2019 11:58 am

1to9only wrote:The SE samurai solver code is incomplete: copy serate.java to samurai.java, modify to read 5 sudokus, generate 5 sukakus accounting for overlapped nonets, project stalled - because it is a samurai solver (only). :idea: An SE gattai solver would be better... Don't think I've given this much thought since...

I can see at least if we are targeting each subgrid for this method of rating that a template of the gattai will be needed for each type of gattai but the engine would work the same way for all of them
User avatar
tarek
 
Posts: 3145
Joined: 05 January 2006

Re: SE rating for overlapping Sudoku puzzles - suggestion

Postby Hajime » Mon Sep 16, 2019 4:02 pm

I have a suggestion how to determine overall ed for subgrids in an overlapping puzzle
I think it is consistent with tarek 's code
and, yes, you need a 21x21 grid for samurai and 33x33 for sumo etc. as m_b_metcalf stated
Hidden Text: Show
Code: Select all
initialize //load puzzle in large grid and gridcandidates in another large grid ...
             //large grid: 21x21 for a samurai or 33x33 for a sumo, etc.
             //inclusive array glocx and glocy of topleft position of subgrids in large grid
ecc = 0 //eliminated candidates counter
n=-1
for i=1 to grid_count: g_ed(i)=0 next 'ed value per subgrid
while n<ecc do
   n=ecc
   for m=1 to methods_count //24...
      for g=1 to grid_count
         try_eliminate(m, g)
      next
      if n<ecc then exit for m
      // if some method is succesvol eliminating candidates, start all over again with method 1
   next
loop
ed = some formula to determine ed from array g_ed(g) for g=1 to grid_count
if allcellsfilled then
  message "a solution found with ed=" & ed
else
  message "no solution found with available methods"
end if

done

sub try_eliminate( m, g)
 case m of
  1: try_ns (g, 1.0) //naked singles
  2: try_hs_block (g, 1.2) //hidden singles in block
  3: try_hs_rc( g, 1.5) //hidden singles in row or column
  .
  .
  12: try_xwing( g, 3.2) //X_wing
  .
  .
  24: try_dfc_plus(g, 9.0) //dynamic forcing chains plus
  // no method for brute force
end case
end sub

sub try_ns (g, v)
//find naked singles; g=subgrid_nr; v=value of this method
  for i=0 to 8 do
  for j=0 to 8 do
    x=glocx(g) + i
    y=glocy(g) + j
    if grid( x,y) = 0 then //empty cell
      if length(gridcandidates(x,y))=1 then //naked candidate
         grid(x,y)=gridcandidates(x,y)
         gridcandidates(x,y)="" // candidate erased
         ecc=ecc+1
         if g_ed(g)<v then g_ed(g)=v //upgrade ed value per method for subgrid g
      end if
   end if
  next
  next
end sub
User avatar
Hajime
 
Posts: 83
Joined: 20 April 2018
Location: Netherlands

Re: SE rating for overlapping Sudoku puzzles - suggestion

Postby 1to9only » Sun Oct 27, 2019 12:30 pm

1to9only wrote:Many months ago (about the time I did the sukaku changes!), I spent a little time trying to get SE to solve a samurai

I've revisited my SamuraiExplainer and made a little progress!
I'm testing using Ruud's 1st samurai posted here - This is Samurai number 1 for Tuesday November 21, 2006, rated Hard.
Code: Select all
6...4.9...3...95....9....13...8...3.4...9...7.1...5...54.........15.......8.7....
.......16.41.7...5.8...39.....5..4...3..1..6...2..8......6...8.....4.69..........
....7.......3..........2....5....9..2...8...7..6....4....1..........9.......3....
4..26..................7...8...1.2..9..4.2..3..7.5...4.5.3......62..........21..5
...31..78........9...6.51..4.6...8..3...6...2..9...4.7..74.9...8........95..28...

This is the rating after one pass through the 5 grids:
Code: Select all
6...4.9..134.895..8.9.5.413...81..3.48..9.157.1...5...547.....1..15..7....8.7...5 ED=9.0/1.2/1.2
.......16.41.7...5.8.1.39.....5..4...3..1..6...2..8......6...8.....4.69.......... ED=2.6/1.2/1.2
....7.......3.......58.2....5....9..2...8...7..6....4..3.1..........9.......3.... ED=10.5/1.2/1.2
4.126..................7...8...1.2..91.4.2..3..7.5...4.5.3......62..........21..5 ED=8.3/2.3/2.3
694312578135847629782695134426971853378564912519283467267459381841736295953128746 ED=4.2/1.2/1.2

The overlapping nonets are not processed, so connected grids are not affected! - this is to be looked at next.
.
1to9only
 
Posts: 1187
Joined: 04 April 2018

Re: SE rating for overlapping Sudoku puzzles - suggestion

Postby 1to9only » Tue Oct 29, 2019 11:06 am

1to9only wrote:I'm testing using Ruud's 1st samurai posted here - This is Samurai number 1 for Tuesday November 21, 2006, rated Hard.

The Ruud Samurai number 1 puzzle is rated as below:
Code: Select all
6...4.9...3...95....9....13...8...3.4...9...7.1...5...54.........15.......8.7.... ED=4.0/1.2/1.2
.......16.41.7...5.8...39.....5..4...3..1..6...2..8......6...8.....4.69.......... ED=2.6/1.2/1.2
....7.......3..........2....5....9..2...8...7..6....4....1..........9.......3.... ED=3.4/1.2/1.2
4..26..................7...8...1.2..9..4.2..3..7.5...4.5.3......62..........21..5 ED=3.6/2.3/2.3
...31..78........9...6.51..4.6...8..3...6...2..9...4.7..74.9...8........95..28... ED=2.0/1.2/1.2
ED=4.0/1.2/1.2
675143982134289576829657413752814639486392157913765248547936821391528764268471395
923854716641279835785163942197536428834712569562498371359627184218345697476981253
821674359764395218395812476158467923243981567976253841537128694682749135419536782
481269537579134682623587419845913276916472853237658194758346921162795348394821765
694312578135847629782695134426971853378564912519283467267459381841736295953128746
Solved.

m_b_metcalf's earlier post of another of Ruud's hardest samurai is not solvable using existing SE solving techniques:
Code: Select all
..9.7..8....6...2.6.5.4.....6.5.3...8.1.....7...8..9.4.....4...95...........65... ED=3.4/1.2/1.2
8.9....1.....4...8..1.62....2.5..43.37..8.........6.........3.5...6.3.......7.8.. ED=3.4/1.2/1.2
.............1........6..........5.1.62..5.......9..32...4..........1......3.2... ED=3.4/1.2/1.2
6...4.......57....2.7.........8...4..73.9...2..6..5.9....3..5.91..6......8....2.. ED=2.6/1.2/1.2
...7...4......2.9....5....37.2.6.......37.....9....35......4..628...3.....1...5.. ED=4.5/1.2/1.2
ED=4.5/1.2/1.2
..9.7..8....65.42.6.5.4.....6.593812891426..75..817964..6..4...95...........65...
869735214.32.4...8.41862..3.285.743.37..8.......3.6.8......83.5.8.653....53.7.8..
............51..8.....6..53......5.1.62..5.......9..32...4...2..2...1......3.2...
6...4.......57..2.2.7.........8...4..73.9...2..6..5.9..6.3..5.91..6......8....2..
.2.7...4......2.9....5....3732.65.8.5..37.....9....357953..4..6287653.1...1..753.
Not Solved.

[Edit 31 Oct) Program has changed since this was posted, the samurai ratings have been updated.
Last edited by 1to9only on Thu Oct 31, 2019 6:49 pm, edited 1 time in total.
1to9only
 
Posts: 1187
Joined: 04 April 2018

Re: SE rating for overlapping Sudoku puzzles - suggestion

Postby creint » Tue Oct 29, 2019 5:45 pm

m_b_metcalf's earlier post of another of Ruud's hardest samurai is not solvable using existing SE solving techniques:

Solved used forcing chains in 6.5 seconds, which is probably less than SE 10.0.
Nice to see that no solution can be found when solving only one at a time. Chains need to cross the overlap into another grid.

I'm testing using Ruud's 1st samurai posted here - This is Samurai number 1 for Tuesday November 21, 2006, rated Hard.

Solved in 0.75 seconds, using easier forcing chains, which is probably less than SE 9.0.
creint
 
Posts: 122
Joined: 20 January 2018

Re: SE rating for overlapping Sudoku puzzles - suggestion

Postby Hajime » Tue Oct 29, 2019 8:00 pm

Let's try an easy samurai that can be solved with singles only. But neither subgrids can be solved individually. So a next cell can only be solved using info from the other subgrids interfering via the overlapping parts. Suppose hidden singles SE rating 1.5 . What is the overall SE?
User avatar
Hajime
 
Posts: 83
Joined: 20 April 2018
Location: Netherlands

Next

Return to Software