Updated Python library: Repetitivity, Sudoku

David: I haven't looked at PADS much, but you might find this interesting if you're not aware of it. Did you know that Boost has a graph library (in C++) with Python bindings? It's experimental, the documentation isn't on the web yet, but will be very shortly. You can see it (and build it) if you download the code from the CVS (see http://www.boost.org/). You have access to all BGL algorithms, listed on http://www.boost.org/libs/graph/doc/table_of_contents.html

Herve Br.

Hi, Hervé. Didn't know about Boost and Python, I'll have to look into that.

PADS is primarily just a collection of algorithms I've needed implementations for at some point or another, so its coverage is not very complete. But some things are much much more straightforward in Python than in C++. For instance the Boost quick tour takes about ten lines of messy code to define a 5-vertex 11-arc graph (the one in their Figure 2):

    enum { A, B, C, D, E, N };
    const int num_vertices = N;
    typedef std::pair<int, int> Edge;
    Edge edge_array[] = 
    { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
      Edge(C,E), Edge(B,D), Edge(D,E), };
    const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);
    Graph g(num_vertices);
    for (int i = 0; i < num_edges; ++i)
      add_edge(edge_array[i].first, edge_array[i].second, g);

The same thing can be done in Python as:

    G = {0:[1,2,3,4], 1:[], 2:[0,4], 3:[0,1,4], 4:[0,1]}

I'd be interested to find out whether the Boost Python binding allows the continued use of such simplified definitions.

Will send you a copy by email since I'm not sure how regularly you're likely to read here.

I don't know if I sm doing something wrong, but I have some test examples where Boost is a fair bit slower than raw Python code (not even using PADS).

-- Suresh

David,

I am a Python beginner/enthusiast and just recently I found your sudoku script and I am enjoying using it. I wanted to experiment with imput files but I failed:

• what is the correct format of an input file?

• what is the correct command line form when using an input file?

Could you help me please.

Thank you

Andrzej Kolinski

what is the correct format of an input file?

Any text file that lists the cells in order, having a single digit for each given and some other character for the blank cells. By default the blank cells should be given as either a period or a zero, but there is an option to allow any other character to count as a blank cell. Any character other than the digits or the blank cells is ignored.

So, the output the program produces is suitable to reuse as input.

what is the correct command line form when using an input file?

python Sudoku.py < filename

or

python Sudoku.py -xC < filename

to use C as the blank character

I suppose, since you found this unclear, I should work on documenting it more thoroughly...

sudoku.py -g option works fine (and I enjoy using your script very much). But python Sudoku.py <sud1.txt -2 -ft > sud2.txt command line where sud1.txt is for example (I tried many other input file formats):

 ----------------------------------- 
| 3   .   8 | .   .   . | 9   .   . |
|           |           |           |
| 7   .   6 | .   .   3 | .   2   . |
|           |           |           |
| .   1   . | .   .   . | 7   .   . |
|-----------------------------------|
| 9   .   . | .   7   . | .   5   . |
|           |           |           |
| .   .   3 | .   6   . | 2   .   . |
|           |           |           |
| .   2   . | .   9   . | .   .   1 |
|-----------------------------------|
| .   .   2 | .   .   . | .   3   . |
|           |           |           |
| .   4   . | 2   .   . | 8   .   6 |
|           |           |           |
| .   .   7 | .   .   . | 4   .   2 |
 ----------------------------------- 

What am I doing wrong?

Andrzej Kolinski

This sounds like more a problem with how your python and command line are set up and less with how my code works. That command line should cause python to run in such a way that commands to read input from the standard input stream get their input from the filename. My code doesn't see the <filename part, it just reads from standard input. Does it work to run any other python programs with input redirected?

One workaround might be, instead of redirecting input from a file, just run the program without the redirection so that it expects you to type the input, and then copy and paste it into your console window. That's the way I usually run it, actually.

Does the fact that I am in the windowsXP-land have anything to do with these command line problems?

Probably, but it also means it's going to be hard for me to diagnose them in more detail. I mostly use OS X and occasionally Solaris.

I returned back to using your excellent program. Mainly because my wife is now after an "evil" level. Could you please just show me how you input data into the command line to solve a puzzle.

ex.:

c:\dir\sudoku.py -g -ftext > s1.txt (to generate and save)
c:\dir\sudoku.py -g -2 -ftext > s1.txt (to generate, solve and save)

but

c:\dir\sudoku.py -? (to input a puzzle to be solved)

Maybe I will then be able to figure out the way on my os (Windows XP) :-).

Thank you

Andrzej Kolinski

c:\dir\sudoku.py < s1.txt

(to solve the puzzle in that file)