## Pathfinding Sudoku variant

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Pathfinding Sudoku variant

I made this variant to test custom restrictions on my solver.
Default sudoku rules apply. Additionally, there has to be at least one ascending path (without diagonals) from each 1 to the 9 of the same grid.
There's only one valid solution.

EXAMPLE

Code: Select all
`+-----------+|15.|..9|...||...|7.8|91.||.4.|.1.|...|+-----------+|..1|.3.|...||..7|...|.29||.9.|...|18.|+-----------+|.1.|..5|...||98.|1..|..6||..3|.9.|..1|+-----------+`

Solution: Show

PUZZLE 1

Code: Select all
`+-----------+|7..|.4.|..5||..3|62.|...||...|...|4..|+-----------+|...|3.4|..9||.25|7..|.8.||8..|...|..3|+-----------+|..4|...|...||..1|...|72.||.7.|.6.|5..|+-----------+`

Code: Select all
`7...4...5..362..........4.....3.4..9.257...8.8.......3..4........1...72..7..6.5..`

PUZZLE 2

Code: Select all
`+-----------+|1..|.6.|..2||...|...|...||.89|.45|...|+-----------+|4..|.5.|2..||...|91.|..3||.9.|...|8.6|+-----------+|..4|..1|...||5..|6..|..8||8..|.9.|.5.|+-----------+`

Code: Select all
`1...6...2..........89.45...4...5.2.....91...3.9....8.6..4..1...5..6....88...9..5.`

I hope you like it
Last edited by Wecoc on Sat May 11, 2019 10:15 pm, edited 2 times in total.
Wecoc

Posts: 72
Joined: 08 April 2019
Location: Girona, Catalonia

### Re: Pathfinding Sudoku variant

I don't understand 'ascending path'. You may omit clues?

Hajime

Posts: 205
Joined: 20 April 2018
Location: Netherlands

### Re: Pathfinding Sudoku variant

The rules beside normal sudoku are: for every house one path (only horizontal and vertical lines (and no toroid) are allowed) from digit 1 to digit 9 must exists.

Solution 1 is missing a possible path in box 7, bottom-left 1-2-4-8-9 is possible too.
How does your solver solve this?

Adding greater than restrictions based on logic is the only easy way for a solver.
For Z3 solving: combinations for each possible path, redundant ones not needed
Direct SAT solving should be impossible or I am missing something.
For SAT generating adding the greater than restrictions first with defined paths should work, but can give sometimes no solutions.
Alternative for generating: you could try to find a sudoku that has this path property.
creint

Posts: 211
Joined: 20 January 2018

### Re: Pathfinding Sudoku variant

Hajime wrote:I don't understand 'ascending path'. You may omit clues?

Look at the first grid of the example's solution. You can go from 1 to 9 using two ascending paths: 1-2-3-4-9, 1-2-3-6-9
They go always in ascending order 1<2<3<4<9. I wouldn't be valid the path 1-2-7-4-9, for example.
There should be always at least 1 path with those conditions on each grid. It may seem like not much of a restriction, but it can help eliminate many candidates.

creient wrote:Solution 1 is missing a possible path in box 7, bottom-left 1-2-4-8-9 is possible too.

Good sight. I'll fix it now.

creient wrote:How does your solver solve this?

I made my solver using Ruby, it checks for basic techniques (looks for singles, intersections, naked/hidden subsets, wings, etc) and for more complex cases it makes a guessing for each candidate.
It does its job except with very difficult puzzles, but it won't find 3D-Medusa or things like that
It doesn't do all at once, it's a step by step process like the Andrew Stuart's solver.

To make this variant I created a new Sudoku sub-class and applied the new restriction on the eliminate block/row/column intersections step, to eliminate extra candidates if possible.
I used a simplified version of A* Pathfinding to get all possible paths.

Probably this won't help much but I'll post here the piece of code that gets all the paths.

