Loading [Contrib]/a11y/accessibility-menu.js
  1. CSPLib
  2. Problems
  3. prob079
  4. Models
  5. diagtoqueens.py

079: n-Queens Completion Problem and Excluded Diagonals n-Queens Problem

Download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#!/usr/bin/env python3
 
# program to convert from queens and ruled out diagonals to report stats and convert to dimacs
 
import sys
 
 
def An(n):
    assert( n % 6 == 1 or n % 6 == 5)
    res = []
    for i in range(n):
        res.append([i,(2*i)%n])
    return( res)
 
def Bn(n):
    assert( n % 6 == 1 or n % 6 == 5)
    res = []
    for i in range(n):
        res.append([(2*i)%n,i])
    return( res)
 
def timesn(n,q):
    return [q[0]*n,q[1]*n]
 
def plusqueen(q1,q2):
    return [q1[0]+q2[0],q1[1]+q2[1]]
 
def offsetqueens(n,offsetq,queens):
    return [plusqueen(timesn(n,offsetq),q) for q in queens]
 
q19col0 = [0,8]
q19col19 = [19,8]
q19row0 = [17,0]
q19row19 = [17,19]
q19rest = [[1,12],[2,17],[3,7],[4,10],[5,15],[6,1],[7,16],[8,13],[9,2],[10,6],[11,18],[12,3],[13,5],[14,11],[15,9],[16,14],[18,4]]
 
def max(numbers):
    assert(len(numbers) != 0)
    max=numbers[0]
    for i in range(1,len(numbers)):
        if numbers[i] > max:
            max=numbers[i]
    return max
 
def checkrowcols(Queens):
    if(Queens == []):
        return True
    n1 = len(Queens)
    n2 = max([q[0] for q in Queens] + [q[1] for q in Queens]) + 1
    if( n1 > n2):
        return False
    rowbits = [0 for i in range(n2)]
    colbits = [0 for i in range(n2)]
    for q in Queens:
        colbits[q[0]] = 1
        rowbits[q[1]] = 1
    return ( (len([1 for i in range(n2) if rowbits[i] != 0]) == n1) and
             (len([1 for i in range(n2) if colbits[i] != 0]) == n1) )
 
def checkdiags(Queens):
    if(Queens == []):
        return True
    n1 = len(Queens)
    n2 = max([q[0] for q in Queens] + [q[1] for q in Queens]) + 1
    if( n1 > n2):
        return False
    d1bits = [0 for i in range(2*n2)]
    d2bits = [0 for i in range(2*n2)]
    for q in Queens:
        d1bits[q[0]+q[1]] = 1
        d2bits[q[0]-q[1]+n2-1] = 1
    return ( (len([1 for i in range(2*n2) if d1bits[i] != 0]) == n1) and
             (len([1 for i in range(2*n2) if d2bits[i] != 0]) == n1) )
 
def checknoattack(Queens):
    return checkrowcols(Queens) and checkdiags(Queens)
 
### e.g. reduce3to2(7,[],[],[])
 
def reduce3to2(M3):
    n3=M3[0]
    P3=M3[1]
    m3=M3[2]
    C3=M3[3]
    R3=M3[4]
    assert len(C3) == len(R3), ("different numbers of rows and columns: ")
    assert m3 == len(C3)+len(P3), "m inconsistent with length of cols and preplaced queens"
    assert m3 <= n3, ("more queens to place than places to put them: " + str(m3) + " " + str(n3))
    if P3 or C3 or R3:
        ncheck = max([q[0] for q in P3] + [q[1] for q in P3] + C3 + R3)
        assert ncheck < n3, ("Row or column required more than input value of n")
    assert(checkrowcols(P3)), ("preplaced queens have two in same row or column: " + str(P3))
    Cprime = C3 + [q[0] for q in P3]
    Rprime = R3 + [q[1] for q in P3]
    assert len(set(Rprime)) == m3, "preplaced queen in one of required rows"
    assert len(set(Cprime)) == m3, "preplaced queen in one of required cols"
    if not checkdiags(P3):
        return [n3,P3]
    if n3%3 == 2:
        nprime = n3*2+1
    else:
        nprime = n3*2-1
    an = An(nprime)
    bn = Bn(nprime)
    qscol0 = [q for q in offsetqueens(nprime,q19col0,an) if q[0] not in Cprime]
    qsrow0 = [q for q in offsetqueens(nprime,q19row0,bn) if q[1] not in Rprime]
    qsrest = qscol0+qsrow0
    for qr in q19rest:
        qsrest += [q for q in offsetqueens(nprime,qr,an)]
    Cprime.sort()
    Rprime.sort()
    QC = [[i,2*Cprime[i]] for i in range(m3)]
    QR = [[2*Rprime[i],i] for i in range(m3)]
    result = P3
    result += offsetqueens(nprime,q19col19,QC)
    result += offsetqueens(nprime,q19row19,QR)
    result += qsrest
    assert(checknoattack(result)),("Bug: computed attacking set of queens: "+str(result))
    return [19*nprime+m3,result]
 
 
def reduce4to3(n4,m4,C4,R4,D4diff,D4sum):
    n3=n4*7-3
    m3=m4+len(D4diff)+len(D4sum)
    Qdiff = [ [6*n4-3-d,3*n4-1-2*d] for d in D4diff ]
    Qsum =  [ [2*n4-2-d,n4+2*d] for d in D4sum ]
    C3=[c+3*n4-2 for c in C4]
    R3=R4
    return [n3,Qdiff+Qsum,m3,C3,R3]
 
# Special case where all rows and columns allowed
def reducesimple4to3(M4Simple):
    n = M4Simple[0]
    Ddiff = M4Simple[1]
    Dsum = M4Simple[2]
    return reduce4to3(n,n,list(range(n)),list(range(n)),Ddiff,Dsum)
 
# Numbers as read from input file
# numbers[0] = n
# numbers[1] = maxdiags
# numbers[2,4,6 ... ] = diagonal, +n-1 for difference diagonals
# numbers[3,5,7... ] = 1 for sum diag, 0 for diff
 
def diagtosimple4(numdiags,numbers):
    n = numbers[0]
    maxdiags = numbers[1]
    assert numdiags <= maxdiags, "more diagonals requested than available in input"
    assert len(numbers) >= numdiags*2 + 2, "fewer diagonals than claimed"
    Ddiff=[]
    Dsum=[]
    for i in range(numdiags):
        d=numbers[i*2+2]
        direction=numbers[i*2+2+1]
        assert(direction == 0 or direction == 1)
        if direction == 1:
            Dsum.append(d)
        else:
            Ddiff.append(d-n+1)
    return [n,Ddiff,Dsum]
     
 
 
def reducesimple4to2(M4Simple):
    return reduce3to2(reducesimple4to3(M4Simple))
 
def printqueens2(M2):
    print("letting n = ",M2[0])
    print("letting init = ",M2[1])
 
def printqueensfromdiag(numdiags,numbers):
    printqueens2(reducesimple4to2(diagtosimple4(numdiags,numbers)))