Python Constraints

Viewed 139

I have been working on making a search algorithm for Akari (Light Up) game with python-constraint and I have to make it a CSPs. I have defined my variables as x and y and domains are the length of the board accordingly.

Here is a link for the game if you wanna check it out : https://www.puzzle-light-up.com/

Here is my problem.

I have managed to get solutions for the cases:

  • If there is a zero tile, I do not include neighbours of that tile in the solution.
  • If there is a numbered tiles get coordinates of neighbour tiles(all 4 of them).

Problem Is:

  • Even though I get 4 neighbours, I have to make it so that numbered 4 tile must get all neighbours while numbered 3 must get 3 neighbours, numbered 2 and 1 tiles must get 2 and 1 neighbour tiles accordingly.
  • Also I couldn't decide how to make a constraint for blocks of white tiles that are connected horizontally and vertically, where only one light should be placed. Basically no two lights can see each other. Black tiles and numbered tiles block the light.

Here is my code and solution I get. If you can give any advice on how to think about the problem or show my mistakes that would be great. I have searched enough and couldn't find any useful information that can make me move forward in code-wise.

from constraint import *

# -1 for Black Tiles
# 0 for 0
# _ for W
# 1 for 1
# 2 for 2
# 3 for 3
# 4 for 4

board = [
    ["_", "_", "_", "_", "_", "_", "-1"],
    ["_", "_", "4", "_", "_", "_", "_"],
    ["0", "_", "_", "_", "1", "-1", "_"],
    ["_", "_", "_", "1", "_", "_", "_"],
    ["_", "-1", "1", "_", "_", "_", "-1"],
    ["_", "_", "_", "_", "-1", "_", "_"],
    ["1", "_", "_", "_", "_", "_", "_"]
]

problem = Problem()

# Variable and Domains
rows = range(len(board))
cols = range(len(board[0]))

problem.addVariables("y", rows)
problem.addVariables("x", cols)

# Constraints


# not including around of 0
problem.addConstraint(
    lambda y, x: not ((0 <= y + 1 <= 6 and board[y + 1][x] == "0") or (0 <= y - 1 <= 6 and board[y - 1][x] == "0") or
                      (0 <= x + 1 <= 6 and board[y][x + 1] == "0") or (0 <= x - 1 <= 6 and board[y][x - 1] == "0")),
    ["y", "x"])

# do not include 0 tile
problem.addConstraint(lambda y, x: board[y][x] != "-1", ["y", "x"])

# including numbered tiles

problem.addConstraint(lambda y, x:
                      # add for 1
                      (0 <= y + 1 <= 6 and board[y + 1][x] == "1") or (0 <= y - 1 <= 6 and board[y - 1][x] == "1")
                      or (0 <= x + 1 <= 6 and board[y][x + 1] == "1") or (0 <= x - 1 <= 6 and board[y][x - 1] == "1")
                      # add for 2
                      or (0 <= y + 1 <= 6 and board[y + 1][x] == "2") or (0 <= y - 1 <= 6 and board[y - 1][x] == "2")
                      or (0 <= x + 1 <= 6 and board[y][x + 1] == "2") or (0 <= x - 1 <= 6 and board[y][x - 1] == "2")
                      # add for 3
                      or (0 <= y + 1 <= 6 and board[y + 1][x] == "3") or (0 <= y - 1 <= 6 and board[y - 1][x] == "3")
                      or (0 <= x + 1 <= 6 and board[y][x + 1] == "3") or (0 <= x - 1 <= 6 and board[y][x - 1] == "3")
                      # add for 4
                      or (0 <= y + 1 <= 6 and board[y + 1][x] == "4") or (0 <= y - 1 <= 6 and board[y - 1][x] == "4")
                      or (0 <= x + 1 <= 6 and board[y][x + 1] == "4") or (0 <= x - 1 <= 6 and board[y][x - 1] == "4"),
                      ["y", "x"])

# check if there is a light source neighbour of a dedicated light source for 4
problem.addConstraint(lambda y, x:
                      not ((0 <= y + 2 <= 6 and board[y + 2][x] == "4") 
                           or (0 <= y - 1 <= 6 and board[y - 2][x] == "4")
                           or (0 <= x + 2 <= 6 and board[y][x + 2] == "4") 
                           or (0 <= x - 1 <= 6 and board[y][x - 2] == "4")), ["y", "x"])

# check if there is a light source diagonal of a dedicated light source for 4
problem.addConstraint(lambda y, x:
                      not ((x + 1 in cols and y + 1 in rows and board[y + 1][x + 1] == "4") 
                           or ( x + 1 in cols and y - 1 in rows and board[y - 1][x + 1] == "4")
                           or (x - 1 in cols and y + 1 in rows and board[y + 1][x - 1] == "4") 
                           or (x - 1 in cols and y - 1 in rows and board[y - 1][x - 1] == "4")), ["y", "x"])


solutions = problem.getSolutions()

print()
print(len(solutions))

print()
for item in solutions:
    print(item)
    board[item["y"]][item["x"]] = "L"

print()
for row in rows:
    print(board[row])

Here is the solution I get for coordinates to place lights:

9

{'x': 4, 'y': 3}
{'x': 3, 'y': 1}
{'x': 3, 'y': 4}
{'x': 2, 'y': 2}
{'x': 2, 'y': 0}
{'x': 2, 'y': 5}
{'x': 1, 'y': 6}
{'x': 1, 'y': 1}
{'x': 0, 'y': 5}

['_', '_', 'L', '_', '_', '_', '-1']
['_', 'L', '4', 'L', '_', '_', '_']
['0', '_', 'L', '_', '1', '-1', '_']
['_', '_', '_', '1', 'L', '_', '_']
['_', '-1', '1', 'L', '_', '_', '-1']
['L', '_', 'L', '_', '-1', '_', '_'][enter image description here][1]
['1', 'L', '_', '_', '_', '_', '_']

EDIT:

This is how the board looks (a) and the result should be (b) https://i.stack.imgur.com/IIXoc.png

0 Answers
Related