Sudoku solver in Ruby
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.