Code Snippets

Ruby sudoku solver

October 14th, 2011

I have written a new sudoku solver in Ruby. Just a simple command line tool as a proof on concept to teach myself Ruby and improve the back-tracking code a bit (the code is a bit better written than my Java version).

The code and more info is on my Github page:
github.com/KungFooAnton/Sudoku-Solver-Ruby

class SudokuSolver
	# Transforms each cell (0-80) to the corresponding top-left (0,3, ... ,57,60) of each 3x3 square.
	def fix_pos(cell)
		return 27*(cell/9/3)+3*(cell/3%3)
	end

	def get_valid(cell, matrix)
		valid = [1,2,3,4,5,6,7,8,9]

		# Look for duplicates in row / column.
		0.upto(8) do |n|
			row_element = matrix[cell%9+n*9]
			col_element = matrix[cell/9*9+n]

			valid[row_element-1] = 0 if row_element != 0
			valid[col_element-1] = 0 if col_element != 0
		end

		# Look for duplicates in "square".
		0.upto(2) do |n|
			[0,9,18].each do |m|
				value = matrix[fix_pos(cell) + n + m]
				valid[value-1] = 0 if value != 0
			end
		end

		return valid.delete_if { |x| x == 0 }
	end

	def solve(i = 0, matrix)
		return true if i == 81
		return solve(i + 1, matrix) if matrix[i] != 0 

		get_valid(i, matrix).each do |n|
			matrix[i] = n
			return true if solve(i+1, matrix)
			matrix[i] = 0
		end

		return false
	end

	# Very simple user-input mode.
	def new
		matrix = Array.new(81).fill(0)

		0.upto(80) do |n|
			matrix[n] = "*"
			puts ascii(matrix) + "\nPick a number 0-9 (Enter or 0 is blank):"
			matrix[n] = 0

			input = gets.chomp.to_i
			puts "\n\n\n==========================================\n\n\n"

			if !get_valid(n, matrix).push(0).include?(input)
				puts "* * * * * * * * * * * * *\n Warning: invalid choice! \n* * * * * * * * * * * * *"
				redo
			end

			matrix[n] = input
		end

		return matrix
	end

	# ASCII-representation of the Sudoku puzzle.
	def ascii(matrix)
		ascii = String.new

		0.upto(80) do |n|
			ascii = ascii + "\n+-------+-------+-------+" if n % 27 == 0
			ascii = ascii + "\n" if n % 9  == 0
			ascii = ascii + "| " if n % 3 == 0
			ascii = ascii + (matrix[n] != 0 ? matrix[n].to_s : "_") + " "
			ascii = ascii + "|" if n % 9 == 8
		end

		return ascii + "\n+-------+-------+-------+"
	end
end

# Short example of how to use it.
# User have to input the sudoku puzzle from commandline.
s = SudokuSolver::new
start_time = Time.now
s.solve(matrix = s.new)
puts "* * * * * * * * * * * * * *\nSolved it in #{Time.now - start_time}s!\n* * * * * * * * * * * * * * #{s.ascii(matrix)}"

No comments »

Posted in Code Snippets, Projects

Palindrome finder in Java (+ Ruby)

October 10th, 2010

I was doing the first of three steps in the Greplin programming challenge the other night in PHP before I went to sleep, just for the fun of it. I found the link via Hacker News (love that site) and there are a lot of really neat solutions if you read the comments. Much much better ones than mine.

The challenge was basically to find the longest palindrome (a word, phrase, number or other sequence of units that can be read the same way in either direction) in a given string. I re-wrote the thing the day after in Java (I thought it was a good exercise for me since I’m taking a Java course in school at the moment) and here’s how it turned out:

import java.util.ArrayList;

public class PalindromeFinder {

    public static void main(String[] args) {

        String text = "FhourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth";
        ArrayList results = new ArrayList();

        for (int blockSize = text.length(); blockSize != 1; blockSize--)
        {
            for (int x = 0; x != text.length() - blockSize; x++) {

                String stringPiece = text.substring(x, x + blockSize);

                if (stringPiece.equals(new StringBuilder(stringPiece).reverse().toString())) {
                    results.add(stringPiece);
                    // Break here if you only want to find largest palindrome.
                }
            }
        }

        System.out.println(results.get(0));
    }
}

I did the same thing in Ruby today. Just thought it would be fun learning it.

string = "FhourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"
results = Array.new

for i in 2 .. string.size
	for j in 0 .. string.size - i
		piece = string[j,i]
		if piece == piece.reverse
			results << piece
		end
	end
end

puts results[-1]

Note: It should be “results < < piece" without a blank space between the < but something gets screwed with the markup.

No comments »

Posted in Code Snippets

Tags: