Ruby Challenge: Sudoku

  • (2 Pages)
  • +
  • 1
  • 2

25 Replies - 12056 Views - Last Post: 24 July 2011 - 07:24 PM Rate Topic: -----

#16 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • 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 = Marshal.load(Marshal.dump(matrix)); #deep clone
			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

Was This Post Helpful? 1
  • +
  • -

#17 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • 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

Was This Post Helpful? 2
  • +
  • -

#18 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 906
  • View blog
  • Posts: 3,171
  • 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 :)
Was This Post Helpful? 0
  • +
  • -

#19 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 906
  • View blog
  • Posts: 3,171
  • 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.
Was This Post Helpful? 0
  • +
  • -

#20 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • 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

Was This Post Helpful? 0
  • +
  • -

#21 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 906
  • View blog
  • Posts: 3,171
  • 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.
Was This Post Helpful? 0
  • +
  • -

#22 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • 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

Was This Post Helpful? 0
  • +
  • -

#23 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • 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

Was This Post Helpful? 1
  • +
  • -

#24 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 906
  • View blog
  • Posts: 3,171
  • 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
		"(#{@x}, #{@y})"
	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

Was This Post Helpful? 0
  • +
  • -

#25 Tethik  Icon User is offline

  • D.I.C Head

Reputation: 17
  • View blog
  • Posts: 61
  • Joined: 14-March 10

Re: Ruby Challenge: Sudoku

Posted 24 July 2011 - 09:37 AM

View Postxclite, 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.
Was This Post Helpful? 0
  • +
  • -

#26 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 906
  • View blog
  • Posts: 3,171
  • 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.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2