write this program using any language with backtracking. put comments so that I
ID: 3914230 • Letter: W
Question
write this program using any language with backtracking. put comments so that I can understand.
e) 105% Program 2 - Backtracking A polyomino (or an n-omino ) is a plane figure made up of n unit-size squares lined up on a grid. All of the 4-ominos are drawn below. Design a backtracking-based algorthm that runs in time 0(3) to generate all n-ominos, including all rotations and reflections. Extra Credit - Modify your algorithm to remove all rotations and reflections. Reminders -1) You need only complete three of the programs. 2) Each program that you submit is to be accompanied with a one or two page report describing your methodology that includes a discussion of your data structures and time complexity searchExplanation / Answer
The code show below is in Python
n=input()
r= range
M=lambda P : set(p-min(p.real for p in P)-min(p.imag for p in P)*1j for p in P)
A=[ ]
for i in r(1<<18) :
p=[k%3+k/3*1j for k in r(18) if i>>k&1]
C = set(P[ : 1])
for x in P : [any (p+1j**k in C for k in r(4))and C.add(p) for p in P]
p=M(P)
if not (C^P or p in A or len(P)-n):
for y in r(4) :print ' ' .join(' * '[y+x*1j in p] for x in r(6))
A+=[M([p*1j**k for p in P]) for k in r(4)]
These polyominos are represented as a set of complex numbers which are representing cells of polyomino. Just for example, consider M takes a polyomino and translates it so that the minimum real and the imaginary co-ordiantes are 0 and the outer loop iterates through all 2^18 3x6 grids generating a potential polyomino P and making sure P is connected and checking that P is not in the list A of previously found Polyominos and verifying that P has excatly n cells. Any new polyomino is added to A in all 4 rounds.
Below is the result for n=4:
1.**
*
*
2.*
**
*
3. *
**
*
4.*
*
**
5.*
**
*
6.****
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.