#StackBounty: #algorithm #game #prolog Constraint solving CrossCells puzzle game solution

Bounty: 50

There’s a puzzle game called
CrossCells (not
affiliated; there’s also multiple other ones with the same kind of idea,
but slightly different layout and rule set) that I’ve been playing on
and off. After getting a bit frustrated with one puzzle (they’re
getting larger and larger and I’m not very methodical with solving them
anymore) I thought of what environment I’d use to solve them
automatically (brute force not being a great idea).

This is also kind of spoiler-ish for puzzle 25, though I’m not printing
the full solution, you’d have to run the code to see it.


I set up a quick hack in Prolog
(SWI Prolog using one of the
constraint solving modules; apt-get install swi-prolog should do the trick)
and wanted to get some feedback on the solution, especially regarding

  • whether this the go-to approach for this kind of puzzle, or whether a
    more simple approach would work too,
  • whether a different environment would be a much better match for the
    kind of problem (I’m not familiar enough with Prolog, but the
    documentation was enough to let me at least get this done in a matter
    of hours; I’d be more happy with, say, Java/Python/…, anything where
    I can still switch to an imperative mode for e.g. I/O).

For the specifics of the code also

  • how this could be shortened while still being readable. It took quite a
    while (after one failed attempt at expressing the equations) to
    actually write down the whole puzzle in a readable way. E.g. not
    having to write down all the variables explicitly in the goal and
    when invoking it would be fantastic.
  • Whether the equations could be more concise. I deliberately wrote them
    down row by row and column by column to be able to visually compare
    them with the game’s representation. But, that comes at the cost of
    additional variables (Nx) and screen space.
  • Printing and comparing the solution is cumbersome, any hints how this
    could be improved?
    Edit: The second goal solve now prints each row, yet I can’t think of a good way to truly show this as the original grid pattern, making comparing it with the real thing still a bit annoying. Still happy to find a better way!

Edit: Since there was no answer yet I trimmed it down a bit myself, the noise is manageable now, focus would be more on how the equations could be simplified even more.


Okay so the rules of the game for this particular puzzle:

screenshot of unsolved puzzle 25 of the game CrossCells

(Red was edited on top just in case.)

  • Each cell can be toggled on (highlighted in blue by default), toggled
    off (barely visible, same as the background basically) or undecided
    (what’s shown in the picture, dark gray). This corresponds to the
    “term” in the cell being part of the expression, not being part of the
    expression, or undecided. Only if all cells in the sequence are
    either on or off can the constraint be satisfied or not; if any cell
    is still in undecided state, the puzzle is not solved yet. (In the
    solution there’s no need to model the undecided state, we always
    assign either on or off to each cell.)
  • Precedence is the usual, except that there’s implied parentheses
    between each cell; e.g. the first row reads
    (((+ 1) + 2) * 4) + 2 = 4! If the first two cells were off, it
    would be essentially (((0) + 0) * 4) + 2 = 4 though.
  • Each column, row and sub-square can have a constraint. Those are
    always after all cells in the sequence / at the boundary of the
    square. In this one there’s 10 of those for columns and rows and one for
    the highlighted square (“[6] tiles”).
  • The constraints are either number of tiles allowed to be set in the
    sequence (“[1] tiles”) or the total of evaluating the arithmetic
    expression made up of the chosen cells (“24 total”).

Part of the problem of expressing this is that you can’t simply write
(for the first row) (1 * A + 2 * B) * 4 * C + 2 = 4 (given A-D as
integers between 0 and 1), because if e.g. “x4” is off, it’s simply not
part of the expression, instead the full expression would read
(+)1 + 2 ___ + 2 = 4 (not ((+)1 + 2) * 0 + 2 = 4).

(Hope I didn’t forget to explain anything, showing this interactively
would be a little bit easier.
Here’s one YouTube link;
of course there are others too and it might disappear.)


So the solution below

  • uses variables Bx as integers 0 or 1 to express whether a cell
    (numbered from top left to bottom right, row by row) is present or
    not,
  • uses variables Nx where necessary to deal with optional factors /
    “xA” cells (by, annoyingly, either constraining them to 1 if the corresponding value Bx isn’t on/0, or constraining them to their factor if Bx is on/1; I’d love to have a better way for this) – the goal factor abstracts out this pattern,
  • and finally simply lists the constraints row by row and column by column.

While puzzle25 computes the solution, solve (for the lack of a better name), prints the solution for a given puzzle goal (so solve(puzzle25). will solve it and show the solution), that’s already preparing for more puzzles to come.

:- use_module(library(clpfd)).

