Kenken-csp-solver

Exploring how to solve Kenken games using CSP techniques.

How to run

Run the kenken.py file by python: /python kenken.py.

Game generator

Generate new game.

CSP-solver solve using following techniques :

1- Backtracking :

Assign values from the domain and checking the constraints if it fail it check another value from the domain , until it ends the domain only at this time it return 'failure' and try another set of values (same domains different order) .
if it finishes assignment without failure then this is the answer

2- Backtracking with forward checking :

similarily assign values from the domain until it is done , but whenever it assign a value it modify the domain of the surrounding value according to following constraints :-
1- First constraint : No repeated values in same row and cloumn .
2- Second constraint : the operation made on the cage satisfy the condition .

3- Backtracking with arc consistency :

At every assignment, exclude any value in the domain which has not a value in the other end of the constraint that both satisfy it. We check the two ends of binary constraints which include:

• No repeated values in same row and cloumn.
• Each two ends' domains of 2-sized cages satisfy the constraint value and operation.

Heuristic :

Most Constraining Variable :

It sorts the cage within the length criteria of each cage and solve them in the recursive Backtrack function .
Which means it solve the cage of the greatest length first and then the smaller and the smaller and so on until it finds the solution .