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.
  1. Prepare
  2. Algorithms
  3. Recursion
  4. Crossword Puzzle
  5. Discussions

Crossword Puzzle

Sort by

recency

|

202 Discussions

|

  • Johnson98
     + 0 comments

    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.

  • xinyangchen4
     + 0 comments

    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.

  • er_anshulyadav
     + 0 comments

    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

  • idavidmiller1985
     + 0 comments

    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.

  • nasirdaudahmad
     + 1 comment
    def crosswordPuzzle(crossword, words):
    # Write your code here
    solSteps=[]
    words = words.split(';')
    for i in range(len(crossword)):
       
        for j in range(len(crossword[i])):
            if crossword[i][j]=='-':
                if j<len(crossword[i])-1 and crossword[i][j+1]=='-' and (crossword[i][j-1]!='-' and j>0 ):
                    k=0
                    while crossword[i][j+k]=='-':
                       if j+k==9:
                           k+=1
                           break
                       k+=1
                    solSteps.append("h"+str(i)+str(j)+str(k))  
                elif j==0 and crossword[i][1]=='-':
                    k=0
                    while crossword[i][k]=='-':
                   
                       if k==9:
                           k=10
                           break
                       k+=1
                    solSteps.append("h"+str(i)+str(j)+str(k))
                elif  i<len(crossword)-1 and i> 0 and crossword[i+1][j]=='-' and crossword[i-1][j]!='-':
                    k=0
                    for x in range(i,len(crossword)):
                        if crossword[x][j]!='-':
                           break
                        k+=1
                    solSteps.append("v"+str(i)+str(j)+str(k))    
                elif  i== 0 and crossword[1][j]=='-':
                    k=0
                    for x in range(i,len(crossword)):
                        if crossword[x][j]!='-':
                           break
                        k+=1
                    solSteps.append("v"+str(i)+str(j)+str(k))    
    def canFillWord(word,blankword):
        orientation,row,col,size = blankword[0],blankword[1],blankword[2],blankword[3:]
        row,col,size = int(row),int(col),int(size)
        if len(word)!= size :
            return False
        if orientation=='v':
            for r in range(row, row+len(word)):
                if crossword[r][col]!="-" and crossword[r][col]!=word[r-row]:
                    return False
            for r in range(row, row+len(word)):
                if crossword[r][col]=="-" or crossword[r][col]==word[r-row]:
                    l=list(crossword[r])
                    l[col]=word[r-row]                
                    crossword[r]= "".join(l)
        if orientation=='h':
            for c in range(col, col+len(word)):
                if crossword[row][c]!="-" and crossword[row][c]!=word[c-col]:
                    return False
            l=list(crossword[row])
            for c in range(col,col+len(word)):
                if crossword[row][c]=="-" or crossword[row][c]==word[c-col]:
                    l[c] = word[c-col]
            crossword[row]="".join(l)
        return True    
    def unFill(word,blankword):
       
        orientation,row,col,size = blankword[0],int(blankword[1]),int(blankword[2]),int(blankword[3:])
        if orientation=='v':
            for r in range(row, row+len(word)):
                if crossword[r][col]==word[r-row]:
                    l=list(crossword[r])
                    l[col]="-"                
                    crossword[r]= "".join(l)
        if orientation=='h':
            l=list(crossword[row])
            for c in range(col,col+len(word)):
                if  crossword[row][c]==word[c-col]:
                    l[c] = "-"
            crossword[row]="".join(l)
           
    def solve(words,solSteps,i=0,k=0,done=[]):
        
        if len(done) == len(words):
            
            return crossword
       
        if canFillWord(words[i],solSteps[k]):
            
            if  words[i] not in done:
                if k < len(solSteps)-1:
                    k+=1
                done.append(words[i])
               
            
            i=0
           
            return solve(words,solSteps,i,k,done)
        else:
           
            if i < len(words)-1:
                i+=1
            else:
                i=0
               
                if done:
                    w = done[len(done)-1]
                    
                    for x in range(len(words)):
                        if len(words[x])==len(w) and words[x]!=w:
                            i = x
                            unFill(done[len(done)-1], solSteps[k-1])
                            
                            del done[len(done)-1]
                            if done:
                                
                                canFillWord(done[len(done)-1],solSteps[len(done)-1])
                            break
                    k = len(done)
                    print(words[i],solSteps[k])

                   
               
            return solve(words,solSteps,i,k,done)
    return solve(words,solSteps,i=0,k=0,done=[])