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

Doc Brown · Accepted Answer · 2015-08-08 07:11:25Z

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.

hansooloo · Accepted Answer · 2015-08-08 13:04:26Z

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

gnasher729 · Accepted Answer · 2015-08-08 11:19:05Z

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).

Caridorc · Accepted Answer · 2015-08-08 13:35:54Z

1

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

answered Aug 8, 2015 at 13:35

Caridorc

28.2k7 gold badges55 silver badges138 bronze badges

Add a comment |

aaaaaaaaaaaa · Accepted Answer · 2015-08-08 13:54:11Z

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.

Stack Exchange Network

Sudoku solver in Ruby

5 Answers 5

You must log in to answer this question.

Hot Network Questions

Sudoku solver in Ruby

5 Answers 5

You must log in to answer this question.

Related

Hot Network Questions