Bottom Page

Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
 a 'simple' program, hard as .... to understand
#1
Hi, I'm learning python and I went thru some code that was under the title 'simple python programs' and found this.

BOARD_SIZE = 8

def under_attack(col, queens):
   left = right = col

   for r, c in reversed(queens):
       left, right = left - 1, right + 1

       if c in (left, col, right):
           return True
   return False

def solve(n):
   if n == 0:
       return [[]]

   smaller_solutions = solve(n - 1)

   return [solution+[(n,i+1)]
       for i in xrange(BOARD_SIZE)
           for solution in smaller_solutions
               if not under_attack(i+1, solution)]
for answer in solve(BOARD_SIZE):
   print answer
It was my intention to read thru this and a few other programs to see if I could understand them, gain some insight into how python works. If I failed, I could use pyCharm debugger to walk thru each line step by step.

I have to say, even using the debugger, I find this code cryptic.
Is it just me? I'd like to know if experienced python coders can read this code and within a short time understand it.
It has what I'd term 'generator' terms, and these terms are embedded \ implicit. i.e.

Will I be expected to work with code like this in a junior level python job? Cos if I am, I think I'd better quit now and go back to C !

Didn't someone say 'explicit is best' ( with reference to declaring 'self' to be a parameter passed to itself in instance methods ) ? Python is the most implicit language I tried to learn, except prolog. But where prolog is all implicit, python seems to be a horribly confusing mix of implicit and explicit. Powerful I'm sure, but extremely hard to read.

its the 8 queens on a chess board problem, but knowing this I still couldn't understand it.
Quote
#2
It's recursive, so let's start at the bottom of the recursion:

if n == 0:
    return [[]]
That will get returned to solve with n = 1 at this point:

smaller_solutions = solve(n - 1) # n - 1 = 0
Then we get to that horrible list comprehension that I think precludes showing this example to beginners:

return [solution + [(n, i + 1)] for i in xrange(BOARD_SIZE) for solution in smaller solutions if not under_attach(i + 1, solution)]
Let's simplify that with the values we know:

return [solution + [(1, i + 1)] for i in xrange(8) for solution in [[]] if not under_attack(i + 1, solution)]
Now, in the second for loop in the horrible list comprehension, we have only one item. So let's simplify that out as well:

return [[] + [(1, i + 1)] for i in xrange(8) if not under_attack(i + 1, [])]
If we look at under_attack with an empty list for the queens parameter, we can see that the loop will not execute and it will always return False. That means that solve with n = 1 will return:

[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8)]
So it starts out by putting a queen in each column of the first row. This is exactly why i sucks as a variable name. If i was instead col, it would be clearer that the program is iterating over columns.

So this will be returned to solve with n = 2 and passed to the horrible list comprehension. That will iterate over each queen in the first row, and figure out where we can place queens in the second row so that it does not attack the queen in the first row. Again, note the bad variable name n. If it was instead named row, which it was it represents, it would be clearer what is going on in the program.

This continues up the recursion chain, figuring out where in each row you place a queen such that it doesn't attack the previously placed queens. If there are no places to validly place a queen for a given sub-solution, that sub-solution does not get passed up to the next level of the recursion chain.

And, of course, if they'd bothered to put some comments in their code I wouldn't have to write this mess.
Mekire likes this post
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures

Quote
#3
Well, as a first program there are things that are not so simple.
After you have been programming for a while, yes it's quite simple.

I'd start with this post. Choose a tutorial and go from there

One I think is very well done is http://www.python-course.eu/python3_course.php
Quote
#4
thanks, your analysis of the code has helped me understand it. I hadn't realised the code lines up 8 queens on the 1st rank. This makes it a bit easier to understand.

But before I fully go thru it again, at the moment I've got stuck on a problem I thought I'd sorted 2 days ago :
creating break points in pycharm.
Last time i was working with pycharm I could just click on the line number to create what I thought was a breakpoint, I think it was represented by a red or orange ball. It worked at the time.
Today that functionality has vanished. Can't point an click anymore. The pycharm online documents say to create breakpoints with 'ctrl F8' but when I hold this down on a selected line, nothing happens.

edit: ah, just posting about it here has made the difference.
in my previous language I'd click on an empty line and write in 'stop' to get the debugger to stop at that line.
In python its not possible to use an empty line a debugger breakpoint. It nuances like this that I spend alot of time on!
Quote

Top Page

Possibly Related Threads...
Thread Author Replies Views Last Post
  Python Program to Make a Simple Calculator jack_sparrow007 2 4,864 Oct-19-2018, 08:32 AM
Last Post: volcano63
  Hard time trying to have clean MySQL to CSV program PierreSoulier 2 634 Jul-20-2018, 07:52 AM
Last Post: PierreSoulier
  help with simple program juanb007 2 790 Dec-07-2017, 02:15 PM
Last Post: j.crater

Forum Jump:


Users browsing this thread: 1 Guest(s)