Table of contents
As a weekend project I thought of solving LinkedIn’s Queens game programmatically. (Well idea was to make it solve using ChatGPT, but too many un-knows and thought of solving using classic, vanilla backtracking)
For those of you who haven't played (or don't even know) Queens game:
How to play
Goal: Place exactly 1 Q in each row, column, and color region.
Rule: Q cannot touch each other, not even diagonally.
The idea was:
Take a screenshot containing the puzzle
Our code should automatically detect the puzzle grid
Crop or rebuild the puzzle cleanly
Convert the puzzle to 2D array
(solve the classic n-queens problem using backtracking)
Add/Modify the Queens constraints to the N Queens problem
Using the solution, regenerate the image with Queens placed
Enter OpenCV: Detecting and Processing the Puzzle Image
I knew the first step was to process the puzzle image using OpenCV. I have zero to none knowledge in OpenCV, so I started with basic questions to GPT like:
How to load image
import cv2 as cv
import numpy as np
# Reading an image
original = cv.imread("<file_name">)
cv.imshow("original", original)
How to draw a line, circle, rectangle, text on the same image
# Drawing a line
line = cv.line(original, (original.shape[1]//2, original.shape[0]//2), (0,0) , (0,255,0), thickness=2)
cv.imshow("line", line)
# Drawing other shapes
circle = cv.circle(line, (line.shape[1]//2, line.shape[0]//2), 50, (0,0,255), thickness=2)
rect = cv.rectangle(circle, (10,10), (circle.shape[1]//2, circle.shape[0]//2), (255,0,0), thickness=2)
text = cv.putText(rect, "Hi", (rect.shape[1]//2, rect.shape[0]//2), cv.FONT_HERSHEY_SIMPLEX, 1, (255,255,255), thickness=2)
cv.imshow("all shapes", text)
Cropping image
# its essentially selecting the pixels we need from the entire image
cropped = original[0:original.shape[1]//2, 0:original.shape[0]//2]
cv.imshow("cropped", cropped)
How to detect contours
by default OpenCV reads images as BGR, as opposed to traditional RGB
# Its best to convert image to grayscale
# and add a bit of blur for better contour detections
# since our image is mostly a grid we dont need blur
# by default OpenCV reads images as BGR
# as opposed to traditional RGB
gray = cv.cvtConvert(original, cv.COLOR_BGR2GRAY)
contours, _ = cv.findContours(gray, cv.RETR_TREE, cv.CHAIN_APPROX_NONE)
Combining the basics
Read the image
Convert to Grayscale
Find contours, sort them and pick the largest (I picked second largest since the 1st was always the bounding box of original image)
Crop to just the puzzle
Again find contours, because now our image only contains the puzzle grid
Get the number of cells
Iterate over each cell and take average color and assign a number for each color
original = cv.imread(file_name)
cv.imwrite("solution/original.png", original)
gray = cv.cvtColor(original, cv.COLOR_BGR2GRAY)
contours, _ = cv.findContours(gray, cv.RETR_TREE, cv.CHAIN_APPROX_NONE)
contours = sorted(contours, key=cv.contourArea, reverse=True)
# fix the 1 here!!!
x, y, w, h = cv.boundingRect(contours[1])
# Crop the grid area from the image
grid = original[y:y+h, x:x+w]
cv.imwrite("solution/grid.png", grid)
gray = cv.cvtColor(grid, cv.COLOR_BGR2GRAY)
cv.imwrite("solution/gray-grid.png", gray)
contours, _ = cv.findContours(gray, cv.RETR_TREE, cv.CHAIN_APPROX_NONE)
contours = sorted(contours, key=cv.contourArea)
total_cells = len(contours) - 2
grid_size = int(math.sqrt(total_cells))
if total_cells != grid_size**2:
print("Unable to detect full grid! Aborting")
cell_width = w // grid_size
cell_height = h // grid_size
colors = []
board = []
color_index = 1
color_map = {}
reverse_color_map = {}
padding = 10
for i in range(grid_size):
row = []
for j in range(grid_size):
# Calculate cell coordinates
cell_x = j * cell_width
cell_y = i * cell_height
padding = 15
cell = grid[cell_y+padding:cell_y+cell_height-padding, cell_x+padding:cell_x+cell_width-padding]
# Get the average color of the cell
avg_color = cell.mean(axis=0).mean(axis=0)
avg_color = avg_color.astype(int)
avg_color = tuple(avg_color)
# Append the color in RGB format
# row_colors.append(tuple(avg_color))
if avg_color not in color_map:
color_map[avg_color] = str(color_index)
reverse_color_map[str(color_index)] = avg_color
color_index += 1
row.append(color_map[avg_color])
board.append(row)
| Original | Grid | Grayscale |
 |  |  |
Board
|1,1,1,1,1,1,1,1,2,2|
|1,1,3,4,4,4,4,2,2,5|
|1,3,3,3,4,4,2,2,5,5|
|1,1,3,6,4,2,2,7,7,7|
|1,1,6,6,2,2,8,8,8,7|
|1,1,6,2,2,8,8,8,8,7|
|1,1,2,2,7,8,8,9,8,7|
|1,2,2,7,7,7,9,9,9,7|
|2,2,10,10,7,7,7,9,7,7|
|2,10,10,7,7,7,7,7,7,7|
Solving the N-Queen problem
Here is the solution to classic N Queen problem using backtracking generated using ChatGPT
def is_safe(board, row, col, n):
# Check this row on left side
for i in range(col):
if board[row][i] == 'Q':
return False
# Check upper diagonal on left side
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 'Q':
return False
# Check lower diagonal on left side
for i, j in zip(range(row, n), range(col, -1, -1)):
if board[i][j] == 'Q':
return False
return True
def solve_nqueens_util(board, col, n):
# If all queens are placed
if col >= n:
return True
# Consider this column and try placing queens in all rows one by one
for i in range(n):
if is_safe(board, i, col, n):
board[i][col] = 'Q'
# Recur to place the rest of the queens
if solve_nqueens_util(board, col + 1, n):
return True
# If placing queen at board[i][col] doesn't lead to a solution, then backtrack
board[i][col] = '.'
return False
def solve_nqueens(n):
board = [['.' for _ in range(n)] for _ in range(n)]
if not solve_nqueens_util(board, 0, n):
return "No solution exists"
return board
def print_board(board):
for row in board:
print(" ".join(row))
# Example usage:
n = 8
solution = solve_nqueens(n)
if solution != "No solution exists":
print_board(solution)
else:
print(solution)
Adding constraints for Queens
Our new is_safe method becomes:
def is_safe(original_board, board, row, col, queens_in_colors, n):
# Check this row on left side
for i in range(col):
if board[row][i] == 'Q':
return False
# Check upper diagonal on left side
if col - 1 >= 0 and row - 1 >= 0:
if board[row-1][col-1] == "Q":
return False
if col - 1 >= 0 and row + 1 < n:
if board[row+1][col-1] == "Q":
return False
for i in range(row):
if board[i][col] == "Q":
return False
# same color shouldnt have one
current_color = original_board[row][col]
if queens_in_colors[current_color]:
return False
return True
Re-generating the Image with the Solution
Finally, its time to regenerate the image with Q placed on the cells
solved_board = solve_n_queens(board)
if len(color_map) != grid_size:
print("Too many colors detected! Aborting")
# recreating grid
output_image = np.ones((h,w,3), dtype="uint8")
border_size = 1
letter_height = 10
for i in range(grid_size):
for j in range(grid_size):
cell_x = j * cell_width
cell_y = i * cell_height
color_pick = reverse_color_map.get(board[i][j])
color = (int(color_pick[0]), int(color_pick[1]), int(color_pick[2]))
output_image = cv.rectangle(output_image, (cell_x + border_size, cell_y + border_size), (cell_x + cell_width - border_size, cell_y + cell_height - border_size), color, thickness=-1)
output_image = cv.line(output_image, (cell_x, cell_y), (cell_x + cell_width, cell_y ), (0,0,0), thickness=1)
if solved_board[i][j] == "Q":
output_image = cv.putText(output_image, "Q", (cell_x + cell_width // 2 - letter_height, cell_y + cell_height // 2 + letter_height), cv.FONT_HERSHEY_COMPLEX, 1, (0,0,0), lineType=cv.LINE_AA, thickness=2)
cv.imwrite("solution/solve.png", output_image)
Final Output
