Projects

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

Brute force Sudoku solver in Java

March 31st, 2011

I did this Sudoku solver for a school project and I’ve now decided to release it as a proof-of-concept project. It’s nothing fancy. It contains a class used to brute force Sudoku puzzles, you can read more about the algorithm on Wikipedia, and a little Swing GUI. I’ve never used Swing before doing this project so don’t expect anything amazing. The code is released under GPL v2 and I hope it might be useful to someone out there. There is a generated Javadoc so check it out for more detailed info about the classes.

Check out the code in my public Mercurial repository.

Download executable JAR-file.

And heres a overview of the brute force class (got to the Mercurial repository to get the GUI source):

/**
 * Sudoku Solver Proof-of-concept.
 * Copyright (C) 2011 Anton Fagerberg (Kung Foo Code).
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package sudoku;

public class Sudoku {

	private int[][] matrix = new int[9][9];
	private int[][] inputMatrix = new int[9][9];

	/**
	 * Remove all the numbers from the sudoku-matrixes.
	 */
	public void resetMatrix() {
		matrix = new int[9][9];
		inputMatrix = new int[9][9];
	}

	/**
	 * Set value of the X- & Y-coordinate in the matrix.
	 * If x > 8 the y-value will automatically increase. set(0, 1, 1) is the same as set(9, 0, 1).
	 * @param x X-coordinate, 0-80.
	 * @param y Y-coordinate, 0-8.
	 * @param value Number, 1,9.
	 */
	private void fill(int x, int y, int value) {

		while (x < 0) {
			x += 9;
			y--;
		}

		while(x > 8) {
			x -= 9;
			y++;
		}

		matrix[x][y] = value;
	}

	/**
	 * Save value from user input to the matrix which handles user input.
	 * If x > 8 the y-value will automatically increase. set(0, 1, 1) is the same as set(9, 0, 1).
	 * @param x X-coordinate, 0-80.
	 * @param y Y-coordinate, 0-8.
	 * @param value Number, 1,9.
	 */
	public void set(int x, int y, int value) {

		while (x < 0) {
			x += 9;
			y--;
		}

		while(x > 8) {
			x -= 9;
			y++;
		}

		inputMatrix[x][y] = value;
	}

	/**
	 * Copy the values of the matrix containing the user input to the matrix used when trying to solve the puzzle.
	 */
	private void copyMatrix() {
		for (int x = 0; x != 9; x++)
			for (int y = 0; y != 9; y++)
				matrix[x][y] = inputMatrix[x][y];
	}

	/**
	 * Try to solve the sudoku-puzzle.
	 * @return True or false based on if the puzzle was solved or not.
	 */
	public boolean solve() {
		copyMatrix();
		return solve(0);
	}

	/**
	 * Get the value from the specified X- & Y-coordinate in the matrix used to solve the sudoku-puzzles.
	 * If x > 8 the y-value will automatically increase. set(0, 1, 1) is the same as set(9, 0, 1).
	 * @param x X-coordinate, 0-80.
	 * @param y Y-coordinate, 0-8.
	 * @return The value, 0-9. (0 is regarded as not defined).
	 */
	public int getValue(int x, int y) {

		while (x < 0) {
			x += 9;
			y--;
		}

		while(x > 8) {
			x -= 9;
			y++;
		}

		return matrix[x][y];
	}

	/**
	 * Get the value from the specified X- & Y-coordinate from the matrix which contain the user inputs.
	 * If x > 8 the y-value will automatically increase. set(0, 1, 1) is the same as set(9, 0, 1).
	 * @param x X-coordinate, 0-80.
	 * @param y Y-coordinate, 0-8.
	 * @return The value, 0-9. (0 is regarded as not defined).
	 */
	public int getValueOriginal(int x, int y) {

		while (x < 0) {
			x += 9;
			y--;
		}

		while(x > 8) {
			x -= 9;
			y++;
		}

		return inputMatrix[x][y];
	}

	/**
	 * Recursive function which fills a valid number to the X- & Y-coordinate based on the sudoku-rules.
	 * The function will call itself with the next X- & Y-coordinate if it finds a valid number to insert or if the number is already set by the user input.
	 * If x > 8 the y-value will automatically increase.
	 * @param x X-coordinate.
	 * @return True or false if a valid number can be inserted or not.
	 */
	private boolean solve(int x) {

		if (x == 81)
			return true;

		if (getValue(x, 0) != 0 && getValue(x, 0) == getValueOriginal(x, 0)) {
			return solve(x+1);
		}
		else {
			for (int i : getValidNumbers(x, 0)) {
				if (i != 0) {
					fill(x, 0, i);

					if (!solve(x+1))
						fill(x,0,0);
					else
						return true;
				}
			}
		}
		return false;
	}

	/**
	 * Validate if a specified number is valid at the X- & Y-coordinate based on the sudoku-rules.
	 * If x > 8 the y-value will automatically increase. set(0, 1, 1) is the same as set(9, 0, 1).
	 * @param x X-coordinate, 0-80.
	 * @param y Y-coordinate, 0-8.
	 * @param number Number (Only 1-9 can be valid).
	 * @return True or false based on if the number is valid according to the sudoku-rules.
	 */
	public boolean validNumberOriginal (int x, int y, int number) {

		if (number < 1 || number > 9)
			return false;

		while (x < 0) {
			x += 9;
			y--;
		}

		while(x > 8) {
			x -= 9;
			y++;
		}

		int[] validNumbers = {1,2,3,4,5,6,7,8,9};

		// Check vertical and horizontal
		for (int i = 0; i != 9; i++) {
			if (inputMatrix[i][y] != 0)
				validNumbers[inputMatrix[i][y]-1] = 0;
			if (inputMatrix[x][i] != 0)
				validNumbers[inputMatrix[x][i]-1] = 0;
		}

		// Check the "squares"
		int squareX, squareY;

		if (x < 3)
			squareX = 0;
		else if (x < 6)
			squareX = 3;
		else
			squareX = 6;

		if (y < 3)
			squareY = 0;
		else if (y < 6)
			squareY = 3;
		else
			squareY = 6;

		for (int i = 0; i != 3; i++) {
			for (int j = 0; j != 3; j++) {
				if (inputMatrix[i+squareX][j+squareY] != 0) {
					validNumbers[inputMatrix[i+squareX][j+squareY]-1] = 0;
				}
			}
		}

		return (validNumbers[number-1] == 0) ? false : true;
	}

	/**
	 * Returns an array of the valid numbers at the X- & Y-coordinate according to the sudoku-rules.
	 * If the number n is valid the array will have array[n-1] = n. If n is invalid array[n-1] = 0.
	 * If x > 8 the y-value will automatically increase. set(0, 1, 1) is the same as set(9, 0, 1).
	 * @param x X-coordinate, 0-80.
	 * @param y Y-coordinate, 0-8.
	 * @return Array of valid numbers (size 9).
	 */
	private int[] getValidNumbers(int x, int y) {

		while (x < 0) {
			x += 9;
			y--;
		}

		while(x > 8) {
			x -= 9;
			y++;
		}

		int[] validNumbers = {1,2,3,4,5,6,7,8,9};

		// Check vertical and horizontal
		for (int i = 0; i != 9; i++) {
			if (matrix[i][y] != 0) {
				validNumbers[matrix[i][y]-1] = 0;
			}
			if (matrix[x][i] != 0) {
				validNumbers[matrix[x][i]-1] = 0;
			}
		}

		// Check the "squares"
		int squareX, squareY;

		if (x < 3)
			squareX = 0;
		else if (x < 6)
			squareX = 3;
		else
			squareX = 6;

		if (y < 3)
			squareY = 0;
		else if (y < 6)
			squareY = 3;
		else
			squareY = 6;

		for (int i = 0; i != 3; i++) {
			for (int j = 0; j != 3; j++) {
				if (matrix[i+squareX][j+squareY] != 0) {
					validNumbers[matrix[i+squareX][j+squareY]-1] = 0;
				}
			}
		}

		return validNumbers;
	}

	/**
	 * Print a ascii-version of the sudoku-puzzle to the console.
	 */
	public void printTable() {
		System.out.print("\n");
		for (int x = 0; x != 9; x++) {
			for (int y = 0; y != 9; y++) {
				System.out.print(" " + inputMatrix[x][y] + " ");
				if (y == 2 || y == 5)
					System.out.print("|");
			}
			if (x == 2 || x == 5)
				System.out.print("\n---------+---------+--------");
			System.out.print("\n");
		}
	}
}

