Constraint Satisfaction Problem

[MVanderloo]

There are multiple problems in the repo that fall under CSP. Essentially a list of variables and constraints between them. It is not an algorithm but a class of problems that can be modeled in such a way, such as sudoku, n queens, graph coloring. There are multiple ways to solve them, one being backtracking. Could be considered a data structure? Otherwise I don’t know where it would live. I recently did an assignment for school in golang to make a sudoku and killer sudoku solver where we convert to a generic CSP to solve.

Where could this live in the repo? It’s difficult to define every constraint that a problem would use but you can cover most problems with EQUALS and NOT_EQUALS constraints. Or maybe there is a good way to define constraints by passing in some lambda functions. I’m not super experienced in rust but this could be something I’d be interested to contribute.

[github-actions[bot]]

This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[siriak]

I'm not entirely sure that I get it. So you want to make sure all the e.g. sudoku solvers accept input in the same format? That's a good idea, I think you might use traits for that.

[github-actions[bot]]

This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[skewballfox]

I'm not entirely sure that I get it. So you want to make sure all the e.g. sudoku solvers accept input in the same format? That's a good idea, I think you might use traits for that.

Please correct me if I'm wrong, but I think he means a more generalized linear solver, you describe the problem as a set of variables and constraints, and the algorithm finds an optimal solution which satisfies those constraints, if it exist.

[siriak]

@MVanderloo, I think you could add it to Math section if it's generalized and make an adapter to transform a Sudoku problem to a generic problem statement

[appgurueu]

Please correct me if I'm wrong, but I think he means a more generalized linear solver, you describe the problem as a set of variables and constraints, and the algorithm finds an optimal solution which satisfies those constraints, if it exist.

I don't think it's necessary about a linear solver but rather about solving boolean satisfiability problems (e.g. Sudoku can be modeled as a SAT problem).

[MVanderloo]

So my experience with this problem is creating a Constraint Satisfaction Problem solver, but yes I believe it can be generalized to Integer Linear Programming.

From my understanding, Linear Programming allows for domains that represent a range of numbers rather than Integer Linear Programming which the domain is a finite set of values. The algorithms I am familiar with solve for domains that are sets rather than ranges.

[github-actions[bot]]

This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[github-actions[bot]]

Please ping one of the maintainers once you add more information and updates here. If this is not the case and you need some help, feel free to ask for help in our Gitter channel. Thank you for your contributions!