# Ruby Challenge: Sudoku

• (2 Pages)
• 1
• 2

## 25 Replies - 17465 Views - Last Post: 24 July 2011 - 07:24 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=236057&amp;s=65bdc41a9031dc7214b43b41cb633f53&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #16 Karel-Lodewijk

Reputation: 454
• Posts: 864
• Joined: 17-March 11

## Re: Ruby Challenge: Sudoku

Posted 30 June 2011 - 07:00 PM

This prints all possible solutions to a sudoku.

The algorithm is very basic:
• The solve function goes over every element from left to right, top to bottom.
• If it finds an element not filled in, it will make a list of all possible candidates ((1..9) but not present in row/column/block).
• Then it will call itself recursively with that element filled in for all possible elements.
• When there are no new indexes we have found a solution and add it to the list of solution.

Or shorter a depth first recursive search strategy.

If you just want the algorithm that finds 1 solution, you can instead of solutions.add(matrix) just do pp matrix and exit.

```require 'pp'

def solve(matrix, x, y, solutions)
def nextIndex(x,y) #moves to the next index in 2d array
x += 1
if x > 8 then
y += 1
x = 0
end
if y > 8 then
raise StopIteration
end
return x,y
end

begin
while (matrix[x][y] != 0) do
x,y = nextIndex(x,y)
end

candidates = (1..9).to_a #initial
candidates = candidates - matrix[x] #prune
candidates = candidates - matrix.transpose[y] #prune
blockX = (x / 3).floor
blockY = (y / 3).floor
for i in (blockX*3..blockX*3+2)
for j in (blockY*3..blockY*3+2)
candidates.delete(matrix[i][j]) #prune
end
end

newX, newY = nextIndex(x,y)
candidates.each {|candidate|

newMatrix[x][y] = candidate
solve(newMatrix, newX, newY, solutions)
}

rescue StopIteration
solutions.push(matrix)
end

end

input = []
9.times do
line = gets.chomp
input.push(line.split(",", 9).map{|x| x.to_i})
end

solutions = []
solve(input, 0, 0, solutions)
solutions.each { |x|
pp x
}

```

This post has been edited by Karel-Lodewijk: 30 June 2011 - 07:09 PM

### #17 Karel-Lodewijk

Reputation: 454
• Posts: 864
• Joined: 17-March 11

## Re: Ruby Challenge: Sudoku

Posted 30 June 2011 - 07:15 PM

Perhaps you'll find this interesting.

This is a sudoku solver I've made in prolog. Prolog has kind of a different take on programming perfectly suited to these kind of programs.

