Pathfinding Sudoku variant

For fans of Killer Sudoku, Samurai Sudoku and other variants

Pathfinding Sudoku variant

Postby Wecoc » Tue Apr 30, 2019 1:34 pm

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
Image


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 8-)
Last edited by Wecoc on Sat May 11, 2019 10:15 pm, edited 2 times in total.
Wecoc
 
Posts: 56
Joined: 08 April 2019
Location: Girona, Catalonia

Re: Pathfinding Sudoku variant

Postby Hajime » Tue Apr 30, 2019 4:28 pm

I don't understand 'ascending path'. You may omit clues?
User avatar
Hajime
 
Posts: 78
Joined: 20 April 2018
Location: Netherlands

Re: Pathfinding Sudoku variant

Postby creint » Tue Apr 30, 2019 4:33 pm

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: 105
Joined: 20 January 2018

Re: Pathfinding Sudoku variant

Postby Wecoc » Tue Apr 30, 2019 5:21 pm

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 :roll:
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: 56
Joined: 08 April 2019
Location: Girona, Catalonia

Re: Pathfinding Sudoku variant

Postby creint » Wed May 01, 2019 7:17 pm

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: 105
Joined: 20 January 2018

Re: Pathfinding Sudoku variant

Postby Wecoc » Sat May 11, 2019 10:37 pm

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
Image


PUZZLE 2 - Solution: Show
Image
Wecoc
 
Posts: 56
Joined: 08 April 2019
Location: Girona, Catalonia

Re: Pathfinding Sudoku variant

Postby Wecoc » Thu May 23, 2019 3:39 pm

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
Image

PUZZLE 4 - Solution: Show
Image


Code: Select all
Without pathfinding:
Example  [26 clues] - 312 solutions
Puzzle 1 [23 clues] - 10 solutions
Puzzle 2 [24 clues] - 47 solutions
Puzzle 3 [25 clues] - 10 solutions
Puzzle 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: 56
Joined: 08 April 2019
Location: Girona, Catalonia

Re: Pathfinding Sudoku variant

Postby creint » Thu May 23, 2019 5:05 pm

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: 105
Joined: 20 January 2018

Re: Pathfinding Sudoku variant

Postby Wecoc » Thu May 23, 2019 6:15 pm

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: 56
Joined: 08 April 2019
Location: Girona, Catalonia

Re: Pathfinding Sudoku variant

Postby creint » Thu May 23, 2019 6:47 pm

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: 105
Joined: 20 January 2018

Re: Pathfinding Sudoku variant

Postby Wecoc » Thu May 23, 2019 11:16 pm

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/PATH
1....9.5.4..3.......6..421......56..25.8..7.....1....98....3.9.53..6.4...17.4...5
123679854485312967796584213971435682254896731368127549842753196539261478617948325 UR
123679854485312967976584213791435682254896731368127549842753196539261478617948325
123679854485312976796584213371495628259836741648127539864753192532961487917248365 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 1
7.2.4.3654.362.8.7..6.374.2..7384259325796184849.1.673..4.7.93..3145.72..78.63541
712849365493625817586137492167384259325796184849512673654271938931458726278963541
712948365493625817586137492167384259325796184849512673254871936631459728978263541
782149365413625897596837412167384259325796184849512673654271938931458726278963541
782149365493625817156837492617384259325796184849512673564271938931458726278963541
782149365493625817516837492167384259325796184849512673654271938931458726278963541
782941365413625897596837412167384259325796184849512673254178936631459728978263541
782941365493625817516837492167384259325796184849512673254178936631459728978263541
792148365413625897586937412167384259325796184849512673254871936631459728978263541
792841365413625897586937412167384259325796184849512673254178936631459728978263541
792841365453629817186537492617384259325796184849215673564172938931458726278963541 PATH
Wecoc
 
Posts: 56
Joined: 08 April 2019
Location: Girona, Catalonia


Return to Sudoku variants