4 comments »

Posted in Projects

Tags: Brute force Java Sudoku Sudoku solver Swing

Mandelbrot Fractals Generator

November 18th, 2010

I was given an assignment to create a Mandelbrot Fractals Generator at my University – and this is basically what I did.

A short user manual:

Chose resolution and Color or Black / White and press render to generate the image.
The field labeled “extra” is the number of iterations. More iterations = more accurate picture (and slowed load of course).
Press mouse and drag to zoom in. The more you zoom in, the more iterations you’ll need.
You can save images from the File-menu, the will however be of crappy quality. (Note: I did not design the GUI, it was given to me as part of the assignment).

Example:

import java.awt.Color;

public class Generator {

	private int pixelResolution = 1;
	private int iterations;
	private Color[] colorLevels = new Color[255];;

	public Generator() {
		for (int i = 0; i < 255; i++) {
			colorLevels[i] = new Color(i, 0, i); // From black to pink.
		}
	}

	public void render(MandelbrotGUI mGui) {

		switch (mGui.getResolution()) {
			case MandelbrotGUI.RESOLUTION_VERY_HIGH:
				pixelResolution = 1;
				break;
			case MandelbrotGUI.RESOLUTION_HIGH:
				pixelResolution = 3;
				break;
			case MandelbrotGUI.RESOLUTION_MEDIUM:
				pixelResolution = 5;
				break;
			case MandelbrotGUI.RESOLUTION_LOW:
				pixelResolution = 7;
				break;
			case MandelbrotGUI.RESOLUTION_VERY_LOW:
				pixelResolution = 9;
				break;
		}

		try {
			iterations = Integer.parseInt(mGui.getExtraText());
		} catch (NumberFormatException e) {
			if (mGui.getMode() == MandelbrotGUI.MODE_COLOR) {
				iterations = 50;
			} else {
				iterations = 200;
			}
		}

		Color[][] picture = new Color[mGui.getHeight() / pixelResolution][mGui.getWidth() / pixelResolution];
		Complex[][] c = mesh(mGui.getMinimumReal(), mGui.getMaximumReal(), mGui.getMinimumImag(), mGui.getMaximumImag(), mGui.getWidth(), mGui.getHeight());

		for (int x = 0; x < mGui.getHeight() / pixelResolution; x++) {
			for (int y = 0; y < mGui.getWidth() / pixelResolution; y++) {

				int i = 0;

				Complex almonds = new Complex(0.0, 0.0);

				while (almonds.getAbs2() <= 4 && i < iterations) {
					almonds.mul(almonds);
					almonds.add(c[x][y]);
					i++;
				}

				if (almonds.getAbs2() <= 4) {
					if (mGui.getMode() == MandelbrotGUI.MODE_BW) {
						picture[x][y] = Color.BLACK;
					} else {
						picture[x][y] = new Color(20, 20, 20);
					}
				} else {
					if (mGui.getMode() == MandelbrotGUI.MODE_BW) {
						picture[x][y] = Color.WHITE;
					} else {
						picture[x][y] = colorLevels[(int) Math.ceil((254 / (double) iterations) * i)];
					}
				}
			}
		}

		mGui.putData(picture, pixelResolution, pixelResolution);
	}

