DEV Community

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

View post

Replies for: In the puzzle generating code, I think it can generate and return puzzles with multiple solutions. Am I missing something that prevents that from ...

Collapse
 
dsasse07 profile image
Daniel Sasse •

Hi edh_developer, from what I have understood from looking into this, the process of generating the board, and then running the solve function to test the removal of each value to create a starting board should account for this. I haven't come across an edge case where this has not worked yet, so it is quite possible I could have missed something, or that my understanding is a bit off. If you have any specific advice I would be happy to chat with you about it and make any necessary revisions. Thank you!

Collapse
 
edh_developer profile image
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.

Thread Thread
 
edh_developer profile image
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))
Enter fullscreen mode Exit fullscreen mode

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

Thread Thread
 
dsasse07 profile image
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!