Tag Archives: Python

SAT-based KenKen Solver

Python, , ,

Inspired by the SAT-based Sudoku solver by Tjark Weber and the corresponding Python implementation, I coded up a quick SAT-based KenKen solver.

The ideas in the KenKen solver are pretty similar to the Sudoku solver. In particular, we reuse the framework of using a boolean variable to represent
each possible digit in each cell and all of the clauses which correspond to the following rules:

  • At least one digit must be present in a cell
  • Two or more digits may not be present in a cell
  • The same digit may not appear more than once in any row
  • The same digit may not appear more than once in any column

To satisfy the mathematical expressions, we generate all list of all possible ways each “cage” can be filled. This is most naturally expressed in disjunctive normal form:

(cell1 has value v1 AND cell2 has value v2 AND ...)
OR (cell1 is value w1 AND cell2 has value w2 AND ...)
OR ...

This can be easily and efficiently transformed into a equisatisfiable conjunctive normal form by adding a few auxiliary variables.

The SAT-based solver is reasonably fast. For example, on my laptop it can solve a 6-by-6 KenKen problem in about 23 ms. On a big a 9-by-9 problem it takes about 328 ms which is a factor of 5 or so slower than the NekNek solver (which takes about 65 ms).

A data descriptor for __doc__

Python, , ,

In Python, suppose you want to implement a class which has a dynamically generated docstring. The easiest way to do this would be to use the @property decorator for the __doc__ attribute. (You also need your class to be a “new-style” class, i.e., inherit from object). For example:

class A(object):
    """Docstring for class."""
    def __init__(self, x):
        self.x = x
    @property
    def __doc__(self):
        return "My value of x is %s." % self.x

This gives the desired result:

>>> a = A(10)
>>> print(a.__doc__)
My value of x is 10.

But hides the docstring for the class A:

>>> A.__doc__
<property at 0x2083db8>

Read on to see how we can fix this. Continue reading A data descriptor for __doc__ →

Debugging MPI + Python

Python, , , , , ,

Python is increasingly becoming a popular language for controlling large numerical simulations due to its scripting abilities and easy bindings with C, C++, and Fortran as provided by ctypes, Boost.Python, SWIG, etc. In addition, there are some nice convenience wrappers for MPI, including mpi4py.

However debugging MPI scripts can be challenging. Here are some useful ways to run your programs for debugging.

  • Open an xterm window for each MPI process, with the script running in iPython.

    $ mpirun -np 4 xterm -e "ipython script.py"
  • Open an xterm window for each MPI process, with gdb attached to each python process. The -x flag tells gdb to run the commands given in the specified file. This is often a good place to add additional breakpoints.

    $ echo "run script.py" > gdb.in
$ mpirun -np 4 xterm -e "gdb -x gdb.in python"
  • Open each MPI process within screen, then open a gnome-terminal with one tab for each screen.

    $ mpirun -np 4 screen -L -m -D -S mpi 
    ipython script.py &
$ gnome-terminal --tab -e "screen -RR -p mpi" 
                 --tab -e "screen -RR -p mpi" 
                 --tab -e "screen -RR -p mpi" 
                 --tab -e "screen -RR -p mpi"

    If your program dies unexpectedly, it is probably because LD_LIBRARY_PATH is stripped by glibc since screen is a setgid/setuid program. You can work around this my modifying the mpirun call as

    $ mpirun -np 4 screen -L -m -D -S mpi 
    env LD_LIBRARY_PATH=$LD_LIBRARY_PATH ipython script.py

Simple Timer using Python’s With Statement

Python, ,

Python’s with statement, available since Python 2.5, does not seem to be widely used despite being very useful.

Here we describe how to use the with statement to create a simple timer with the syntax:

>>> with TicToc():
...     some_slow_operations
...
Elapsed time is 2.000073 seconds.

Readers familiar with MATLAB will recognize the similarity to the familiar timing mechanism:

> tic ; some_slow_operations; toc
Elapsed time is 10.020349 seconds.

Continue reading Simple Timer using Python’s With Statement →

Calling Python from C++

Boost.Python, Python, ,

In a previous post we already covered calling a C function from one Boost.Python module in another module.

What if instead we want to call a Python function directly from C? We’ll stick with the same Bird / Quacker metaphor as in the previous post, but we’ll now implement our duck class in PyDuck.py:

"""
PyDuck.py
"""

def quack():
    print "Python Quack"

Now how can we call Python from C++? It turns out that Boost.Python defines operator() for the object class, so calling Python is relatively easy.  But things become more difficult if we want to maintain a default implementation in C.

Continue reading Calling Python from C++ →