How do I train a bot to solve Katona matchstick problems? | Artificial intelligence
Katona style matchstick problems are the ones where you remove matchsticks in a given configuration of matchsticks to create n unit squares in the end. In the end, every matchstick is an edge to a unit square. Some variations include 2×2 or 3×3 sizes of squares allowed as well as long as no two squares are overlapping, i.e. a bigger square 2×2 can’t contain a smaller square of size 1×1. Some variations allow bigger square to contain smaller one as long as they don’t share an edge viz. https://puzzling.stackexchange.com/questions/59316/matchstick-squares
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? Please explain in terms of a reflex agent or a learning agent.
I am more interested in how a state is represented. My approach is graph based. Please let me know how to handle the general cases. I am willing to provide a list of related problems if necessary.
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
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.
0------0------0------0------0 | | | | | | | | | | 0------A------0------0------0 | | | | | | | | | | 0------0------0------0------0 | | | | | | | | | | 0------0------0------0------0 | | | | | | | | | | 0------0------0------0------0 Goal 1 : I wish to create a large 2×2 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.
0------0------0------0------0 | | | | | | | | 0 A 0------0------0 | | | | | | | | 0------0------0------0------0 | | | | | | | | | | 0------0------0------0------0 | | | | | | | | | | 0------0------0------0------0 That is one move.
Goal 2 : I want to create a 3×3 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?