Hidden Text: Show
Code: Select all
`  # Custom restriction of box/column/row pointing: Pathfinding  def iterate_bcr_path    for dbox in 0...9 # For each 3x3 box      next if @solved_boxes.include?(dbox)      c = self.cells.select{|x| x.box == dbox}      # Get cells with 1 as candidate      c1 = c.select{|cell| cell.values.include?(1)}      # Get cells with 9 as candidate      c9 = c.select{|cell| cell.values.include?(9)}      # We will only use those cases with both cells resolved      # On the guess candidates part this will automatically check those      # boxes that didn't have one of the candidates resolved yet      next if c1.size > 1 or c9.size > 1      # s = start cell (1), e = end cell (9)      s, e = c1[0], c9[0]      iterate_pathfinding(s, e)    end  end    # Iterate Pathfinding  def iterate_pathfinding(s, e)    # Get X, Y of the start and end cells    sx = self.cells.index(s) % 9    ex = self.cells.index(e) % 9    sy = (self.cells.index(s).to_f / 9).floor    ey = (self.cells.index(e).to_f / 9).floor    # If the distance between them is 2 or less every candidate is possible    # inbetween (1-n-9) so no candidates will never be eliminated    return if ((sx - ex).abs + (sy - ey).abs) <= 2    # Create initial path    paths = [Path_Route.new([[sx, sy]])]    # Get all possible paths    get_paths(paths, ex, ey)    # Select solved paths only    paths = paths.select{|path| path.solved}    # If no solved paths were found, the puzzle is broken    # That means that 1/9 candidate is not possible in that cell    if paths.size == 0      @broken_candidate = true      return    end    # Get all cells involved in any possible path    route_cells = []    for path in paths      for k in path.hash_route.keys        if !route_cells.include?(k) && path.hash_route[k] != 9          route_cells.push(k)        end      end    end    # Get all cells involved in EVERY possible path, remove non-used    # candidates of that cell    for i in route_cells      if paths.all?{|path| path.hash_route.keys.include?(i)}        values = []        for path in paths          values.push(path.hash_route[i])        end        values.uniq!        cell = get(*i)        next if cell.start        cell.values = values.clone      end    end    # Get those numbers that appear in EVERY possible path, remove them in    # non-involved cells    for i in 2..8      if paths.all?{|path| path.hash_route.values.include?(i)}        box = get(sx, sy).box        coords = []        for path in paths          coords.push(path.hash_route.invert[i])        end        coords.uniq!        coords_cells = coords.map{|x| get(*x)}        next i if coords_cells.any?{|cell| cell.box != box}        for c in self.cells.select{|cell| cell.box == box}          next if coords_cells.include?(c)          c.values.delete(i)        end      end    end  end    # Get all possible ascending paths  def get_paths(paths, ex, ey)    loop do      # Loop until all paths have no more steps      break if paths.all?{|path| path.end_route == true}      r = paths.select{|path| path.end_route == false}      for path in r # For each path        ix, iy = *path.current        # Get neighbors        n = [[ix, iy + 1], [ix - 1, iy], [ix + 1, iy], [ix, iy - 1]]        n = n.select{|x| x.all?{|v| v >= 0 && v <= 8}}        n = n.select{|x| !path.route.include?(x)}        for node in n # For each neighbor          cell = get(*node)          for value in cell.values            res = path.clone            # Include as new path if the neighbor has a greater value than            # the current cell            if value > path.value              res.value = value              res.route.push(node)              res.hash_route[node] = value              # If the neighbor's value is 9, the path ends automatically              if res.value == 9                res.end_route = true                res.solved = true if node == [ex, ey]              end              paths.push(res)            end          end        end        path.end_route = true      end    end  end`
Wecoc

Posts: 72
Joined: 08 April 2019
Location: Girona, Catalonia

### Re: Pathfinding Sudoku variant

