.data

	enter_n: .asciiz "Enter N: "
	array_msg: .asciiz "Board:\n"
	newline: .asciiz "\n"
	space: .asciiz " "
	.align 2
	array: .space 100
.text

	la $s7, array


	#cout enter N
	li $v0, 4
	la $a0, enter_n
	syscall
	#take n as input
	li $v0, 5
	syscall
	move $t0, $v0 #$t0 = n
	move $t1, $t0 #$t1 = n
	move $t8, $v0 #$t8 = n
	#calculate done which is 2^n - 1
	li $t2, 2
	li $t3, 1
	calculate_done:
		mult $t3, $t2
		mflo $t3
		sub $t1, $t1, 1
		bne $t1, 0, calculate_done

	mult $t0, $t0
	mflo $t1 #$t1 = $t0 * $t0

	#$t3 = done = 2^n - 1
	sub $t3, $3, 1

	#Now Initilaize ld, rd, col = 0
	li $s0, 0 #$s0 = ld
	li $s1, 0 #s1 = col
	li $s2, 0 #s2 = rd

	li $t5, 0 #$t5 = row
	li $t6, 0 #$t6 = column

	innerRecurse:
		beq $s1, $t3, allocate_queens #if col = done
		#poss = $s3
		or $s3, $s0, $s2
		or $s3, $s3, $s1
		xor $s3, $s3, 1

		and $s4, $s3, $t3 #poss & done
		beq $s4, 1, while
		while:
			#bit = s6
			#-poss = s5
			sub $s5, $s3, $zero
			and $s6, $s3, $s5 #var bit = poss $ -poss
			sub $s3, $s3, $s6
			#ld | bit >> 21
			or $s0, $s0, $s6
			srl $s0, $s0, 1
			#col | bit
			or $s1, $s1, $s6
			#rd | bit << 1
			or $s2, $s2, $s6
			sll $s2, $s2, 1

			#calculate and column
			#Reset row
			mult $t1, $t5 #t1 = n*n |  #t5 = row
			mflo $t7
			add $s7, $s7, $t7

			set_row:
				sw $zero, ($s7)
				add $s7, $s7, 4
				sub $t8, $t8, 1
				bnez $t8, set_row

			la $s7, array
			li $t2, 0
			move $t9, $s1 #s1 = col
			shift_col:
				add $t2, $t2, 1
				srl $t9, $t9, 1
				bnez $t9, shift_col
			#subtract from n then $t2 = col
			sub $t2, $t0, $t2 #t2 = col
			mult $t5, $t0 #i * cols
			mflo $a1
			add $a1, $a1, $t2
			mult $a1, $t0
			mflo $a1
			li $a3, 1
			sw $a3, array($a1)
			#increment row
			add $t5, $t5, 1
			move $t8, $t0
			jal innerRecurse

			and $s4, $s3, $t3 #poss & done
			beq $s4, 1, while








	allocate_queens:
		j print_array_adjust

	print_array_adjust:
		li $v0, 4
		la $a0, array_msg
		syscall
		mult $t0, $t0
		mflo $t3 #$t3 = n * n (counter)
		la $t5, array
		li $t4, 0
		move $t6, $t0
		j print_array
	print_array:
		li $v0, 1
		lw $a0, ($t5)
		syscall
		li $v0, 4
		la $a0, space
		syscall
		add $t4, $t4, 1
		beq $t4, $t6, new_line
		j continue
		new_line:
			li $v0, 4
			la $a0, newline
			syscall
			li $t4, 0
		continue:
		add $t5, $t5, 4
		sub $t3, $t3, 1
		bnez $t3, print_array



	exit:
		li $v0, 10
		syscall