Sudoku solver in Ruby 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 &gt; 2
    x = 6 if i &gt; 5
    y = 3 if j &gt; 2
    y = 6 if j &gt; 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 &lt;&lt; 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
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.