```:- use_module(library(clpfd)).
solve(Data, Result):-
Data = [A1, A2, A3, A4, A5, A6, A7, A8, A9,
B1, B2, B3, B4, B5, B6, B7, B8, B9,
C1, C2, C3, C4, C5, C6, C7, C8, C9,
D1, D2, D3, D4, D5, D6, D7, D8, D9,
E1, E2, E3, E4, E5, E6, E7, E8, E9,
F1, F2, F3, F4, F5, F6, F7, F8, F9,
G1, G2, G3, G4, G5, G6, G7, G8, G9,
H1, H2, H3, H4, H5, H6, H7, H8, H9,
I1, I2, I3, I4, I5, I6, I7, I8, I9],

Data ins 1..9,

%rows must be all_distinct
all_distinct([A1, A2, A3, A4, A5, A6, A7, A8, A9]),
all_distinct([B1, B2, B3, B4, B5, B6, B7, B8, B9]),
all_distinct([C1, C2, C3, C4, C5, C6, C7, C8, C9]),
all_distinct([D1, D2, D3, D4, D5, D6, D7, D8, D9]),
all_distinct([E1, E2, E3, E4, E5, E6, E7, E8, E9]),
all_distinct([F1, F2, F3, F4, F5, F6, F7, F8, F9]),
all_distinct([G1, G2, G3, G4, G5, G6, G7, G8, G9]),
all_distinct([H1, H2, H3, H4, H5, H6, H7, H8, H9]),
all_distinct([I1, I2, I3, I4, I5, I6, I7, I8, I9]),

%columns must be all_distinct
all_distinct([A1, B1, C1, D1, E1, F1, G1, H1, I1]),
all_distinct([A2, B2, C2, D2, E2, F2, G2, H2, I2]),
all_distinct([A3, B3, C3, D3, E3, F3, G3, H3, I3]),
all_distinct([A4, B4, C4, D4, E4, F4, G4, H4, I4]),
all_distinct([A5, B5, C5, D5, E5, F5, G5, H5, I5]),
all_distinct([A6, B6, C6, D6, E6, F6, G6, H6, I6]),
all_distinct([A7, B7, C7, D7, E7, F7, G7, H7, I7]),
all_distinct([A8, B8, C8, D8, E8, F8, G8, H8, I8]),
all_distinct([A9, B9, C9, D9, E9, F9, G9, H9, I9]),

%blocks
all_distinct([A1, A2, A3, B1, B2, B3, C1, C2, C3]),
all_distinct([A4, A5, A6, B4, B5, B6, C4, C5, C6]),
all_distinct([A7, A8, A9, B7, B8, B9, C7, C8, C9]),
all_distinct([D1, D2, D3, E1, E2, E3, F1, F2, F3]),
all_distinct([D4, D5, D6, E4, E5, E6, F4, F5, F6]),
all_distinct([D7, D8, D9, E7, E8, E9, F7, F8, F9]),
all_distinct([G1, G2, G3, H1, H2, H3, I1, I2, I3]),
all_distinct([G4, G5, G6, H4, H5, H6, I4, I5, I6]),
all_distinct([G7, G8, G9, H7, H8, H9, I7, I8, I9]),

Result = Data.

```

run it with

```solve([_, _, _, _, 6, _, _, 3, _,
_, 9, 6, _, _, 5, _, _, 4,
_, _, _, 7, _, 1, _, 6, _,
_, 1, _, _, _, 3, _, 9, 5,
_, 4, 9, _, 1, _, 7, 2, _,
7, 3, _, 5, _, _, _, 1, _,
_, 6, _, 9, _, 7, _, _, _,
4, _, _, 8, _, _, 9, 5, _,
_, 2, _, _, 5, _, _, _, _], Result).

```

This post has been edited by Karel-Lodewijk: 30 June 2011 - 07:16 PM

### #18 xclite

• I wrote you an code

Reputation: 1123
• Posts: 3,758
• Joined: 12-May 09

## Re: Ruby Challenge: Sudoku

Posted 05 July 2011 - 05:44 PM

Thanks for the submissions! I'll give them a look and try to post some results by the weekend. I'll also post my solution and let you all know how it stacks up - hopefully somebody's beaten me

### #19 xclite

• I wrote you an code

Reputation: 1123
• Posts: 3,758
• Joined: 12-May 09

## Re: Ruby Challenge: Sudoku

Posted 05 July 2011 - 05:59 PM

Hey Karel-Lodewijk, I'd like to run yours against the other two solutions I have. However, since yours doesn't read from a file, I can't test it in the same way. I'd sub my file reading in, but I don't want to assume your program has the same order for the grid as mine. I also wouldn't want your time dependent on my code, for better or for worse (more likely for worse =p). If you add some code that reads in from a csv, I'd love to run it.

### #20 Karel-Lodewijk

Reputation: 454
• Posts: 864
• Joined: 17-March 11

## Re: Ruby Challenge: Sudoku

Posted 05 July 2011 - 07:44 PM

Well just run it with

ruby code.rb < input.csv

It should work. But remember my comment, it is written to find all solutions to a given sudoku, not stop at one.

Anyway my code is not written to score high points on efficiency. It does score high points on simplicity.

This post has been edited by Karel-Lodewijk: 05 July 2011 - 07:45 PM

### #21 xclite

• I wrote you an code

Reputation: 1123
• Posts: 3,758
• Joined: 12-May 09

## Re: Ruby Challenge: Sudoku

