This page looks best with JavaScript enabled

checkerboard & N queens

x*y checkerboard & N queens

naive back-track

 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

import copy

def upd_restrict(tup, restrict):
    r, c = tup
    re = copy.deepcopy(restrict)
    re['row'].add(r)
    re['col'].add(c)
    re['add'].add(r+c)
    re['sub'].add(r-c)
    return re

def chk_restrict(tup, restrict):
    r, c = tup
    if r in restrict['row'] or c in restrict['col'] or r+c in restrict['add'] or r-c in restrict['sub']:
        return False
    return True

def bt(picked, restrict, arr):
    # print(picked,restrict)
    if len(picked)<N:
        for i in range(len(arr)):
            if chk_restrict(arr[i], restrict):
                bt(picked+[arr[i]], upd_restrict(arr[i], restrict), arr[i+1:])
    else:
        re.append(picked[:])


re = []
N = 8
x, y = 8,8
restrict = {}
for key in ['row', 'col', 'add', 'sub']:
    restrict[key] = set()

bt([], restrict, [(i, j) for i in range(x) for j in range(y)])
print(re)
print(len(re))