factor(B, N, Factor) :-
    B #= 0 #==> N #= 1,
    B #= 1 #==> N #= Factor.

puzzle25(Rows) :-
    Rows = [          [B1,  B2,  B3,  B4], %            =4
                      [B5,  B6,  B7,  B8], %            =5

            [B9, B10, B11, B12, B13, B14, B15, B16], % =24

                     [B17, B18, B19, B20], %            =2
                     [B21, B22, B23, B24] %             =6
            %          =6  =12  [1]   =6
            % and the inner block can only have 6 selected
           ],
    flatten(Rows, Flat),
    Flat ins 0..1,

    factor(B3, N3, 4),
    ((1 * B1) + (2 * B2)) * N3 + (2 * B4) #= 4,

    factor(B6, N6, 2),
    (2 * B5) * N6 + (2 * B7) + (1 * B8) #= 5,

    factor(B10, N10, 2),
    factor(B11, N11, 2),
    factor(B12, N12, 3),
    factor(B13, N13, 2),
    factor(B14, N14, 3),
    factor(B15, N15, 4),
    (1 * B9) * N10 * N11 * N12 * N13 * N14 * N15 + (8 * B16) #= 24,

    factor(B18, N18, 2),
    factor(B20, N20, 2),
    ((1 * B17) * N18 + (2 * B19)) * N20 #= 2,

    factor(B23, N23, 2),
    factor(B24, N24, 2),
    ((3 * B21) + (3 * B22)) * N23 * N24 #= 6,

    ((1 * B1) + (2 * B5)) * N11 + (1 * B17) + (3 * B21) #= 6,
    (2 * B2) * N6 * N12 * N18 + (3 * B22) #= 12,
    B3 + B7 + B13 + B19 + B23 #= 1,
    ((2 * B4) + (1 * B8)) * N14 * N20 * N24 #= 6,

    B1 + B2 + B3 + B5 + B6 + B7 + B11 + B12 + B13 + B17 + B18 + B19 #= 6.

solve(Puzzle) :-
    apply(Puzzle, [L]),
    flatten(L, M),
    label(M),
    forall(member(Row, L), write_term(Row, [nl(true)])).

I’m fairly certain this is correct, because the output works when put into the game and there’s only a single solution (which is what I’d expect from how the game is set up, multiple solutions would be more complicated for the player).


Get this bounty!!!

HackerEarth: Battle Of Bots 6: Draughts

Problem:

Sample Game

Draughts is a two player board game which is played on a 8X8 grid of cells and is played on opposite sides of the game-board. Each player has an allocated color, Red ( First Player ) or White ( Second Player ) being conventional. Players take turns involving diagonal moves of uniform game pieces in the forward direction only and mandatory captures by jumping over opponent pieces.

Rules:

  • Player can only move diagonally to the adjacent cell and in forward direction, if the diagonally adjacent cell is vacant.
  • A player may not move an opponent’s piece.
  • If the diagonally adjacent cell contains an opponent’s piece, and the cell immediately beyond it is vacant, the opponent’s piece may be captured (and removed from the game) by jumping over it in the forward direction only.
  • If a player made a jump, then its mandatory to keep on jumping as long as the jump is possible.
  • Player cannot move to the diagonally adjacent cell once the player made a jump.

The game will end when any of the players don’t have any move left. At the end of the game the player with majority of pieces will win.

We will play it on an 8X8 grid. The top left of the grid is [0,0] and the bottom right is [7,7].

Input:
The input will be a 8X8 matrix consisting only of 0o2. Then another line will follow which will contain a number –  1 or 2 which is your player id. In the given matrix, top-left is [0,0] and bottom-right is [7,7]. The x-coordinate increases from left to right, and y-coordinate increases from top to bottom.

The cell marked 0 means it doesn’t contain any stones. The cell marked 1 means it contains first player’s stone which is Red in color. The cell marked 2 means it contains second player’s stone which is white in color.

Output:
In the first line print the coordinates of the cell separated by space, the piece he / she wants to move.
In second line print an integer N, number of steps or jumps the piece will make in one move.
In the next N lines print the coordinates of the cells in which the piece will make jump.
You must take care that you don’t print invalid coordinates. For example, [1,1] might be a valid coordinate in the game play if [1,1] in diagonal to the piece in which is going to jump, but [9,10] will never be. Also if you play an invalid move or your code exceeds the time/memory limit while determining the move, you lose the game.

Starting state
The starting state of the game is the state of the board before the game starts.

0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 2 0 2 0 2 0 2
2 0 2 0 2 0 2 0

