Solving Sudoku using Python and Prolog

Two weeks ago, I add came up with an interesting algorithm for solving Hidato which basically involves decomposing the board the grid (can be square, hexagonal or any other shape), into classes of pieces and then arranging them (maybe I’ll write a detailed post on it in the future). So while pondering whether it would be interesting enough to go forward and actually implementing the algorithm compared to the work it would require, I started thinking what will be the simplest way to solve such puzzles, as opposed to efficient.

At first I’ve looked at general purpose constraint solvers, and decided to tackle Sudoku instead as it’s a bit simple to define in terms of constraints. I considered several libraries but in the end I’ve settled on plainly using Prolog. I chose Prolog because as a logic programming language, constraints are its bread and butter. I although kind of liked it as I haven’t done anything in Prolog for quite a few years.

Describing Sudoku in terms of constraints is extremely simple. You need to state that every cell is in a given range and that all rows, columns and sub-grid contain different integers. As mangling with lists in prolog isn’t fun, I’ve wrote a python program that outputs all the prolog statements with hardcoded references to the variables which build-up the board. It’s ugly but dead simple. The script gets the dimensions of the sub-grid.
Continue reading Solving Sudoku using Python and Prolog

passha – A hashapass variant

I like the idea of hashapass, but I’m unwilling to use an online tool, as I fear that someday it might be compromised. So I wrote down my own variant of hashapass. It uses slightly longer passwords, and sha256 as the hash function.

#! /usr/bin/python

"""
passha.py - Generate passwords from a master password and a parameter.

Based on hashapass (http://hashapass.com)
"""
import hmac
import hashlib

def main(passwd, param):
    hm = hmac.HMAC(passwd, param, hashlib.sha256)
    print hm.digest().encode("base64")[:10]
    
if __name__=="__main__":
    import getpass
    passwd = getpass.getpass()
    param = raw_input("Parameter: ")
    main(passwd, param)

CSS Compactor – Reduces CSS File Size

This is a script I wrote back 2006 that reduces the file size for CSS files by removing unnecessary whitespace and comments. It’s also capable of taking such compacted CSS file, and re-indent it to make it readable. For example it would take the following CSS:

/* sample css */
* {
    margin: 0px;
    padding: 0px;
}

/* define style for the logo */
#header .logo {
    float: left;
    /* another comment */
}

and turn it into:

*{ margin:0px; padding:0px;}#header .logo{ float:left;}

which is an equivalent but much shorter CSS code. It can also reindent it back to:

*{
	 margin: 0px;
	 padding: 0px;
}
#header .logo{
	 float: left;
}

Continue reading CSS Compactor – Reduces CSS File Size

Building CookieJar out of Firefox’s cookies.sqlite

Firefox 3 started to store it’s cookies in a SQLite database instead of the old plain-text cookie.txt. While Python’s cookielib module could read the old cookie.txt file, it doesn’t handle the new format. The following python snippet takes a CookieJar object and the path to Firefox cookies.sqlite (or a copy of it) and fills the CookieJar with the cookies from cookies.sqlite.

import sqlite3
import cookielib

def get_cookies(cj, ff_cookies):
    con = sqlite3.connect(ff_cookies)
    cur = con.cursor()
    cur.execute("SELECT host, path, isSecure, expiry, name, value FROM moz_cookies")
    for item in cur.fetchall():
        c = cookielib.Cookie(0, item[4], item[5],
            None, False,
            item[0], item[0].startswith('.'), item[0].startswith('.'),
            item[1], False,
            item[2],
            item[3], item[3]=="",
            None, None, {})
        print c
        cj.set_cookie(c)

It works well for me, except that apperantly Firefox doesn’t save session cookies to the disk at all.

spass-2.0 – Secure Password Generator

This is a complete rewrite of my secure password generator. The new version uses my a true random number generator (and here).

The major change was using the new true random number generator in order to ensure strong passwords. Less significant changes include an easy way to specify password’s strips, and some calling convention changes.

Usage examples:

$ ./spass
E5pT35Fg
$ ./spass -l 14
R$tfOm4g_yRQ2J
$ ./spass -s 0-9a-f -l 32
8b5f14a1eeaabe58c2878ab5416a9ebb

Download the tarball spass-2.0.tar.bz2. The program depends on Boost‘s program_options (it was tested against version 1.37 and 1.42 and should work with other versions too).

Statistical Tests for My Audio Based Random Number Generator

In May I’ve written about a way to generate random number from audio noise. Basically it went like this:

  1. Get audio sample from the microphone.
  2. Push the least significant bit to a buffer.
  3. Repeat steps 1-2 until the buffer is full (buffer size == block size for the hash function).
  4. Apply the hash function on the buffer.
  5. Get random bits from the digest.

In order to continue developing this random number generator (RNG), I’ve written a C++ class that simplifies working with it.
Continue reading Statistical Tests for My Audio Based Random Number Generator

Audio Based True Random Number Generator POC

Few days ago I came up with an idea to create a true random number generator based on noise gathered from a cheap microphone attached to my computer. Tests showed that when sampling the microphone, the least significant bit behaves pretty randomly. This lead me to think it might be good source for gathering entropy for a true random number generator.
Continue reading Audio Based True Random Number Generator POC

Hash Puppy 0.2

This is an update for my simple easy-to-use checksum calculator. It supports md4, md5, and sha1 hash functions. I wrote the project as a way to experience and learn Qt.

Changes since the previous version (Hash Puppy 0.1) include ability to abort a checksum calculation and improved GUI responsiveness. Also there were other minor tweaks to make Hash Puppy easier to use.
Continue reading Hash Puppy 0.2

Improved FTP Backup for WordPress

This script backups both the database and files of a WordPress blog into a remote FTP server (while keeping a local copy). It’s an update of my WordPress Backup to FTP script. The main changes are auto-detecting database settings and better support for caching plugins (specifically WP-Cache). The new version makes it easier to backup multiple WordPress blogs to the same FTP server.
Continue reading Improved FTP Backup for WordPress

An Early Release of the New cssrtl.py-2.0

It has been three years since I’ve released the original version of cssrtl.py (and two since it’s re-release). The old version did a nice job, but experience gained during that time led me to write from scratch a new version. I’ve detailed more than a month ago, the basic principles and ideas that guided me to design a better tool to help adapting CSS files from left-to-right to right-to-left.

The guidelines weren’t just empty words, they were written while working on the Hebrew adaptation to the Fusion theme and in the same time writing a new proof-of-concept version of cssrtl.py. The original intent was to release a more mature version of that code when it will be completed. However, due to the apparent shortage of time in the present and foreseeable future, I can’t see myself complete the project any time soon. So following the “release early” mantra, I’ve decided to release the code as-is. As I said, the code is in working state, but not polished, so it may be of benefit but may contain bugs. If you find any bugs or have any suggestions, I would be glad to hear.
Continue reading An Early Release of the New cssrtl.py-2.0