We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Recursion
- Crossword Puzzle
- Discussions
Crossword Puzzle
Crossword Puzzle
Sort by
recency
|
202 Discussions
|
Please Login in order to post a comment
This is my solution to the Crossword Puzzle challenge. I thought I’d share since I found a fun way to tackle it 🧩 I started by creating a 10x10 grid copy and using a backtracking approach to place each word. First, I split the input words and tried placing them one by one, either horizontally or vertically, in the grid’s free spaces (‘-’). If a word didn’t fit without conflicting with existing letters, I’d backtrack and try a different spot or orientation. Here’s a snippet of how I checked if a word can fit:
def canPlaceWord(grid, word, row, col, direction): if direction == 'H': # Horizontal if col + len(word) > 10: # Check bounds return False for i in range(len(word)): if grid[row][col + i] != '-' and grid[row][col + i] != word[i]: return False return True else: # Vertical if row + len(word) > 10: return False for i in range(len(word)): if grid[row + i][col] != '-' and grid[row + i][col] != word[i]: return False return True
Then, I’d place the word, update the grid, and move to the next word, backtracking if I hit a dead end. It took a bit of trial and error, but it felt so rewarding to solve this crossword just like cracking a real puzzle. 📰 I’ve always loved crosswords, and this challenge reminded me how much fun word puzzles can be. As I mentioned, I’ve always been into word puzzles. lately, I’ve been solving the Letter Boxed puzzle from the New York Times each day. It’s become a daily fun routine, and whenever I get stuck or want to double-check my answers at letterboxedanswer.net as they posts clean and spoiler-free solutions. It keeps the streak going without totally giving the game away, which I really appreciate.
First, find all horizontal and vertical blank positions. At each recursion step, take one word from the list, and find the first blank that matches the word length and partially filled letters. Fill the word in your chosen blank, and solve the recursive problem removing the current blank and word; if this yields a successful solution, then this is the answer; otherwise, try the same chosen blank with the next possible word, and so on iteratively. Base cases are the following: if no blank remains but some words are not used, then return false/empty; if not any word matches the chosen blank, return false/empty; if all blanks are filled and no word is left, return the current puzzle.
Easy DFS with backtracking, had to do to refresh the concept or to get involve in brain tickling, here my solution c++ with explanation - 200 lines of self code
https://gist.github.com/yadav26/c0b561d864f8cd0427398726e21056c3
Just like in life, in crossword puzzles, it's not about having an endless supply of words, but making the most out of what you have - a lesson in frugality.