6 ms·

To see what I mean, please consider the Prolog program for solving Sudoku puzzles that is shown in this article, and try the following query: | ?- sudoku(X

by zmonx 9y ago

To see what I mean, please consider the Prolog program for solving Sudoku puzzles that is shown in this article, and try the following query: | ?- sudoku(X, Y). This is called the most general query, since all arguments are fresh variables. Declaratively, we are asking Prolog: "Are there any solutions whatsoever?" In this case, the system answers with: X = [_#3(1..4),_#24(1..4),...etc.] Y = [_#3(1..4),_#24(1..4),...etc.] This shows that the Prolog program did not perform any search at all: No concrete value is instantiated, and the system does not ask for alternatives. That's right! No search whatsoever, and no backtracking at all, is performed in this program. No matter which definition of brute force search you are applying, this definitely does not fall into "search" at all! In the article, a more concrete query is also shown, as well as its solution. This solution is found via constraint propagation alone. This means that the system has deduced the unique solution purely by reasoning about the available constraints, which it does automatically every time a constraint is posted. This is one example of an algorithm that does not guess. This also shows that even supposing you cannot make an algorithm that "never guesses", you can definitely make an algorithm that has to do much less guessing than searching over the whole tree. In Prolog, such algorithms are implemented and encapsulated in powerful combinatorial constraints like all_distinct/1, which are available in many Prolog systems and which you can use in your applications. Internally, the associated constraint propagators prune the search tree by applying various algorithms for you behind the scene. The ability to use such constraints and their strong pruning are major attractions of using Prolog for combinatorial tasks. You are right that there may be cases where such propagation, albeit quite strong, may not suffice to fully solve a concrete combinatorial task. For this reason, you have to apply a concrete enumeration of remaining variables. In Constraint Logic Programming over Integers, this search is called labeling and provided by predicates like fd_labeling/2 or similar, depending on your Prolog system. The article does not use them though, and even if it did, the search could be guided by various heuristics by simply supplying a few options, which together with the pruning applied by constraints distinguish such a search from more uninformed search strategies. Note also that the posted solution is quite hard to generalize elegantly. A shorter and equivalent Prolog program that describes 4x4 Sudoku puzzles is: sudoku(Rows) :- Rows = [Row1,Row2,Row3,Row4], maplist(same_length(Rows), Rows), blocks(Row1, Row2), blocks(Row3, Row4), append(Rows, Vs), fd_domain(Vs, 1, 4), maplist(fd_all_different, Rows), transpose(Rows, Cols), maplist(fd_all_different, Cols). blocks([], []). blocks([A1,A2|As], [B1,B2|Bs]) :- fd_all_different([A1,A2,B1,B2]), blocks(As, Bs). This assumes the availability of append/2 and transpose/2, which are likely already provided by your Prolog system, and easy to implement if they aren't.

taeric 9y ago
You can actually make a sudoku problem where, by the rules of the game, all open pieces have at least 2 possible values while still having a unique solution. So, to that end, I am unaware of how you could make a solver that doesn't have to guess. (As noted in a sibling post, I wouldn't be shocked to find I was wrong, but I would be interested in the details.) So, I'm ultimately wary of the claims here. The system has to be doing a search. It may be crafted in such a way that it just walks straight to the solution for some specifications, but that is as much from luck of easy constraints as it is the algorithm.
- zmonx 9y ago
  When you say "all open pieces have at least 2 possible values", how can the solution be unique? Surely for each piece, some values are not admissible, otherwise this would be a contradiction. Sufficiently strong pruning could have eliminated them, either by search or by more reasoning.
  - Pyxl101 9y ago
    Consider the Eight Queens problem. There are multiple valid solutions to the problem on a given chessboard. They are symmetric solutions, yet distinct. Any algorithm that finds a single solution and not all of them must be prioritizing arbitrarily among solutions, i.e., searching or fathoming them in some particular order. > This solution is found via constraint propagation alone. This means that the system has deduced the unique solution purely by reasoning about the available constraints, which it does automatically every time a constraint is posted. This is one example of an algorithm that does not guess. Have you considered how that constraint propagation algorithm works? What specific algorithm are you referring to? Constraint Programming is an alternative formulation of the same problem that Integer Linear Programming tackles, and the latter is known to be NP-hard. https://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns https://en.wikipedia.org/wiki/Linear_programming#Integer_unk... Constraint Programming and Integer Programming are both characterized as examples of Tree Search: http://preserve.lehigh.edu/cgi/viewcontent.cgi?article=1780&context=etd http://preserve.lehigh.edu/cgi/viewcontent.cgi?article=1780&... > Since tree search is a basic solution technique employed in both constraint and integer programming, we begin with a generic overview oftree search as a technique for finding feasible solutions to mathematical models. [...] > Every tree search algorithm is defined by four elements: a node- processing procedure, pruning rules, branching rules, and search strategy. The processing step is applied at every node of the search tree beginning with the root node, and usually involves some attempt to further reduce the feasible set associated with the node by applying logical rules. > Overall a tree search algorithm works as follows. A list of nodes that are candidates to be processed is maintained throughout the algorithm. This list initially contains only the root node. At each step in the algorithm, a node is chosen and processed. If the processing results in pruning of the node by one of the pruning rules, then the node is discarded. Otherwise, the node is further divided, resulting in two or more children, which are then added to the list of candidates. This procedure is iterated until no nodes remain on the candidate list. > [...] the constraint program is made up of two pieces: the constraints that comprise the formulation and a search strategy for solving the problem (emphasis mine). This is in contrast to a mathematical program, which describes a model but does not specify how to solve it. > Traditionally, a constraint programming formulation consists only of a list of decision variables, domains, a set of constraints to be satisfied, and a search procedure (emphasis mine). This traditional definition refers to a constraint satisfaction problem (CSP), since a solution is any assignment of values to variables such that all constraints are satisfied. Can you clarify which algorithm you're referring to, and how it manages to solve the problem without employing Tree Search?

by zmonx 9y ago

taeric 9y ago

You can actually make a sudoku problem where, by the rules of the game, all open pieces have at least 2 possible values while still having a unique solution. So, to that end, I am unaware of how you could make a solver that doesn't have to guess. (As noted in a sibling post, I wouldn't be shocked to find I was wrong, but I would be interested in the details.) So, I'm ultimately wary of the claims here. The system has to be doing a search. It may be crafted in such a way that it just walks straight to the solution for some specifications, but that is as much from luck of easy constraints as it is the algorithm.

