Discussion on: Generating & Solving Sudoku in JS & Ruby with Backtracking

[edh_developer]

Here's an example of a puzzle with two solutions:

sandwalk.blogspot.com/2007/06/i-kn...

It's possible for your code to randomly generate this puzzle, or one like it. The solver would then find one of the two solutions and return it, without checking for alternate solutions. It wouldn't catch the given example, and it may even return a different solution than the one you started with.

[edh_developer]

I tried it. I added this to the end of your source and ran it:

def printboard(board)
  i = 1
  for row in board
    puts "#{row[0]} #{row[1]} #{row[2]} | #{row[3]} #{row[4]} #{row[5]} | #{row[6]} #{row[7]} #{row[8]}"
    if i == 3 || i == 6 then puts "---------------------" end
    i += 1
  end
end

SOLUTION = [
    [9, 2, 6, 5, 7, 1, 4, 8, 3],
    [3, 5, 1, 4, 8, 6, 2, 7, 9],
    [8, 7, 4, 9, 2, 3, 5, 1, 6],
    [5, 8, 2, 3, 6, 7, 1, 9, 4],
    [1, 4, 9, 2, 5, 8, 3, 6, 7],
    [7, 6, 3, 1, 4, 9, 8, 2, 5],
    [2, 3, 8, 7, 9, 4, 6, 5, 1],
    [6, 1, 7, 8, 3, 5, 9, 4, 2],
    [4, 9, 5, 6, 1, 2, 7, 3, 8]
]
# Could have been randomly generated by
# poke_holes(SOLUTION,52)
PUZZLE = [
    [9, 0, 6, 0, 7, 0, 4, 0, 3],
    [0, 0, 0, 4, 0, 0, 2, 0, 0],
    [0, 7, 0, 0, 2, 3, 0, 1, 0],
    [5, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 4, 0, 2, 0, 8, 0, 6, 0],
    [0, 0, 3, 0, 0, 0, 0, 0, 5],
    [0, 3, 0, 7, 0, 0, 0, 5, 0],
    [0, 0, 7, 0, 0, 5, 0, 0, 0],
    [4, 0, 5, 0, 1, 0, 7, 0, 8]
]

puts "\nOriginal Puzzle:\n\n"
printboard(SOLUTION)

puts "\n\nGenerated Solution:\n\n"
printboard(Sudoku.new.solve(PUZZLE))

The resulting output:

$ ruby sudoku-full.rb

Original Puzzle:

9 2 6 | 5 7 1 | 4 8 3
3 5 1 | 4 8 6 | 2 7 9
8 7 4 | 9 2 3 | 5 1 6
---------------------
5 8 2 | 3 6 7 | 1 9 4
1 4 9 | 2 5 8 | 3 6 7
7 6 3 | 1 4 9 | 8 2 5
---------------------
2 3 8 | 7 9 4 | 6 5 1
6 1 7 | 8 3 5 | 9 4 2
4 9 5 | 6 1 2 | 7 3 8

Generated Solution:

9 2 6 | 5 7 1 | 4 8 3
3 5 1 | 4 8 6 | 2 7 9
8 7 4 | 9 2 3 | 5 1 6
---------------------
5 8 2 | 3 6 7 | 1 9 4
1 4 9 | 2 5 8 | 3 6 7
7 6 3 | 1 9 4 | 8 2 5
---------------------
2 3 8 | 7 4 9 | 6 5 1
6 1 7 | 8 3 5 | 9 4 2
4 9 5 | 6 1 2 | 7 3 8

[Daniel Sasse]

Thank you! I was able to replicate this using a few different boards after your tip. I wrote a multipleSolutions check that now attempts to solve the puzzle from each of the currently empty positions and if more than one unique solution is found it will replace the removed value and attempt to remove a different one. I believe there is a more efficient solution, but this fix is working in the meantime for our app (fludoku.netlify.app). I coded the fix in JS first for the app, and will be working to update the ruby gist and gem to match. Thank you again!