Python Takuzu solver

If you are unfamiliar with the logic puzzle game Takuzu, I learned how to play it and was inspired to make the project from this challenge posted on reddit. The short version of the game is it's a logic puzzle that uses 0s and 1s on an n×n grid that does not allow three repeating numbers in a row nor two rows or columns to be the same.

I would love to get advice on style, variable naming, and areas where efficiency could be improved if possible. One function in particular I would like advice on is build_perms. It's functional and yields the results I want, however it does so with multi-layered nested lists. I'd also like to know if I went overkill with list comprehensions. I haven't extensively used them in the past, so I thought this may be a good way to learn. Either way, here's the project:

```
import re, itertools, copy

def rotate_right(puzzle):
"""
Rotates the puzzle right thus making
our columns into our rows and vice versa
"""
return [''.join(t) for t in zip(*puzzle[::-1])]

def rotate_left(puzzle):
"""
Rotates the puzzle left thus making
our rows back into our columns
"""
return [''.join(t) for t in list(zip(*puzzle))[::-1]]

def replace_twos(line):
"""
An easy placement of alternating numbers.
Helps fill out the initial board
"""
line = line.replace('.00.', '1001')
line = line.replace('00.', '001')
line = line.replace('.00', '100')

line = line.replace('.11.', '0110')
line = line.replace('11.', '110')
line = line.replace('.11', '011')

line = line.replace('1.1', '101')
line = line.replace('0.0', '010')

return line

def half_filled(line):
"""
Fills all .s with the opposite number
if the board has half already filled
"""
if line.count('1') == (len(line) // 2):
line = line.replace('.', '0')
elif line.count('0') == (len(line) // 2):
line = line.replace('.', '1')

return line

def solve_partial(puzzle):
"""
Finds

Optimization of satisfy_costraints

As you stated that this function runs over 2 million times, I will focus on improving its runtime.

I suggest you remove all the variables it contains as assigning a result to a var forces evaluation while avoiding it allows to take advantage of the lazyness of all (it stops at the first false).

Also running list.count (linear) for each item in the list (linear) is quadratic (linear x linear) I suggest you use your own set idea that is linear.

Square brackets create a list that is immediately discarded, you should use round ones instead to create a generator (no space / time waste).

"Pythonic" style

range(len

for i in range(len(puzzle)):
    puzzle[i] = replace_twos(puzzle[i]) 
    puzzle[i] = half_filled(puzzle[i])

As a general rule range(len means that you are fighting against the language. You can write this without explicit indexing with either list comprehension or map (I suggest list comprehension).

In another example:

for i in range(len(puzzle)):
    ....
    if like_original(puzzle[i], line)

You can iterate directly over the puzzle with for:

for x in puzzle:
    ....
    if like_original(x, line)

It is clearer and you may chose any descriptive name over x to further improve.

Dry

line = line.replace('.00.', '1001') 
line = line.replace('00.', '001')
# .... Many more similar lines

Too much repetition. The DRY principle suggests a loop where only the pairs of string change:

for to_replace, replacement in ( ('.00.', '1001'), ...):
    line = line.replace(to_replace, replacement)

This improves the signal / noise ratio.

Proper handling of failure

print("UH OH")

Is not a proper way to handle errors.

You should raise an appropriate exception (even a costum one if that makes your code more descriptive) with a clear error message.

Something like:

raise ImpossiblePuzzleException("Puzzle could not be solved")

Or SolvingFailureException.

Do not let improper end conditions slip through, fail loudly (the caller can catch the exception but he cannot avoid the print, so this also empowers the caller)

Use standard terminology to improve understanding

# Go until our solve partial returns the 
# same puzzle as before

Applying a function until no change is seen amymore is called finding the fixed point of that function. State that in your code for the benefit of those familiar with the fixed point concept. You may write a fixed_point function to abstract more.

Avoid making a long list that is immediately trown away

filled_puzzles = list(itertools.product(*line_solutions))

You then iterate over filled_puzzles. But iteration does not need a list, being Iterable is sufficient (duck typing, it's all about supplying the right methods, you treat object by what they can do, not what they are). Remove list for a free speed-up.

bool

You do a pair of times:

return True if x else False

That is equivalent to:

return bool(x)

That is just simpler.

not

if x: return False
 return True

You do this while return not x would be simpler.

StackExchange Code Review Q#133992, answer score: 4