Columns puzzle game challenge solver - brainstorming

ParadigmShifter · Post by **ParadigmShifter** » Sun Feb 25, 2024 7:33 pm

While I wait to install 4.5GB of data just so I can build a C# console project template lol.

Aim is to generate a list of solvable board positions for columns, I'll start with solvable in 1 play at first I think.

For solvable in 1 move boards:

Without loss of generality I can assume the placed piece is in the middle of the board and that the piece that is placed has an A tile (tile types from A to E for now) at the bottom of the stack. There may be a requirement that there is an A tile adjacent (orthogonally or diagonally) to where the bottom tile of the placed piece lands (not 100% sure about that though - sounds reasonable enough though).

Other assumptions: tiles already on the board must connect with the middle column or another already placed tile and there must be no gaps between placed tiles unless they are adjacent to the middle column, so

Code: Select all

a|.a

is obviously not allowed (where the vertical bar is the middle column) since there is no way to clear the A tile on the right since it is not connected to the middle column or another piece.

With those constraints (and the board sizes I search can go from (actual board width in game - 1)*2 + 1 wide as long as only the (actual board width in game) is not exceeded during the search - that's to cope with "the first move need not be in the middle column" situation), I can then generate all possible tiles already placed possibilities and see if there is a piece which will clear the board or not.

So for boards with 0 tiles already placed, there is exactly one solution

Code: Select all

A
A
A

1 tile placed solvable positions with those constraints, 1 possibility

Code: Select all

A
A
A
a

where lowercase = tile on board at start, uppercase = winning move

2 tiles already placed, I make 4 possible solvable positions

Code: Select all

..A
..A
aaA + mirror image

Code: Select all

.A.
.A.
aAa

and

Code: Select all

A
A
A
a
a

3 tiles already on board, I make 6 possible solvable positions

Code: Select all

..A.
..A.
aaAa + mirror image

Code: Select all

..A
.aA
aaA + mirror image

Code: Select all

B
B
A
a
a
b

and finally

Code: Select all

B
A
A
a
b
b

I think there are 7 solvable positions for 4 pieces already placed... so I think I need a computer program to check that and then generate the possibilities now...

Once I have all solvable in 1 positions I have to build a tree of moves which can produce that position in 1 move to get all solvable in 2 board positions etc.

Wish me luck lol.

More info here: viewtopic.php?p=137819#p137819

Or has anyone got a better idea for how to generate solvable in X initial positions?

EDIT: I'm going to need a better idea because the number of possibilities blows up massively as you add more pieces even to a "solve in 1" scenario. If 10 pieces are already placed on the board there's lots of ways to place them, and then assuming each already placed piece can be anything (this is an invalid assumption but removing it requires checking the position is valid for each position) with 5 pieces there are nearly 10 million combinations

At least one must be of type A though so that reduces it a bit lol.

Maybe it needs C++ to get involved with it's std::next_permutation algorithm and for the speed... but no amount of speed will overcome the combinatorial explosion of possibilities.

No I'm not going to use a neural network lol

Maybe trying random positions and seeing if they are solvable (Monte Carlo) is a better idea... can hash the positions already tried. Most (nearly all really) random positions aren't solvable though.

EDIT2: Smaller board and less combinations of pieces to start with I think though. I once worked out the maximum number of tiles that need checking for this (was going to do that instead of a full evaluation, but it was complicated to code in ASM and a full eval was fast enough), that might be doable in a high level language on a PC.

Max number of places that must be checked where ### is placed piece

Code: Select all

x...x
xx.xx
xx#xx
xx#xx
xx#xx
xxxxx
x.x.x

where x might form part of a line of 3. That's only for the initial drop though once pieces fall that changes stuff (probs best to do a full eval then).