![[info]](http://l-stat.livejournal.com/img/userinfo.gif?v=92.1){kind=small}
I figured it might be useful to collect the updates to different parts of my web existence in a single place, and easier to use livejournal than to roll my own. So here's the first one:
I just updated my Python algorithms library, PADS. Newly added are Sudoku.py, a command-line Sudoku puzzle solver/generator (type "python Sudoku.py -h" at a command line in the PADS directory for more information on how to use it), Repetitivity.py, analysis of paths in graphs that have no two equal consecutive edge labels (see forthcoming paper, used by Sudoku), and StrongConnectivity.py, DFS-based construction of strongly connected components in digraphs. I also added code to BipartiteMatching.py to find edges that can not participate in any perfect matching of a given graph (also used by Sudoku).
I thought the trick for finding unmatchable edges in bipartite graphs was cute; it was new to me, though probably familiar to matching specialists. Find a single perfect matching in the bipartite graph, orient the unmatched edges from one side of the bipartition to the other, and orient the matched edges in the opposite direction. The unmatchable edges are the unmatched ones that have endpoints in different strongly connected components of the resulting digraph.
Anonymous
August 2 2005, 21:30:36 UTC 6 years ago
Graph library in Python
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/tablHerve Br.
August 2 2005, 23:18:17 UTC 6 years ago
Re: Graph library in Python
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.
Anonymous
August 3 2005, 13:55:14 UTC 6 years ago
Re: Graph library in Python
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
Anonymous
September 6 2005, 19:00:42 UTC 6 years ago
input file for Sudoku.py
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
September 7 2005, 01:38:18 UTC 6 years ago
Re: input file for Sudoku.py
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...
September 7 2005, 01:40:10 UTC 6 years ago
Re: input file for Sudoku.py
Sorry, my comment got cut off due to my forgetting to mark up the < and > signs appropriately in HTML. Here's the rest of the answer.what is the correct command line form when using an input file?
python Sudoku.py <inputfile
or
python Sudoku.py -xC <inputfile
where C is the character you want to use to denote a blank cell.
I suppose, since you found this confusing, I should work on documenting it more thoroughly...
Anonymous
September 7 2005, 12:14:37 UTC 6 years ago
Re: input file for Sudoku.py
sudoku.py -g option works fine (and I enjoy using your script very much). But python Sudoku.py-----------------------------------
| 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 |
-----------------------------------
is still giving me the same message:
IOError: [Errno 9] Bad file descriptor (I know this error message by heart already)
What am I doing wrong?
Andrzej Kolinski
September 7 2005, 19:55:29 UTC 6 years ago
Re: input file for Sudoku.py
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.
Anonymous
September 8 2005, 13:10:13 UTC 6 years ago
Re: input file for Sudoku.py
Does the fact that I am in the windowsXP-land have anything to do with these command line problems?September 8 2005, 18:43:52 UTC 6 years ago
Re: input file for Sudoku.py
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.Anonymous
October 28 2005, 11:52:04 UTC 6 years ago
Re: input file for Sudoku.py
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
October 28 2005, 21:59:12 UTC 6 years ago
Re: input file for Sudoku.py
c:\dir\sudoku.py < s1.txt(to solve the puzzle in that file)