## DEV Community is a community of 787,776 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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

edh_developer

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

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!

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