	private Complex[][] mesh(double minRe, double maxRe, double minIm, double maxIm, int width, int height) {

		double positionIm = (maxIm - minIm) / height;
		double positionRe = (maxRe - minRe) / width;

		Complex[][] c = new Complex[height / pixelResolution][width / pixelResolution];

		double alignIm = 0.5 * positionIm * (pixelResolution + 1) - maxIm;
		double alignRe = 0.5 * positionRe * (pixelResolution + 1) + minRe;
		double posResIm = positionIm * pixelResolution;
		double posResRe = positionRe * pixelResolution;

		double[] complexX = new double[(width / pixelResolution)];

		for (int y = 0; y < width / pixelResolution; y++) {
			complexX[y] = posResRe * y + alignRe;
		}

		for (int a = 0; a < height / pixelResolution; a++) {
			double complexY =  posResIm * a  + alignIm;
			for (int b = 0; b < width / pixelResolution; b++) {
				c[a][b] = new Complex(complexX[b], complexY);
			}
		}

		return c;
	}
}

Note that I did not write the GUI!

No comments »

Posted in Projects

- Subscribe Subscribe to my blogs feed
About Kung Foo Code
- Welcome to Kung Foo Code! This is a personal site which belongs to me, Anton Fagerberg – a open-source loving, 24 years old guy from Sweden. I have recently moved to Lund, Sweden where I study “Master of Science in Computer Science and Engineering” at Lunds University.
  
  I use this place to write about the random nerdy things which I find amusing, distribute my applications (even if I haven’t published so many yet), show of code snippets and share a couple of neat tutorials.
You are currently browsing the archives for the Projects category.

Categories

Back to Top