Posted 05 July 2011 - 08:19 PM

Doh I apparently failed to read the part where you parse input - I'd thought it just took an array. Thanks for the heads up.

### #22 Karel-Lodewijk

Reputation: 454
• Posts: 864
• Joined: 17-March 11

## Re: Ruby Challenge: Sudoku

Posted 05 July 2011 - 09:06 PM

I tried to make a more efficient version and it turned out much slower, also I noticed a small bug. If you leave the right-bottom field empty, it will fail sort of. Also it now returns the first solution it finds instead of all solutions. So I guess this is the version I'm submitting.

```require 'pp'

def solve(matrix, x, y, solutions)
def nextIndex(x,y) #moves to the next index in 2d array
x += 1
if x > 8 then
y += 1
x = 0
end
if y > 8 then
raise StopIteration
end
return x,y
end

begin
while (matrix[x][y] != 0) do
x,y = nextIndex(x,y) #move to an element that has not been set yet
end

candidates = (1..9).to_a #initially we can put (1..9) there, but we can prune
candidates = candidates - matrix[x] #prune elements present in rows
candidates = candidates - matrix.map{|x| x[y]} #prune elements present in column
blockX = (x / 3)
blockY = (y / 3)
for i in (blockX*3..blockX*3+2)
for j in (blockY*3..blockY*3+2)
candidates.delete(matrix[i][j]) #prune elements present in 3x3 block
end
end

candidates.each {|candidate| #go over each candidate, create a new square with the candidate filled in
matrix[x][y] = candidate
solve(matrix, x, y, solutions)
matrix[x][y] = 0
}

rescue StopIteration #we are done iterating, so every element has been filled in
pp matrix
exit
solutions.push(matrix)
end

end

input = []
9.times do
line = gets.chomp
input.push(line.split(",", 9).map{|x| x.to_i})
end

solutions = []
solve(input, 0, 0, solutions)
solutions.each { |x|
pp x
}

```

Edit: made 2 really obvious performance improvements. I was selecting a column with

```matrix.transpose[y]

```

Which means transposing the entire sudoku, this is silly.

```matrix.map{|x| x[y]}

```

works just as well.

Then when branching out I needed to make a copy of the matrix. I can not work on the original because when backtracking through the recursive call stack I want my changes to be undone.

I used a dirty trick to get a deep copy of the matrix

```Marshal.load(Marshal.dump(matrix));

```

but basically I change but 1 row, so I only need a deep copy of one row. So I changed it with.

```newMatrix = matrix.dup();
newRow = matrix[x].dup();
newMatrix[x] = newRow;

```

edit2:

On second thought, I don't need a copy at all. Since this code results in a depth first search, I can just undo the change like this.

```matrix[x][y] = candidate
solve(matrix, x, y, solutions)
matrix[x][y] = 0

```

When backtracking matrix[x][y] becomes 0 again, which is exactly what I want.

Now, the way to go to make it more efficient would be keeping the branching factor low. This could be done by starting on an index where the number of candidates is the smallest. Basically if the sudoku has only 1 unique solution, there would be no branching at all. But my attempt at this caused more overhead than it gained performance.

This post has been edited by Karel-Lodewijk: 07 July 2011 - 07:31 AM

### #23 Karel-Lodewijk

Reputation: 454
• Posts: 864
• Joined: 17-March 11

## Re: Ruby Challenge: Sudoku

Posted 07 July 2011 - 08:13 AM

Ok, I went through the trouble of making an efficient implementation. The result is not pretty.

Let me walk you through the noteworthy facts.

The algorithm has not changed really. Still a depth first search but this time with a most constrained value heuristic and some information hashing thrown in for good measure.

• I do a lot of the work that needs to be doing once and store the information in hash maps.
• Heuristic: I calculate the number of candidates for each cell beforehand and select the cell with the smallest number of candidates first. I then update the candidates as I go on solving the sudoku. Think of how a human would solve a sudoku, he wouldn't randomly fill in a number but he would fill in a number of which he is most certain it will be correct. Backtracking to the error when you've made a mistake is a nightmare (inefficient), this is also true on a computer.

1) These are the rowIndexHash, columnIndexHash, blockIndexHash: Where you can get the elements that have not been filled in based on a row,index or block.

2) I needed a priorityqueue in order to efficiently find the element to fill in with the lest number of candidates. But I needed one that performed well when updating a lot of elements often. I found one based on a Fibonacci heap, which was perfect. Think of a Fibonacci heap as a lazy tree-based heap. A heap that allows you to decrease priorities and only restructures if a certain number of these decreases happen. This is the data structure to use when you need a priority queue but the number of priority updates you do also depends on the size of the input.

But this fancy data structure might cause more overhead than it's worth as it contains a maximum of 81 elements. But here you go atleast this time, on my system it outperforms the first version

Spoiler

Interesting things to note:

I profiled it and found that at least for lists with a size < 10, creating them as sets hurts the performance of search/delete operations.

I used a lot of double keys in my hash maps hashMap[[x,y]] = . But after profiling I found out that about 1/4 the running time was spent on hashing Arrays. So creating a unique key from these elements. This is why instead of hashMap[[x,y]], you'll find hashMap[x+9*y], my very fast, much more efficient hash function, given x doesn't go higher than 8 .

This post has been edited by Karel-Lodewijk: 07 July 2011 - 10:47 AM

### #24 xclite

• I wrote you an code

Reputation: 1123
• Posts: 3,758
• Joined: 12-May 09

## Re: Ruby Challenge: Sudoku

Posted 19 July 2011 - 06:35 PM

Results! Everybody loves them, although since only two of you entered, I guess only two of you will really be concerned about seeing them.

I ran Karl's most recent response prior to the June 30th deadline as part of the competition, as well as his final attempt just for comparison's sake.

I ran two puzzles, a complete and an incomplete.
Karl's first submission averaged: 0.004529078 seconds on puzzle1, 0.00495823 on puzzle2.
Karl's final submission averaged: 0.002242384 seconds on puzzle1, 0.00480819 on puzzle2.
Tethik's first submission averaged: 0.0028601678 seconds on puzzle1, 0.002859311 on puzzle2.

Conclusions:
Tethik won the official competition in both categories.
Karl was able to make dramatic improvements through his iterations, although I am surprised the improvements didn't carry over to the incomplete puzzle.

The following counts include my addition of timing lines where necessary.
Tethik's submission was 264 lines total.
Karl's initial submission was 58 lines (whoa), while his last was 649.

For my part, Karl's final submission was able to beat mine on average for the complete puzzle, although nobody was able to beat my average for the incomplete puzzle: 0.025109121s and 0.025451263s, respectively.
My solution is 118 lines, posted below.
Congratulations on your succinct, efficient victory, Tethik, and on your excellent complete puzzle optimizations, Karl!

