How do I train a bot to solve Katona style problems?

Question

Cognitive psychology is researched since the 1940s. The idea was to understand human problem solving and the importance of heuristics in it. George Katona (an early psychologist) published in the 1940s a paper about human learning and teaching. He mentioned the so-called Katona-Problem, which is a geometric task.

Squares

Katona style problems are the ones where you remove straws in a given configuration of straws to create n unit squares in the end. In the end, every straw is an edge to a unit square. Some variations include 2x2 or 3x3 sizes of squares allowed as well as long as no two squares are overlapping, i.e. a bigger square 2x2 can't contain a smaller square of size 1x1. Some problems use matchsticks as a variation, some use straws, others use lines. Some variations allow bigger squares to contain smaller ones, as long as they don't share an edge viz. https://puzzling.stackexchange.com/questions/59316/matchstick-squares

• Is there a way we can view it as a graph and removing straws/matchsticks as deleting edges between nodes in a graph?

• If so, can I train a bot where I can plugin some random, yet valid conditions for the game and goal state to get the required solution?

Edit #1: The following problem is just a sample to show where I am getting at. The requirement for my game is much larger. Also, I chose uninformed search to make things simpler without bothering about complex heuristics and optimization techniques. Please be free to explore ideas with me.

Scenario #1:

Consider this scenario. In the following diagram, each dashed line or pipe line represents a straw. Numbers and alphabet denote junctions where straw meet. Let's say, my bot can explore each junction, remove zero, one, two, three or four straws such that resultant state has

• no straw that dangles off by being not connected to a square.
• a small mxm square isn't contained in a larger nxn square (m<n)
• Once straw is removed, it can't be put back.

Initial configuration is shown here. I always need to start from top left corner node P and optimization... the objective is to remove straws in minimum hops from node to node using minimum number of moves, by the time goal state is reached.

       P------Q------R------S------T
       |      |      |      |      |
       |      |      |      |      |
       E------A------B------F------G
       |      |      |      |      |
       |      |      |      |      |
       J------C------D------H------I
       |      |      |      |      |
       |      |      |      |      |
       K------L------M------N------O
       |      |      |      |      |
       |      |      |      |      |
       U------V------W------X------Y

Goal 1 : I wish to create a large 2x2 square.

At some point during, say BFS search (although it could be any uninformed search on partially observable universe i.e. viewing one node at a time), I could technically reach A, blow out all edges on A to create the following.

       P------Q------R------S------T
       |             |      |      |
       |             |      |      |
       E      A      B------F------G
       |             |      |      |
       |             |      |      |
       J------C------D------H------I
       |      |      |      |      |
       |      |      |      |      |
       K------L------M------N------O
       |      |      |      |      |
       |      |      |      |      |
       U------V------W------X------Y

That is one move.

Goal 2 : I want to create a 3x3 square instead.

I can't do that in one move. I need the record of successive nodes to be explored and then possibly backtrack to given point as well if the state fails to produce desired result. Each intermediate state might produce rectangles which are not allowed (also, how would one know how many more and which straws to remove to get to a square) or dangle a straw or worse get stuck in an infinite loop as I can choose to not remove any straw. How do I approach this problem?

#Edit 2:

For validation, figures 3, 4 and 5 are given below.

       P------Q------R------S------T
       |             |      |      |
       |             |      |      |
       E      A      B------F      G
       |             |      |      |
       |             |      |      |
       J------C------D------H      I
       |      |      |      |      |
       |      |      |      |      |
       K------L------M------N      O
       |      |      |      |      |
       |      |      |      |      |
       U------V------W------X      Y

The above figure (3) is invalid as we can't have dangling sticks TG,GI etc.

       P------Q------R------S------T
       |      |                    |
       |      |                    |
       E------A                    G
       |                           |
       |                           |
       J                           I
       |                           |
       |                           |
       K                           O
       |                           |
       |                           |
       U------V------W------X------Y

The above figure (4) is invalid as we can't have overlapping squares

       P------Q------R      S      T
       |             |             
       |             |            
       E      A      B------F------G
       |             |      |      |
       |             |      |      |
       J------C------D------H------I
       |      |      |      |      |
       |      |      |      |      |
       K------L------M------N------O
       |      |      |      |      |
       |      |      |      |      |
       U------V------W------X------Y

Figure (5) is valid configuration.

Answer 1

Your intuition is right: this is fundamentally a problem for combinatorial search.

You're also right that problems are created by the fact that not every move is valid at state. To fix this, you need to add a function that can determine whether a given state is valid or not, in addition to the usual function that checks whether it is your goal state or not. Before adding each node to the queue of your search algorithm, check whether it is a valid state. If it isn't, don't add it.

The second issue you raise is that your search might enter an infinite loop. Since it is possible to remove zero edges from a state, this is a serious concern. There are two approaches to solving this. First, you can try storing all states that you have already visited in a fast data structure like a Hash Table. Before adding a node to your queue, check if it's already been processed. If it has been, don't add it. This may work, but the memory requirements grow exponentially in the number of moves required for a solution. It's sometimes worth it, but I think you can likely skip it for this problem.

A better approach if you're worried about speed is to switch your algorithm to something like iterative deepening, which has the good properties of BFS, but with much lower memory requirements; or to A* search if you can come up with an admissible heuristic for your domain (a good starting point: counting the number of junctions you'd need to remove sticks from to finish, if the robot could teleport, would be admissible).

Hope this helps!

Edit: Here's some pseudo-code for filtering out invalid moves:

function valid_state(State s){
    for stick in s.remaining_sticks:
        if stick is vertical:
           1. let side = walk up from the middle of stick until it becomes possible to turn right.
           2. let side += walk down from the middle of stick until it becomes possible to turn right.
           3. From the first junction above stick where we can turn right, try to walk *side* steps to the right.
           4. Then try to walk side steps down.
           5. Then try to walk side steps left.
           6. Repeat previous 5 steps but for the nearest junctions where we can turn left instead of right.
        else:
           Do exactly what's in the if above, but substitute "left" for "up" and "right" for "down".      
    if we could walk in a square successfully for every stick, this is a valid state, so return true. Otherwise, return false.     
}