You can extend your solver by adding the same strategies on your chains. If a digit is locked inside a row for all chains, then you can exclude in rows too. Same idea for subsets.
Seeing the code I guess you have implemented:
-digit on one place in all chains so all others in box must be false, but next technique already finds this one too.
-digit in all paths in multiple cells then exclude in all other cells in box

If you don't log your steps then there is not much use for the first technique besides some solving speed.
creint

Posts: 211
Joined: 20 January 2018

### Re: Pathfinding Sudoku variant

creint wrote:If a digit is locked inside a row for all chains, then you can exclude in rows too. Same idea for subsets.

Indeed, I think that already happens. If a digit has only a few possibilities between the possible chains, its removed as candidate in all other implicated cells, resulting in a digit on a single row or column if that's the case.
Also if all chains contain the digit inside the box, then it's removed from cells on that box not implicated in any chain. From there, once other possibilities are removed, pointing subsets or naked subsets will be applied by default means.

creint wrote:If you don't log your steps then there is not much use for the first technique besides some solving speed.

I agree. I'm planning to implement a logger in the future, though.

PUZZLE 3

Code: Select all
`+-----------+|1.3|...|...||...|...|.6.||.4.|.1.|7.2|+-----------+|...|...|...||2.7|.5.|4.6||...|...|.35|+-----------+|3..|..7|...||.16|.3.|..4||4.8|2..|15.|+-----------+`

Code: Select all
`1.3.............6..4..1.7.2.........2.7.5.4.6.......353....7....16.3...44.82..15.`

PUZZLE 4

Code: Select all
`+-----------+|1..|...|9..||..4|...|2..||.29|...|.1.|+-----------+|...|.9.|...||...|.7.|.26||...|1..|..4|+-----------+|.9.|...|.3.||..2|...|...||.3.|.2.|...|+-----------+`

Code: Select all
`1.....9....4...2...29....1.....9........7..26...1....4.9.....3...2.......3..2....`

This last one is interesting because 2 numbers (5,8) are missing in the givens but is still solvable because of the new restriction.

PUZZLE 1 - Solution: Show

PUZZLE 2 - Solution: Show
Wecoc

Posts: 72
Joined: 08 April 2019
Location: Girona, Catalonia

### Re: Pathfinding Sudoku variant

Last puzzle of this serie, this one is fairly simple but a bit special.
Because of uniqueness, this puzzle has only 1 solution with default sudoku restrictions, and also has only 1 solution with the new pathfinding restriction... but it's not the same one!

INVALID: Show
PUZZLE 5

Code: Select all
`+-----------+|8..|..9|..4||.5.|...|3..||.2.|...|5..|+-----------+|.1.|..3|6.9||5.7|.9.|...||...|.4.|.58|+-----------+|.91|...|...||..3|..1|975||...|.6.|.3.|+-----------+`

Code: Select all
`8....9..4.5....3...2....5...1...36.95.7.9........4..58.91........3..1975....6..3.`

PUZZLE 3 - Solution: Show

PUZZLE 4 - Solution: Show

Code: Select all
`Without pathfinding:Example  [26 clues] - 312 solutionsPuzzle 1 [23 clues] - 10 solutionsPuzzle 2 [24 clues] - 47 solutionsPuzzle 3 [25 clues] - 10 solutionsPuzzle 4 [18 clues] - +500 solutions (givens with 2 numbers missing)`
Last edited by Wecoc on Thu May 23, 2019 10:45 pm, edited 1 time in total.
Wecoc

Posts: 72
Joined: 08 April 2019
Location: Girona, Catalonia

### Re: Pathfinding Sudoku variant

Puzzle 5 gets I get stuck at the following situation.
Using only normal logic I placed 1 in A8 (last candidate in cell), because there were no visible contradictions looking at the candidates. But this placements leads to a contradiction in box 6, because the only path left is not possible. Tracing back where it went wrong is almost impossible for a normal user, so not a userfriendly variant. It could be possible that you find a very hard sudoku, that even with pathfinding as first strategy that you can do steps that result in this state.

