Sudoku solver in Ruby

Question

All the test cases pass except one of the test case which runs> 10 seconds. What can I do to make my solution faster?

def in_row(grid,i,k)
 grid[i].include? k
end
def in_col(grid,j,k)
 0.upto(8) do |i|
 return true if grid[i][j] == k
 end
 false
end
def in_grid(grid,i,j,k)
 x,y =0,0
 x = 3 if i > 2
 x = 6 if i > 5
 y = 3 if j > 2
 y = 6 if j > 5
 x.upto(x+2) do |xx|
 y.upto(y+2) do |yy|
 return true if grid[xx][yy] == k
 end
 end
 return false
end
def find_unassigned_location(grid)
 grid.each_with_index do |rows,i|
 rows.each_with_index do |cols,j|
 return [i,j] if cols == 0
 end
 end 
 false
end 
def sudoku_solve grid
 # If there is no unassigned location, we are done
 cell = find_unassigned_location(grid)
 return [true,grid] unless cell # No unassigned cell remaining
 i,j = cell[0],cell[1]
 1.upto(9) do |k|
 next if in_row(grid,i,k) || in_col(grid,j,k) || in_grid(grid,i,j,k)
 grid[i][j] = k
 return [true,grid] if sudoku_solve(grid)[0] == true # Recursively solve 
 grid[i][j] = 0 # Unassign location if recursive solution returns false
 end
 return [false,grid]
end
def print_grid (grid)
 grid.each do |rows|
 rows.each do |cols|
 print "#{cols} "
 end
 puts ''
 end 
end
board = []
(0...9).each do |i|
 board << gets.split.map {|num| num.to_i}
end
solution = sudoku_solve(board)
print_grid(solution[1]) if solution[0]
# -- input
4 0 0 0 0 6 0 0 0
0 6 0 0 0 0 0 0 9
0 0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 3 0 6 0 0 2 0
1 0 0 0 0 0 9 0 0
8 0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 0 5 

Answer 1

Remember how you solve Sudoku boards manually - you write a list of allowed numbers into each cell, and whenever you add a new number somewhere to the grid, you update the other cell's lists accordingly.

So one obvious optimization is to implement the same kind of bookkeeping in your program, that will speed up the process heavily: instead of having a test like this

1.upto(9) do |k|
 next if in_row(grid,i,k) || in_col(grid,j,k) || in_grid(grid,i,j,k)

your program can just grab the allowed numbers from the cells's list, without the need of calling the functions in_row, in_col, and in_grid. Of course, the assignment of the number will need some additional time now for the bookkeeping, but if you do this right, I am sure the bookkeeping will pay off.

Moreover, such bookkeeping will allow some further optimizations: for example, when the list of allowed numbers of one cell becomes empty, you can stop the recursion immediately. The same is true when the union of all numbers of the "allowed numbers" lists of a row, a column or a 3x3 subgrid does not contain all values from 1 to 9 any more.

Note that for this approach, it will be beneficial to replace your grid array by a data structure or class which holds not only the cell values, but also the "allowed numbers" list of each cell, and supports adding and removing of numbers.

For removing a number, you will need to reset the grid including the internal "allowed number" lists to the state before the number was added. A simple implementation is to make a copy of the whole grid beforehand and replace the current grid by the copy afterwards, when the "move" was not accepted.

Answer 2

You could tell it to run specific scripts similarly to the way you would solve it yourself based on the number in the rows and columns and box. That way it will not be reading over unused code to answer the question correctly. It's not in ruby but just a idea sketch of kind of how you could make it run faster.

if numbers 1,2,3 are in row
 if 1 =< 1 time in row false
 then check column for 1,2,3
 if 1 =< 1 time in column then false
 else 1 = 1 time in column then true
 then next line
 if the numbers 1,2,3,4,5,6,7,8,9 for box
 if 1 =< 1 time in box false
 then next line
 if 1 = 1 time in box then true
 then next line
if numbers 4,5,6 are in row
 if 4 =< 4 time in row false
 then check column for 4,5,6
 if 4 =< 4 time in column then false
 else 4 = 4 time in column then true
 then next line
 if the numbers 1,2,3,4,5,6,7,8,9 for box
 if 4 =< 4 time in box false
 then next line
 if 4 = 4 time in box then true
 then next line
if numbers 7,8,9 are in row
 if 7 =< 7 time in row false
 then check column for 7,8,9
 if 7 =< 7 time in column then false
 else 7 = 7 time in column then true
 then next line
 if the numbers 1,2,3,4,5,6,7,8,9 for box
 if 7 =< 7 time in box false
 then next line
 if 7 = 7 time in box then true
 then next line

Answer 3

Here's a simple method that is quite fast:

There are 4 x 81 questions that you could ask:

Where in row r should the number x be written? 
Where in column c should the number x be written? 
Where in block b should the number x be written?
Which number should be written at row r, column c? 

Of course every time one cell is filled in, four of these questions don't need answering anymore. Of the other questions, each one has from 0 to 9 possible answers. If any question has 0 possible answers, there is no solution. If any question has exactly 1 possible answer, that answer must be taken. To find out the number of possible answers, you just apply the Sudoku rules, nothing else.

With your code, if one of the questions would be unanswerable, you spend lots and lots and lots and lots of time trying to fill out cells when you should know that this will lead to no success. And since you try the same moves in different orders, you will get exponential time consumption.

You define a "move" as filling out a single cell. Change this by defining a "move" as filling out one single cell, and then performing all forced moves.

Starting with a position X, you find the number of possible answers to all the questions. As long as any question has exactly one possible answer, you fill it out accordingly. If a question has no possible answers, the position has no solution. You repeat until either everything is filled out or every question has two or more possible answers. Only then you start with the recursion:

In the recursion, you find again the number of possible answers to all the questions. Then you sort the questions from lower to highest possible number of answers, and make a list of moves accordingly - you would want to try a move first where you had only two possible choices, not one where you had five choices. For all moves in order of that list, you try the move, then do all the forced moves.

In all Sudokus you find in a newspaper, this approach will be very, very fast. Usually you will find lots of forced moves.

If you find positions where this isn't fast enough, you might consider avoiding moves in different orders that lead to the same result: Every time you examined a move completely without finding it led to a solution, you calculate a hash code of the position and build a hash table of positions with no solution, so you don't examine the same position twice. (This will happen often. If you had a questions with only two possible answers giving moves A and B, making move A might make B a forced move and making move B might make A a forced move, so after making either move A or B you would end up in the identical position).

Answer 4

Functional programming can improve a pair of your functions:

def in_col?(grid, j, k)
 0.upto(8).any? {|i| grid[i][j] == k}
end

Getting a board as input should be a function as well, written as:

def input_board
 9.times.map {gets.split.map(&:to_i)}
end

Answer 5

Usually a brute force implementation like this should be fast enough to solve sudokus, but Ruby is really slow, and your implementation is definitely leaving some additional performance behind.

You search for the next position over and over again, iterating over the entire board every time the solve function is called. But you and up processing the fields in a strict linear order, with the only hiccup that you skip filled fields. An algorithm that simply steps forth and back should be possible, and much faster.

In the solve function you call the in functions up to 9 times each, you will save the majority of your function calls if you just find out once which numbers are blocked. And you'll probably get a little faster if you do it inline.

I'm not sure how much difference it makes, but you don't need to pass the grid between functions, you can just have a global variable. And you definitely do not need it in return values.

A minor thing, grid[i][j] = 0 is unnecessarily placed inside the loop.

You could try implementing some intelligent solving steps, but you'd still need to be able to switch back to brute force for some puzzles, so the total task would be a lot more complex.