8 ms·

Curious about 2 things: 1) Can it solve especially hard Sudoku puzzles? (ie, expert level where humans often get stuck) 2) Is there a resource somewhere that

Curious about 2 things: 1) Can it solve especially hard Sudoku puzzles? (ie, expert level where humans often get stuck) 2) Is there a resource somewhere that lists the types of Prolog problems that it excels at solving?

hjek 7y ago
1) Yes, and (when there is only one unique solution) it can apparently be found in Prolog without doing an search at all by using constraint logic programming. Check the video in the sudoku article. 2) I'm not the best at answering this as I'm quite new to Prolog, but I'll try. I'd say a) anything you'd use a general purpose programming languge for, b) anything you'd use SQL for, and c) anything that's too difficult to do in either of those. SWI Prolog[0] has a large standard library and feels very "batteries included". Perhaps what I wouldn't use it for is mobile apps..? (But then again, there's Tau Prolog[1] which could probably work in a Cordova app). [0]: http://www.swi-prolog.org/ http://www.swi-prolog.org/ [1]: http://tau-prolog.org/ http://tau-prolog.org/
- taeric 7y ago
  I'm curious on your first point. There are puzzles that have multiple legal plays but only a single solution. In those, guessing/searching is basically required, right?
  - triska 7y ago
    A valid Sudoku puzzle is such that the given clues admit precisely one solution. Hence, if you somehow manage to take into account all the initially available information, then no search is required, because, in a sense, the given hints already narrow down the entire space of (ostensibly) possible assignments to a single one. There are constraint solvers that do this. For example, with the CLP(B) version based on BDDs that I mentioned, the solver internally constructs a Binary Decision Diagram (BDD) which is like a (ideally: more compact) truth table of all assignments that satisfy the requirements. Therefore, with the CLP(B) version I posted, search is never necessary for valid Sudoku puzzles, because they admit precisely one solution, and the constraint solver deduces this unique solution by reasoning about the decision diagram. There's a severe drawback to this: The BDD may be exponential in the number of variables. That's a problem, because there are dozens of variables in many Sudoku puzzles. In practice, we are often lucky, and the worst-case space requirements do not arise. For comparison, the CLP(FD/ℤ) formulation is based on constraint propagation that ensures a certain kind of consistency for all individual constraints in isolation, but not necessarily for the combination of all constraints, i.e., the problem as a whole. In practice, at least for Sudoku puzzles, this also often leads to finding the unique solution without any search. This may also be the case if only the minimum number of clues for a valid Sudoku puzzle (i.e., 17, per https://arxiv.org/abs/1201.0749 https://arxiv.org/abs/1201.0749) is specified, as the parent mentions. In general, search is still required. In the concrete case of (standard) Sudoku, the required search, if there is any at all, is typically very small, because the many constraints usually narrow down the entire space considerably. Reducing the amount of required search is the key attraction and goal of the consistency techniques that are used by constraint systems. The available systems differ in how much and how fast they are able to prune inconsistent values, leading to notions such as global consistency, domain consistency, bounds consistency etc. that give some indication of propagation strength.
    - taeric 7y ago
      I'll see if I can find my references again, but pretty sure this is not true. You can have a specified puzzle that has a single solution but requires a guess. I agree most are not this way, but they can be made.
      - triska 7y ago
        If you find such a puzzle, please let me know! Assuming the CLP(B) solver is correctly implemented, the CLP(B) solution I posted will give the unique solution without any search. On the other hand, it is comparatively easy to find puzzles where the CLP(ℤ) version will require search, even if only a small amount.
        taeric 7y ago
        I'll have to dive on it more, but https://news.ycombinator.com/item?id=14246452 https://news.ycombinator.com/item?id=14246452 is last time I remember discussing it. I thought the point was that sometimes searches were needed. Did I misunderstand? Have things changed? (Neither would surprise me.)
    - suyjuris 7y ago
      It seems a bit misleading to talk about not needing search, if you are only referring to a very specific part in the implementation of a constraint solver. Without context, I would have interpreted it as being able to avoid an exponential search over the solution space, which is (for general sudoku, under mild assumptions) impossible. So while it appears to be an advantage in principle, the claim is actually 'sometimes this is faster in practice'.
  - deleted 7y ago
    [deleted]
  - hjek 7y ago
    > In those, guessing/searching is basically required, right? Apparently no guessing is required! In Prolog it's fine for a variable (that represents a square in a sudoku puzzle) to be somewhere between 1 and 9. (Yes, that can be a bit mind-boggling, because in most other programming languages a variable can't really be either this or that. As far as I know, not even in SQL which is also somewhat declarative.) You might get in a situation where one square (let's call it A) is between 1 and 3 and two other squares on the same row (let's call them B and C) are both between 1 and 2. One constraint that we have given is that all numbers on a row must be distinct (because that's one of the rules of a sudoku puzzle), so given those constraints and facts, Prolog can deduce that the value of the first square must be 3. Therefore no guessing (or searching + backtracking) is required; only constraint propagation. This is what the query would look like in a Prolog REPL: [library(clpfd)], % load library for constraint logic over finite domains A in 1..3, B in 1..2, C in 1..2, all_distinct([A,B,C]). And this is the reply: A = 3, B in 1..2, all_distinct([3, B, C]), C in 1..2. I can only recommend you install SWI Prolog[0] and give it a try. It's quite fun! (Triska's explanation is probably more in depth and correct, but I thought I'd just chip in with my newbie way of explaining how I understand this. But seriously, check his videos. They're great stuff. The illustrations make the explanations accessible.) [0]: http://www.swi-prolog.org/ http://www.swi-prolog.org/
    - taeric 7y ago
      Right, I think this is somewhat just talking past each other. You don't have to backtrack on the values, but it is essentially searching on the constraints. That is, if you have a board where there are multiple legal moves on every open position, but only one solution, you still have to pick which constraint to propagate to find the solution. No?
    - tom_mellior 7y ago
      But when you are at a state like A = 3, B in 1..2, all_distinct([3, B, C]), C in 1..2. you don't yet have a complete solution in which each variable is bound to a number. In fact, you don't even have a guarantee that a solution exists. To get to this point no search is necessary, but to get from this point to a guaranteed solution, you need to call a "labeling" predicate, which will do backtracking search.
- new4thaccount 7y ago
  How is Prolog ideal for when you'd use SQL? I can understand it if you're talking about querying a CSV file, but the advantage to SQL is that the database with all your data natively supports SQL and it can usually run pretty fast. Btw: what would it look like to query a small sample CSV file. Like the below example if you wanted to find all cars that are made by Ford? Brand,Model,Year,Color/n Ford,F150,1999,Black/n Toyota,Yaris,2013,Yellow/n Ford,Mustang,1969,Blue/n Edit: sorry for not knowing how to format HN properly and show the newline on each of the rows.
  - hjek 7y ago
    Hey, this is good practice! First we can load the csv library, then read the rows of the csv file, and assert those rows as facts using the `car` identifier. (Doesn't mean `car` like in lisp, obviously, but automobile.) ?- [library(csv)], csv_read_file('cars.csv',Rows, [functor(car)]), maplist(assert, Rows). If we want to find a Ford, then we can enter this query: ?- car('Ford', Model, Year, Colour). Any capitalised word that's not in quotes is a variable in Prolog, so they can take any value. This will give us the result: Model = 'F150', Year = 1999, Colour = 'Black' ; Press space, and we get another: Model = 'Mustang', Year = 1969, Colour = 'Blue'. And there are no more, so it returns to the REPL. (I should really have discarded the first line, because right now there's a car, whose brand is 'Brand', and so on. Well, well...) If we just wanted a list of all the results, we could use the findall/3 predicate. Something that's neat in Prolog is that you can define recursive relations. In SQL it's easy to define a parent/child relation, but what about ancestor/descendant? (Yes, you can use common table expressions, but the syntax is incredibly complicated.) Also, you don't need to create database schemas and Prolog, and unification feels seamless as opposed to explicitly declaring the JOINs. But, in my opinion, where Prolog really shines compared to SQL is that there just isn't that whole object-relational impedance mismatch[0]. [0]: https://en.wikipedia.org/wiki/Object-relational_impedance_mismatch https://en.wikipedia.org/wiki/Object-relational_impedance_mi... Edit: Ok, my turn quiz!! Say we have these bicycles: Brand, Colour, Year Mosquito, Blue, 2010 Raleigh, Red, 2005 Suzuki, Red, 1998 In SQL, how would you find the names of any two brands whose bicycles have the same colour? (Don't bother with the whole CSV parsing; just assume it's already a table.) In Prolog that would be: bicycle(One_brand, Colour, _), bicycle(Another_brand, Colour, _), One_brand \= Another_brand. Maybe I just have particularly hard time understanding SQL, but I'd have to surf StackOverflow for at very least half an hour to do that in SQL. I wouldn't know where to start.
ufo 7y ago
In my experience you need a very contrived Sudoku instance to make it hard for a computer. Usually even the "hard" instances can be quickly solved by a computer search.

hjek 7y ago

1) Yes, and (when there is only one unique solution) it can apparently be found in Prolog without doing an search at all by using constraint logic programming. Check the video in the sudoku article. 2) I'm not the best at answering this as I'm quite new to Prolog, but I'll try. I'd say a) anything you'd use a general purpose programming languge for, b) anything you'd use SQL for, and c) anything that's too difficult to do in either of those. SWI Prolog[0] has a large standard library and feels very "batteries included". Perhaps what I wouldn't use it for is mobile apps..? (But then again, there's Tau Prolog[1] which could probably work in a Cordova app). [0]: http://www.swi-prolog.org/ http://www.swi-prolog.org/ [1]: http://tau-prolog.org/ http://tau-prolog.org/

taeric 7y ago
I'm curious on your first point. There are puzzles that have multiple legal plays but only a single solution. In those, guessing/searching is basically required, right?
- triska 7y ago
  A valid Sudoku puzzle is such that the given clues admit precisely one solution. Hence, if you somehow manage to take into account all the initially available information, then no search is required, because, in a sense, the given hints already narrow down the entire space of (ostensibly) possible assignments to a single one. There are constraint solvers that do this. For example, with the CLP(B) version based on BDDs that I mentioned, the solver internally constructs a Binary Decision Diagram (BDD) which is like a (ideally: more compact) truth table of all assignments that satisfy the requirements. Therefore, with the CLP(B) version I posted, search is never necessary for valid Sudoku puzzles, because they admit precisely one solution, and the constraint solver deduces this unique solution by reasoning about the decision diagram. There's a severe drawback to this: The BDD may be exponential in the number of variables. That's a problem, because there are dozens of variables in many Sudoku puzzles. In practice, we are often lucky, and the worst-case space requirements do not arise. For comparison, the CLP(FD/ℤ) formulation is based on constraint propagation that ensures a certain kind of consistency for all individual constraints in isolation, but not necessarily for the combination of all constraints, i.e., the problem as a whole. In practice, at least for Sudoku puzzles, this also often leads to finding the unique solution without any search. This may also be the case if only the minimum number of clues for a valid Sudoku puzzle (i.e., 17, per https://arxiv.org/abs/1201.0749 https://arxiv.org/abs/1201.0749) is specified, as the parent mentions. In general, search is still required. In the concrete case of (standard) Sudoku, the required search, if there is any at all, is typically very small, because the many constraints usually narrow down the entire space considerably. Reducing the amount of required search is the key attraction and goal of the consistency techniques that are used by constraint systems. The available systems differ in how much and how fast they are able to prune inconsistent values, leading to notions such as global consistency, domain consistency, bounds consistency etc. that give some indication of propagation strength.
  - taeric 7y ago
    I'll see if I can find my references again, but pretty sure this is not true. You can have a specified puzzle that has a single solution but requires a guess. I agree most are not this way, but they can be made.
    - triska 7y ago
      If you find such a puzzle, please let me know! Assuming the CLP(B) solver is correctly implemented, the CLP(B) solution I posted will give the unique solution without any search. On the other hand, it is comparatively easy to find puzzles where the CLP(ℤ) version will require search, even if only a small amount.
      - taeric 7y ago
        I'll have to dive on it more, but https://news.ycombinator.com/item?id=14246452 https://news.ycombinator.com/item?id=14246452 is last time I remember discussing it. I thought the point was that sometimes searches were needed. Did I misunderstand? Have things changed? (Neither would surprise me.)
  - suyjuris 7y ago
    It seems a bit misleading to talk about not needing search, if you are only referring to a very specific part in the implementation of a constraint solver. Without context, I would have interpreted it as being able to avoid an exponential search over the solution space, which is (for general sudoku, under mild assumptions) impossible. So while it appears to be an advantage in principle, the claim is actually 'sometimes this is faster in practice'.
- deleted 7y ago
  [deleted]
- hjek 7y ago
  > In those, guessing/searching is basically required, right? Apparently no guessing is required! In Prolog it's fine for a variable (that represents a square in a sudoku puzzle) to be somewhere between 1 and 9. (Yes, that can be a bit mind-boggling, because in most other programming languages a variable can't really be either this or that. As far as I know, not even in SQL which is also somewhat declarative.) You might get in a situation where one square (let's call it A) is between 1 and 3 and two other squares on the same row (let's call them B and C) are both between 1 and 2. One constraint that we have given is that all numbers on a row must be distinct (because that's one of the rules of a sudoku puzzle), so given those constraints and facts, Prolog can deduce that the value of the first square must be 3. Therefore no guessing (or searching + backtracking) is required; only constraint propagation. This is what the query would look like in a Prolog REPL: [library(clpfd)], % load library for constraint logic over finite domains A in 1..3, B in 1..2, C in 1..2, all_distinct([A,B,C]). And this is the reply: A = 3, B in 1..2, all_distinct([3, B, C]), C in 1..2. I can only recommend you install SWI Prolog[0] and give it a try. It's quite fun! (Triska's explanation is probably more in depth and correct, but I thought I'd just chip in with my newbie way of explaining how I understand this. But seriously, check his videos. They're great stuff. The illustrations make the explanations accessible.) [0]: http://www.swi-prolog.org/ http://www.swi-prolog.org/
  - taeric 7y ago
    Right, I think this is somewhat just talking past each other. You don't have to backtrack on the values, but it is essentially searching on the constraints. That is, if you have a board where there are multiple legal moves on every open position, but only one solution, you still have to pick which constraint to propagate to find the solution. No?
  - tom_mellior 7y ago
    But when you are at a state like A = 3, B in 1..2, all_distinct([3, B, C]), C in 1..2. you don't yet have a complete solution in which each variable is bound to a number. In fact, you don't even have a guarantee that a solution exists. To get to this point no search is necessary, but to get from this point to a guaranteed solution, you need to call a "labeling" predicate, which will do backtracking search.
new4thaccount 7y ago
How is Prolog ideal for when you'd use SQL? I can understand it if you're talking about querying a CSV file, but the advantage to SQL is that the database with all your data natively supports SQL and it can usually run pretty fast. Btw: what would it look like to query a small sample CSV file. Like the below example if you wanted to find all cars that are made by Ford? Brand,Model,Year,Color/n Ford,F150,1999,Black/n Toyota,Yaris,2013,Yellow/n Ford,Mustang,1969,Blue/n Edit: sorry for not knowing how to format HN properly and show the newline on each of the rows.
- hjek 7y ago
  Hey, this is good practice! First we can load the csv library, then read the rows of the csv file, and assert those rows as facts using the `car` identifier. (Doesn't mean `car` like in lisp, obviously, but automobile.) ?- [library(csv)], csv_read_file('cars.csv',Rows, [functor(car)]), maplist(assert, Rows). If we want to find a Ford, then we can enter this query: ?- car('Ford', Model, Year, Colour). Any capitalised word that's not in quotes is a variable in Prolog, so they can take any value. This will give us the result: Model = 'F150', Year = 1999, Colour = 'Black' ; Press space, and we get another: Model = 'Mustang', Year = 1969, Colour = 'Blue'. And there are no more, so it returns to the REPL. (I should really have discarded the first line, because right now there's a car, whose brand is 'Brand', and so on. Well, well...) If we just wanted a list of all the results, we could use the findall/3 predicate. Something that's neat in Prolog is that you can define recursive relations. In SQL it's easy to define a parent/child relation, but what about ancestor/descendant? (Yes, you can use common table expressions, but the syntax is incredibly complicated.) Also, you don't need to create database schemas and Prolog, and unification feels seamless as opposed to explicitly declaring the JOINs. But, in my opinion, where Prolog really shines compared to SQL is that there just isn't that whole object-relational impedance mismatch[0]. [0]: https://en.wikipedia.org/wiki/Object-relational_impedance_mismatch https://en.wikipedia.org/wiki/Object-relational_impedance_mi... Edit: Ok, my turn quiz!! Say we have these bicycles: Brand, Colour, Year Mosquito, Blue, 2010 Raleigh, Red, 2005 Suzuki, Red, 1998 In SQL, how would you find the names of any two brands whose bicycles have the same colour? (Don't bother with the whole CSV parsing; just assume it's already a table.) In Prolog that would be: bicycle(One_brand, Colour, _), bicycle(Another_brand, Colour, _), One_brand \= Another_brand. Maybe I just have particularly hard time understanding SQL, but I'd have to surf StackOverflow for at very least half an hour to do that in SQL. I wouldn't know where to start.

ufo 7y ago

In my experience you need a very contrived Sudoku instance to make it hard for a computer. Usually even the "hard" instances can be quickly solved by a computer search.