Star Battle solver

Background
Star Battle is a grid-based logic puzzle. You are given a SxS square grid divided into S connected regions, and a number N. You must find the unique way to place N*S stars into the grid such that:

Every row has exactly N stars.
Every column has exactly N stars.
Every region has exactly N stars.
No two stars are horizontally, vertically, or diagonally adjacent.
If you would like more information:

Star Battle rules and info
YouTube tutorial and written tutorial of solving Star Battle puzzles by hand
There are many Star Battle puzzles available on Grandmaster Puzzles. Just be aware that some are variants that follow different rules.
Challenge
Write a program to solve a Star Battle puzzle in a reasonable amount of time. There's no strict time requirement, but you should run your program through to completion for at least one (N, S) = (2, 10) puzzle for it to count as a solution.

Feel free to use whatever input/output format is most convenient for you. In the examples below, first N is given, then the SxS grid is given, with each cell labeled by a letter corresponding to its region. The output is . for empty cells and * for cells containing a star. But you don't have to use this format.

Example input (N, S) = (1, 6)
1
AABBCC
AABCCC
AABCCC
DDBBEE
DDBBEF
DDBBFF
Source

Example output
..*...
*.....
...*..
.....*
.*....
....*.
Challenge input (N, S) = (2, 10)
2
AAAABBCCCC
ADAABBBCBB
ADDBBBBBBB
DDDDBEEEEB
DDBBBBBBEB
FFFFGGHHHH
FIFFGGGHGG
FIIGGGGGGG
IIIIGJJJJG
IIGGGGGGJG
by Bryce Herdt

Bonus input (N, S) = (3, 15)
3
AAAAABBBBBCCCCC
ADDDDBBBBBEEECC
ADDDDDDBEEEEEEC
ADDDFDDBEEGEEEC
ADDFFFHHHGGGEEC
AAAFFFHHHGGGCCC
AAHHFHHIHHGHCCC
AAAHHHIIIHHHJJJ
AAAKKKIIIKKKKLJ
AAAMKKKIKKKMLLJ
NNNMMKKKKKMMLLJ
NNNOMMMMMMMLLLJ
NOOOOMMMMMOOLLL
NOOOOOMMMOOOLLL
NNOOOOOOOOOOLLL

Solution


from copy import deepcopy
def getInput():
    try:
        n = int(raw_input())
    except EOFError:
        print "data is empty"
    grid = []
    s = 0
    while(True):
        try:
            row = []
            rowstr = raw_input()
            for c in rowstr:
                charnum = ord(c)-64
                row.append(charnum)
                if charnum>s: s=charnum
            grid.append(row)
        except EOFError:
            break
    return n,s,grid

def combinations(v, st, n, k, maxk, c):
    if k>maxk:
        c.append(v[1:maxk+1])
        return
    for i in range(st, n+1):
        v[k] = i
        combinations(v, i+1, n, k+1, maxk, c)

def getCombinations(n, k):
    v=[0]*100
    combs=[]
    combinations(v, 0, n-1, 1, k, combs)
    for comb in combs:
        for i in range(k-1):
            if comb[i]+1==comb[i+1]:
                combs.remove(comb)
                break
    return combs

def recsolve(n,s,grid,combs,row,invalcols,invalsects,count,placed):
    if row==s:
        return placed
    for comb in combs:
        valid = True
        invalcols2 = invalcols[:]
        invalsects2 = invalsects[:]
        count2 = deepcopy(count)
        for c in comb:
            #check collumn
            if c not in invalcols2:
                #check section
                if grid[row][c] not in invalsects2:
                    #check diagonals
                    if placed!=[]:
                        if c not in [x-1 for x in placed[len(placed)-n:]]+ \
                                    [x+1 for x in placed[len(placed)-n:]]:
                            valid = valid and True
                        else: valid = False
                    else:
                        valid = valid and True
                else: valid = False
            else: valid = False
            if valid:
                count2[c][0] += 1
                count2[grid[row][c]-1][1]+=1
                if count2[c][0]>=n:
                    invalcols2.append(c)
                if count2[grid[row][c]-1][1]>=n:
                    invalsects2.append(grid[row][c])
            else:
                break
        if valid:
            ans=recsolve(n,s,grid,combs,row+1,invalcols2,invalsects2,count2,placed+comb)
            if ans!=None: return ans
    return None

def solve(n,s,grid):
    combs = getCombinations(s,n)
    count = [[0,0] for i in range(s)]
    return recsolve(n,s,grid,combs,0,[],[],count,[])

def outputAns(n,s,ans):
    rows = [ans[i*n:(i+1)*n] for i in range(s)]
    for row in rows:
        outrow = ''
        for i in range(s):
            if i in row:
                outrow+='*'
            else:
                outrow+='.'
        print outrow

n,s,grid = getInput()
ans=solve(n,s,grid)
outputAns(n,s,ans)