```class GridLocation
def initialize(x, y, n, grid, row, column)
@x = x
@y = y
@n = n
@grid = grid
@row = row
@column = column
end

attr_reader :x, :y, :row, :grid, :column
def to_s
"([email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */}, [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */})"
end

def allowed_vals
@grid & @column & @row
end

def <=> (other)
return self.allowed_vals.size <=> other.allowed_vals.size
end

end

class Puzzle
def initialize(file_path)
#file should be a csv
@grid = open(file_path, 'r').readlines.map {|line| line.split(',').map {|str_val| str_val.to_i}}
n = @grid.size
@inner_grids = Array.new(n) {|index| (1..n).to_a}
@rows = Array.new(n) {|index| (1..n).to_a}
@columns = Array.new(n) {|index| (1..n).to_a}
@blank_locations = Array.new
to_reject = nil
@divisor = Math.sqrt(n).to_i
0.upto(n - 1) do |y_val|
0.upto(n - 1) do |x_val|
to_reject = @grid[y_val][x_val]
if to_reject != 0 then
@inner_grids[x_val / @divisor + @divisor * (y_val / @divisor)].delete(to_reject)
@rows[y_val].delete(to_reject)
@columns[x_val].delete(to_reject)
else
@blank_locations << GridLocation.new(x_val, y_val, n, @inner_grids[x_val / @divisor + @divisor * (y_val / @divisor)], @rows[y_val], @columns[x_val])
end
end
end
end

def blanks
@blank_locations
end

def set_val(x, y, val)
@grid[y][x] = val
@inner_grids[x / @divisor + @divisor * (y / @divisor)].delete(val)
@rows[y].delete(val)
@columns[x].delete(val)
@blank_locations.reject! {|blank| blank.x == x and blank.y == y}
end

def unset_val(x, y, val)
@grid[y][x] = 0
@inner_grids[x / @divisor + @divisor * (y / @divisor)] << val
@rows[y] << val
@columns[x] << val
@blank_locations << GridLocation.new(x, y, @grid.size, @inner_grids[x / @divisor + @divisor * (y / @divisor)], @rows[y], @columns[x])
end

attr_reader :grid, :inner_grids, :rows, :columns, :blank_locations
end

def get_tabs(indent)
str = ""
1.upto(indent) do |index|
str += "\t"
end
return str
end

def print_solution(puzzle)
puzzle.grid.each do |line|
line.each do |value|
print value
if value != line[-1]
print ','
else
print "\n"
end
end
end
end

def solve(puzzle, indent = 0)
tabs = get_tabs(indent)
if puzzle.blanks.size == 0
puts "Puzzle solved!"
return puzzle
end
most_constrained = puzzle.blanks.sort[0]
#puts "#{tabs}#######################################################"
#puts "#{tabs}Attempting to find a value for (#{most_constrained.x}, #{most_constrained.y})"
#puts "#{tabs}Possible values: #{most_constrained.allowed_vals}"
success = false
most_constrained.allowed_vals.each do |val|
puzzle.set_val(most_constrained.x, most_constrained.y, val)
#puts "#{tabs}Attempting value: #{val}"
success = solve(puzzle, indent + 1)
if success then break end
#puts "#{tabs}Recursive call with #{val} unsuccessful, unsetting."
puzzle.unset_val(most_constrained.x, most_constrained.y, val)
end
return success
end
before = Time.now()
print_solution(solve(Puzzle.new('test_puzzle2.txt')))
puts "Time: #{Time.now() - before}"

```

This post has been edited by xclite: 24 July 2011 - 07:23 PM

### #25 Tethik

Reputation: 17
• Posts: 63
• Joined: 14-March 10

## Re: Ruby Challenge: Sudoku

Posted 24 July 2011 - 09:37 AM

xclite, on 19 July 2011 - 06:35 PM, said:

Results! Everybody loves them, although since only two of you entered, I guess only two of you will really be concerned about seeing them.

I ran Karl's most recent response prior to the June 30th deadline as part of the competition, as well as his final attempt just for comparison's sake.

I ran two puzzles, a complete and an incomplete.
Karl's first submission averaged: 0.004529078 seconds on puzzle1, 0.00495823 on puzzle2.
Karl's final submission averaged: 0.002242384 seconds on puzzle1, 0.00480819 on puzzle2.
Tethik's first submission averaged: 0.028601678 seconds on puzzle1, 0.002859311 on puzzle2.

Conclusions:
Tethik won the official competition in both categories.
Karl was able to make dramatic improvements through his iterations, although I am surprised the improvements didn't carry over to the incomplete puzzle.

Nice to see some results. Although doesn't a time of 0.03 for the first puzzle make my solution more inefficient in regards to Karl's solution (0.002, 0.005)? Also, did you try out my second solution too? I thought that one would be a bit more efficient. Either way, thanks for a fun challenge.

### #26 xclite

• I wrote you an code

Reputation: 1123
• Posts: 3,758
• Joined: 12-May 09

## Re: Ruby Challenge: Sudoku

Posted 24 July 2011 - 07:24 PM

Ooops, typo. Fixed now. I was able to use your second submission because it was submitted before the deadline, so I should have made that clear.