The New Sudoku Players' Forum

[Hajime]

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)?

[creint]

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.

[tarek]

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

[1to9only]

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.
.

[Hajime]

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.

[tarek]

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

[m_b_metcalf]

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

[tarek]

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

[1to9only]

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). An SE gattai solver would be better... Don't think I've given this much thought since...

[tarek]

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). 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

[Hajime]

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


[1to9only]

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]

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.

[creint]

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.

[Hajime]

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?