Crossword puzzle

Backtracking in Go

Problem Statement

A 10 x 10 Crossword grid is provided to you, along with a set of words (or names of places) which need to be filled into the grid. Cells are marked either + or -. Cells marked with a - are to be filled with the word list.

In essence we are left with a two dimensional slice and a list of words to fill in the blank spaces - of the []slice.

Crossword Puzzle

Considerations

The Crossword Puzzle problem is an algorithmic problem that involves filling in a grid with words, given a set of clues. The grid is represented as a two-dimensional array of cells, each of which can contain a letter or a blank. The clues are given in the form of a list of words, each of which must be placed in the grid in a contiguous manner.

The objective of the problem is to find a placement of the words in the grid that satisfies all of the clues.

There are a number of different algorithms that can be used to solve the Crossword Puzzle problem. One common approach is to use a backtracking algorithm.

Backtracking algorithm

Backtracking algorithms work by trying different possible placements of the words in the grid, and backtracking when they reach a dead end. This approach is typically quite efficient, but it can be slow for large grids or for grids with many clues.

1. Check if there are any words left in the list.
2. Get the first word in the list and separate it from the rest of the words.
3. Create a copy of the current crossword puzzle.
4. Loop over the grid, checking each cell to see if it is a blank space or if the first character in the current word is equal to the first character in the cell.
5. If the cell is a blank space or if the characters match, then copy the current grid state into the copied grid.
6. Call the function fillInRow to try to place the current word in the blank spaces there are in the current row.
7. If placement is successful, then update the copied grid with the new row.
8. Otherwise call the function fillInColumn to try to place the current word into the blank spaces there are in the current column.
9. If the function is successful, then update the copied grid with the new column.
10. Recursively call itself with the copied grid and the rest of the words.
11. If the function returns a solved puzzle, then return the solved puzzle. Otherwise, return the current crossword puzzle.

Crossword Puzzle Algorithm

Backtracking Algorithm Implementation in Go

Resources

Hackerrank solution by kheraankit

Google Bard Conversation helped me order my ideas