First Input
This is the input give to the first player at the start of the game.

0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 2 0 2 0 2 0 2
2 0 2 0 2 0 2 0
1
SAMPLE INPUT
0 1 0 1 0 1 0 1
1 0 1 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0
0 0 0 2 0 0 0 2
2 0 2 0 2 0 2 0
1
SAMPLE OUTPUT
2 5
2
4 3
6 1

Explanation

This is player 1’s turn, and the player will move the piece at [2,5] and will make two jumps. First jump will be at [4,3and second jump will be at [6,1]

After his/her move the state of game becomes:

0 1 0 1 0 1 0 1
1 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 2 0 2 0 2
2 0 2 0 2 0 2 0

This state will be fed as input to program of player 2.

Other valid move for the first player is

2 5
1
3 6

But the following are invalid moves.
Case 1:

2 5
1
4 3

Because after making a jump its possible to jump again and its mandatory to jump as long as its possible to jump.

Case 2:

2 5
2
4 3
5 4

Because after making a jump its invalid to move to diagonally adjacent cell.

Here is the code of the Random Bot.

Time Limit:1.0 sec(s) for each input file.
Memory Limit:256 MB
Source Limit:1024 KB

Solution

This is the solution submitted by me

Two player game program – e.g. TIC TAC TOE…

This is an abstract State class
public abstract class State {

// This method is abstract, the extending class has to give the implementation
// It will return a list of all the possible children from the current state.
public abstract List getChildren();
public abstract String getTurn();
public abstract void setTurn(String turn);

// Find out who is the winner from the current state.
public abstract String getWinner();

// Check if the game has been finished or not.
public abstract boolean isGameOver();

// I have given the implementation specifically for TIC-TAC-TOE.
// You can override this functionality in the extending class according to your game requirements.
//
// This function will give the score of the current state.
// Then you can compare it with its siblings to check which state will be better to move to..
//
public int minimax()
{

if(!getWinner().equals(""))
{
if("X".equalsIgnoreCase(getWinner()))
{
return 1;
}
if("O".equalsIgnoreCase(getWinner()))
{
return -1;
}
if("draw".equalsIgnoreCase(getWinner()))
{
return 0;
}
}
List children = getChildren();
if(getTurn().equals("X"))
{
int maxScore = -100;
for(State child : children)
{
int childScore = child.minimax();
if(childScore > maxScore)
{
maxScore = childScore;
}
}
return maxScore;
}
else
{
int minScore = 100;
for(State child : children)
{
int childScore = child.minimax();
if(childScore < minScore)
{
minScore = childScore;
}
}
return minScore;
}

}
}

Extend the above State class and give some implementations…as follows:
Lets assume the class to be TttState…
We’ll override the abstract methods of the parent class State..

Give a member variable that’ll hold the current state of your game…In my case, I have taken it as array..

// This variable is going to hold the current state of your game.
// It can be any depending on your game requirements...
private String state[][] = null ;

Give a copy constructor

public TttState(State x)
{
TttState tState = (TttState)x;
state = new String[3][3];
for(int i=0;i<=2; i++)
{
for(int j=0; j<=2;j++)
{
this.state[i][j]=tState.state[i][j];
}
}
this.turn = x.getTurn();
}

Give a default constructor

public TttState() {
state = new String[3][3];
for(int i=0;i<=2; i++)
{
for(int j=0; j<=2;j++)
{
this.state[i][j]="";
}
}
this.turn = "X";
}

Give a toString implementation, so that you can print the current state

public String toString()
{
StringBuilder sb = new StringBuilder("");
for(int i=0;i<=2; i++)
{
for(int j=0; j<=2;j++)
{
if(state[i][j].equals(""))
{
sb.append("-");
}
else
{
sb.append(state[i][j]);
}
sb.append("t");
}
sb.append("n");
}
return sb.toString();
}

Override the method getWinner() as follows

public String getWinner()
{
// ROW CHECK BEGINS
if(state[0][0].equalsIgnoreCase("X") && state[0][1].equalsIgnoreCase("X") && state[0][2].equalsIgnoreCase("X"))
{
return "X";
}
if(state[0][0].equalsIgnoreCase("O") && state[0][1].equalsIgnoreCase("O") && state[0][2].equalsIgnoreCase("O"))
{
return "O";
}
if(state[1][0].equalsIgnoreCase("X") && state[1][1].equalsIgnoreCase("X") && state[1][2].equalsIgnoreCase("X"))
{
return "X";
}
if(state[1][0].equalsIgnoreCase("O") && state[1][1].equalsIgnoreCase("O") && state[1][2].equalsIgnoreCase("O"))
{
return "O";
}
if(state[2][0].equalsIgnoreCase("X") && state[2][1].equalsIgnoreCase("X") && state[2][2].equalsIgnoreCase("X"))
{
return "X";
}
if(state[2][0].equalsIgnoreCase("O") && state[2][1].equalsIgnoreCase("O") && state[2][2].equalsIgnoreCase("O"))
{
return "O";
}

// COLUMN CHECK BEGINS
if(state[0][0].equalsIgnoreCase("X") && state[1][0].equalsIgnoreCase("X") && state[2][0].equalsIgnoreCase("X"))
{
return "X";
}
if(state[0][0].equalsIgnoreCase("O") && state[1][0].equalsIgnoreCase("O") && state[2][0].equalsIgnoreCase("O"))
{
return "O";
}
if(state[0][1].equalsIgnoreCase("X") && state[1][1].equalsIgnoreCase("X") && state[2][1].equalsIgnoreCase("X"))
{
return "X";
}
if(state[0][1].equalsIgnoreCase("O") && state[1][1].equalsIgnoreCase("O") && state[2][1].equalsIgnoreCase("O"))
{
return "O";
}
if(state[0][2].equalsIgnoreCase("X") && state[1][2].equalsIgnoreCase("X") && state[2][2].equalsIgnoreCase("X"))
{
return "X";
}
if(state[0][2].equalsIgnoreCase("O") && state[1][2].equalsIgnoreCase("O") && state[2][2].equalsIgnoreCase("O"))
{
return "O";
}
// DIAGNONAL CHECKS
if(state[0][0].equalsIgnoreCase("X") && state[1][1].equalsIgnoreCase("X") && state[2][2].equalsIgnoreCase("X"))
{
return "X";
}
if(state[0][0].equalsIgnoreCase("O") && state[1][1].equalsIgnoreCase("O") && state[2][2].equalsIgnoreCase("O"))
{
return "O";
}

if(state[0][2].equalsIgnoreCase("X") && state[1][1].equalsIgnoreCase("X") && state[2][0].equalsIgnoreCase("X"))
{
return "X";
}
if(state[0][2].equalsIgnoreCase("O") && state[1][1].equalsIgnoreCase("O") && state[2][0].equalsIgnoreCase("O"))
{
return "O";
}
int nonBlank = 0;
for(int i=0;i<=2;i++)
{
for(int j=0;j<=2;j++)
{
if(!state[i][j].equals(""))
{
nonBlank++;
}
}
}
if(nonBlank==9)
{
return "draw";
}

return "";
}

Override the method isGameOver()

public boolean isGameOver()
{
if(!getWinner().equals("") && !getWinner().equals("draw"))
{
return true;
}
else
{
return false;
}
}

Override the method getChildren()

@Override
public List getChildren() {
List children = new ArrayList();
if(turn.equals("X"))
{
for(int i=0;i<=2; i++)
{
for(int j=0; j<=2;j++)
{
if(state[i][j].equals(""))
{
TttState child = new TttState(this);
child.state[i][j]="X";
String newTurn = "O";
child.setTurn(newTurn);
children.add(child);
}
}
}
}
else
{
for(int i=0;i<=2; i++)
{
for(int j=0; j<=2;j++)
{
if(state[i][j].equals(""))
{
TttState child = new TttState(this);
child.state[i][j]="O";
String newTurn = "X";
child.setTurn(newTurn);
children.add(child);
}
}
}
}
return children;
}

Override getTurn and setTurn

public String getTurn() {
return turn;
}

public void setTurn(String turn) {
this.turn = turn;
}

Your main program will look something like this:

public static void main(String args[])
{
TttState x = new TttState();
System.out.println("WINNER : " + x.getWinner());
x.setTurn("X");
Scanner sc = new Scanner(System.in);
while(!x.isGameOver())
{
String xIndex = sc.nextLine();
String yIndex = sc.nextLine();
int xint = Integer.parseInt(xIndex);
int yint = Integer.parseInt(yIndex);
x.getState()[xint][yint]="X";
x.setTurn("O");
int minScore = 100;
List children = x.getChildren();
TttState bestMove = new TttState(x);
for(State child : children)
{
int childScore = child.minimax();
// We are using < because we are always evaluating
// the best move from the options that O player has....
if(childScore < minScore)
{
minScore = childScore;
bestMove = (TttState)child;
bestMove.setTurn("X");
}
}
System.out.print(bestMove);
x = bestMove;
}
System.out.println("GAME OVER...");

}