zmonx 9y ago
When you say "all open pieces have at least 2 possible values", how can the solution be unique? Surely for each piece, some values are not admissible, otherwise this would be a contradiction. Sufficiently strong pruning could have eliminated them, either by search or by more reasoning.
- Pyxl101 9y ago
  Consider the Eight Queens problem. There are multiple valid solutions to the problem on a given chessboard. They are symmetric solutions, yet distinct. Any algorithm that finds a single solution and not all of them must be prioritizing arbitrarily among solutions, i.e., searching or fathoming them in some particular order. > This solution is found via constraint propagation alone. This means that the system has deduced the unique solution purely by reasoning about the available constraints, which it does automatically every time a constraint is posted. This is one example of an algorithm that does not guess. Have you considered how that constraint propagation algorithm works? What specific algorithm are you referring to? Constraint Programming is an alternative formulation of the same problem that Integer Linear Programming tackles, and the latter is known to be NP-hard. https://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns https://en.wikipedia.org/wiki/Linear_programming#Integer_unk... Constraint Programming and Integer Programming are both characterized as examples of Tree Search: http://preserve.lehigh.edu/cgi/viewcontent.cgi?article=1780&context=etd http://preserve.lehigh.edu/cgi/viewcontent.cgi?article=1780&... > Since tree search is a basic solution technique employed in both constraint and integer programming, we begin with a generic overview oftree search as a technique for finding feasible solutions to mathematical models. [...] > Every tree search algorithm is defined by four elements: a node- processing procedure, pruning rules, branching rules, and search strategy. The processing step is applied at every node of the search tree beginning with the root node, and usually involves some attempt to further reduce the feasible set associated with the node by applying logical rules. > Overall a tree search algorithm works as follows. A list of nodes that are candidates to be processed is maintained throughout the algorithm. This list initially contains only the root node. At each step in the algorithm, a node is chosen and processed. If the processing results in pruning of the node by one of the pruning rules, then the node is discarded. Otherwise, the node is further divided, resulting in two or more children, which are then added to the list of candidates. This procedure is iterated until no nodes remain on the candidate list. > [...] the constraint program is made up of two pieces: the constraints that comprise the formulation and a search strategy for solving the problem (emphasis mine). This is in contrast to a mathematical program, which describes a model but does not specify how to solve it. > Traditionally, a constraint programming formulation consists only of a list of decision variables, domains, a set of constraints to be satisfied, and a search procedure (emphasis mine). This traditional definition refers to a constraint satisfaction problem (CSP), since a solution is any assignment of values to variables such that all constraints are satisfied. Can you clarify which algorithm you're referring to, and how it manages to solve the problem without employing Tree Search?