Click here to Skip to main content
15,894,017 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
Ada took a standard chessboard with 8 rows (numbered 1 through 8) and 8 columns (numbered 1 through 8); let's denote a cell in row r and column c by (r,c). Then, Ada placed a bishop in a cell (r0,c0)

; it is guaranteed that this cell is black. Ada's goal is to move the bishop in such a way that it visits all black cells.

Remember that a bishop is a piece that moves diagonally ― formally, the bishop may move from a cell (rs,cs)
to a cell (rt,ct) if and only if either rs+cs=rt+ct or rs−cs=rt−ct. In such a move, the bishop visits all cells between (rs,cs) and (rt,ct)

on this diagonal (inclusive).

Help Ada find a sequence of at most 64
moves for the bishop such that when the bishop follows this route, it visits all black cells on the chessboard. Note that each cell may be visited multiple times and it is not necessary to return to the starting point.


What I have tried:

from collections import deque
moves=[[0 for i in range(8)] for j in range(8)]
count=0
x=[-1,-1,1,1]
y=[-1,1,1,-1]
xq=deque()
yq=deque()
def is_safe(x,y):
	return (x>=0 and x<=7 and y>=0 and y<=7)
xq.append(4)
yq.append(5)
while(len(xq)>0):
	count+=1
	xx=xq.popleft()
	yy=yq.popleft()
	if count>=128:
		break

	
	moves[xx][yy]+=1

	for i in range(4):
		xx=xx+x[i]
		yy=yy+y[i]
		if is_safe(xx,yy):
			xq.append(xx)
			yq.append(yy)

print(moves)


I dont know if I am doing right.How to approach this problem
Posted
Updated 8-Mar-20 4:32am
v3
Comments
Patrice T 15-Mar-20 11:15am    
Do you get a correct answer with the list of moves ?

1 solution

I have spent around a full day finding out solution for it ,
just do it for (1,1) and then it can be easily solved for other cases by moving your
bishop to ((r0+c0)//2,(r0+c0)//2) and then to (1,1) now print the same path as in case
of (1,1)
 
Share this answer
 
Comments
Patrice T 15-Mar-20 10:58am    
Is this supposed to be a solution ?
Member 14771956 15-Mar-20 11:07am    
any code for it?

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900