Code: Select all
`.------------.-------------------.----------------.| 8   7   6  | 235    235   9    | 2     1    4   || 1   5   49 | 24678  278   2478 | 3     689  267 || 3   2   49 | 4678   178   478  | 5     689  67  |:------------+-------------------+----------------:| 4   1   8  | 57     57    3    | 6     2    9   || 5   6   7  | 28     9     28   | 14    4    3   || 9   3   2  | 1      4     6    | 7     5    8   |:------------+-------------------+----------------:| 27  9   1  | 23478  2378  5    | 248   468  26  || 6   48  3  | 248    28    1    | 9     7    5   || 27  48  5  | 9      6     2478 | 1248  3    12  |'------------'-------------------'----------------'`
creint

Posts: 211
Joined: 20 January 2018

### Re: Pathfinding Sudoku variant

Maybe I messed up somewhere, I'll try making another one Also you are right this one is not very userfriendly indeed.
The idea is making a puzzle with a few solutions, but because of unique rectangles the solver ends with only one of them as valid. The contradiction is in those few solutions there's only one that follows the pathfinding rule, and it's not the same one found by uniqueness.
Wecoc

Posts: 72
Joined: 08 April 2019
Location: Girona, Catalonia

### Re: Pathfinding Sudoku variant

But using only singles (which I used) you end up excluding candidates used for the pathfinding rule.
Which seems to contradict normal reasoning that every path should lead to the same solution. So order does matter in this variant. Using valid logic only can render the puzzle in an invalid state.
creint

Posts: 211
Joined: 20 January 2018

### Re: Pathfinding Sudoku variant

I've test it again using Andrew Stuart's solver and Puzzle 5 was wrong, an 8 on box 6 was meant to be a 6, so it's broken
Luckly it doesn't matter because messing around with that solver I found one that has the property I was talking about.
It has 3 solutions without uniqueness, 1 solution with uniqueness and 1 solution (different) with pathfinding.

Code: Select all
`New example - Contradiction between UR/PATH1....9.5.4..3.......6..421......56..25.8..7.....1....98....3.9.53..6.4...17.4...5123679854485312967796584213971435682254896731368127549842753196539261478617948325 UR123679854485312967976584213791435682254896731368127549842753196539261478617948325123679854485312976796584213371495628259836741648127539864753192532961487917248365 PATH`

creint wrote:But using only singles (which I used) you end up excluding candidates used for the pathfinding rule.

As far as I've seen, that should not happen on valid puzzles. That contradiction seen above is because of uniqueness eliminations, not singles.

In puzzles 1-4, order doesn't seem to matter, apart from uniqueness.
For example Puzzle 1 was created using the solver and using paths as soon as you can, but if you try solving it with a default solver you get this, which leads to the same result since only one has a valid path in each box.

Code: Select all
`Puzzle 17.2.4.3654.362.8.7..6.374.2..7384259325796184849.1.673..4.7.93..3145.72..78.63541712849365493625817586137492167384259325796184849512673654271938931458726278963541712948365493625817586137492167384259325796184849512673254871936631459728978263541782149365413625897596837412167384259325796184849512673654271938931458726278963541782149365493625817156837492617384259325796184849512673564271938931458726278963541782149365493625817516837492167384259325796184849512673654271938931458726278963541782941365413625897596837412167384259325796184849512673254178936631459728978263541782941365493625817516837492167384259325796184849512673254178936631459728978263541792148365413625897586937412167384259325796184849512673254871936631459728978263541792841365413625897586937412167384259325796184849512673254178936631459728978263541792841365453629817186537492617384259325796184849215673564172938931458726278963541 PATH`
Wecoc

Posts: 72
Joined: 08 April 2019
Location: Girona, Catalonia