My Answer Set Programming Page
From Wikipedia Answer_set_programming:
Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems. It is based on the stable model (answer set) semantics of logic programming. In ASP, search problems are reduced to computing stable models, and answer set solvers -- programs for generating stable models are used to perform search. The computational process employed in the design of many answer set solvers is an enhancement of the DPLL algorithm and, in principle, it always terminates (unlike Prolog query evaluation, which may lead to an infinite loop).
I have blogged about this in A first look at Answer Set Programming.
More information
Here are some useful links for ASP:
ASP Systems
There are many ASP systems. Here are those I have tested most.
My Answer Set Programming programs
Here are some of my ASP programs. Almost all of of them have also been done in some Constraint Programming system, for example MiniZinc. See Common constraint programming problems for a list of different implementations.
All are written in Gringo/Clingo/clasp, but should be quite easy to convert to other ASP systems, e.g. Lparse/Smodels.
The encodings with .lp
extension are for Gringo version 3. The encodings ported to Gringo 4 has extension .lp4
- 3_jugs.lp: 3 jugs problem (as a graph problem)
- 3_jugs.lp4: 3 jugs problem (as a graph problem)
- a_round_of_golf.lp: A round of gold (Dell Logic Puzzles)
- a_round_of_golf.lp4: A round of gold (Dell Logic Puzzles)
- all_interval.lp: All interval problem (CSPLib problem #7)
- all_interval.lp4: All interval problem (CSPLib problem #7)
- alldifferent_except_0.lp: Alldifferent except 0
- alldifferent_except_0.lp4: Alldifferent except 0
- arch_friends.lp: Arch friends puzzle (Dells Logic Puzzles)
- arch_friends.lp4: Arch friends puzzle (Dells Logic Puzzles)
- assignment.lp: Assignment problem (from Winston "Operations Research")
- assignment.lp4: Assignment problem (from Winston "Operations Research")
- averbach_1.4.lp: Seating problem, example 1.4 in Averbach & Chein "Problem Solving Through Recreational Mathematics"
- bales_of_hay.lp4: Bales of Hay
- building_blocks.lp: Building Blocks puzzle (Dell Logic Puzzles)
- building_blocks2.lp: Building Blocks puzzle (Dell Logic Puzzles), faster version
- building_blocks2.lp4: Building Blocks puzzle (Dell Logic Puzzles), faster version
- bus_scheduling.lp: Scheduling the number of buses for 6 days (from Taha "Operations Research")
- bus_scheduling.lp4: Scheduling the number of buses for 6 days (from Taha "Operations Research")
- bus_scheduling_csplib.lp: Bus driver scheduling (CSPLib problem #22)
Problem instances from CSPLib problem #22:
- bus_scheduling_csplib.lp4: Bus driver scheduling (CSPLib problem #22)
Problem instances from CSPLib problem #22:
- clique.lp: Maximum clique problem
Problem instances:
- coins3.lp: Coin problem: Minimum mumber of coins that allows one to exactly pay any amount smaller than one Euro
- coins3.lp4: Coin problem: Minimum mumber of coins that allows one to exactly pay any amount smaller than one Euro
- coins_grid.lp: Coins puzzle (Tony Hurlimann)
- coins_grid.lp4: Coins puzzle (Tony Hurlimann)
- coins_of_the_realm.lp4: Coins of the realm (Martin Gardner)
- coloring.lp: Simple map coloring problem
- coloring.lp4: Simple map coloring problem
- combinatorial_auction.lp: Combinatorial auction
- combinatorial_auction.lp4: Combinatorial auction
- crew.lp: Crew allocation
- crew.lp4: Crew allocation
- crew_rk.lp4: Crew allocation with symmetry breaking (thanks to Roland Kaminski)
- daily_schedule.lp: Daily schedule (logic puzzle)
- daily_schedule.lp4: Daily schedule (logic puzzle)
- diet1.lp: Diet problem
- diet1.lp4: Diet problem
- discrete_tomography.lp: Discrete tomography,
discrete_tomography.lp4
Problem instances
- euler1.lp: Project Euler, problem 1
- euler1.lp4: Project Euler, problem 1
- euler2.lp: Project Euler, problem 2
- euler2.lp4: Project Euler, problem 2
- fill_a_pix.lp: Fill-a-pix puzzle, fill_a_pix.lp4
Problem instances:
- fib.lp: Fibonacci
- fib.lp4: Fibonacci
- finding_celebrities.lp: Finding celebrities (a clique problem)
- finding_celebrities.lp4: Finding celebrities (a clique problem)
- futoshiki.lp: Futoshiki puzzle, futoshiki.lp4
Problem instances:
- hidato.lp: Hidato puzzle, hidato.lp4
Problem instances:
- jobs.lp: Jobs problem (standard problem in Automated Reasoning)
- jobs.lp4: Jobs problem (standard problem in Automated Reasoning)
- just_forgotten.lp: Just forgotten puzzle (Enigma 1517)
- just_forgotten.lp4: Just forgotten puzzle (Enigma 1517)
- kakuro.lp: Kakuro, a grid based puzzle
- kakuro.lp4: Kakuro, a grid based puzzle
- kenken2.lp: KenKen, a grid based puzzle
- kenken2.lp4: KenKen, a grid based puzzle
- killer_sudoku.lp: Killer Sudoku puzzle
- killer_sudoku.lp4: Killer Sudoku puzzle
- labeled_dice.lp: Labeled dice problem
- labeled_dice.lp4: Labeled dice problem
- langford.lp: Langford's number problem (CSP lib problem #24)
- langford.lp4: Langford's number problem (CSP lib problem #24)
- least_diff.lp: Least diff problem
- least_diff.lp4: Least diff problem
- magic_square.lp: Magic square
- magic_square.lp4: Magic square
- marathon2.lp: Marathon puzzle (XPress)
- minesweeper.lp: Minesweeper, minesweeper.lp4
Problem instances:
- mr_smith.lp: Smith family problem (IF Prolog)
- mr_smith.lp4: Smith family problem (IF Prolog)
- nqueens.lp: N-queens problem
- nqueens.lp4: N-queens problem
- organize_day.lp: Organizing a day, simple scheduling problem.
- organize_day.lp4: Organizing a day, simple scheduling problem.
- photo.lp: Photo preference problem (from Mozart/Oz Tutorial)
- photo.lp4: Photo preference problem (from Mozart/Oz Tutorial)
- place_number.lp: Place number problem
- place_number.lp4: Place number problem
- post_office_problem2.lp: Post office problem (Winston "Operations Research")
- post_office_problem2.lp4: Post office problem (Winston "Operations Research")
- prime_number.lp: A small excursion in prime numbers and divisors
- prime_number.lp4: A small excursion in prime numbers and divisors
- quasigroup_completion.lp, quasigroup_completion.lp4: Quasigroup completion
Problem instances:
- rogo.lp: Rogo grid puzzle, rogo2.lp (faster version with symmetry breaking), rogo2.lp4.
Problem instances:
- safe_cracking.lp: Safe cracking puzzle (Mozart/Oz)
- safe_cracking.lp4: Safe cracking puzzle (Mozart/Oz)
- scheduling_speakers.lp: Scheduling speakers (small scheduling problem from Rina Dechter)
- scheduling_speakers.lp4: Scheduling speakers (small scheduling problem from Rina Dechter)
- send_more_money.lp: SEND+MORE=MONEY
- send_more_money.lp4: SEND+MORE=MONEY
- send_more_money_b.lp: SEND+MORE=MONEY with hard coded M=1 (much faster)
- send_more_money_any_base.lp: SEND+MORE=MONEY in "any" base
- send_more_money_any_base.lp4: SEND+MORE=MONEY in "any" base
- send_most_money.lp: SEND+MOST=MONEY (maximizing MONEY)
- send_most_money.lp4: SEND+MOST=MONEY (maximizing MONEY)
- seseman.lp: Seseman's convent problem
- seseman.lp4: Seseman's convent problem
- set_covering.lp: Set covering problem: placing firestations (Winston: "Operations Research")
- set_covering.lp4: Set covering problem: placing firestations (Winston: "Operations Research")
- set_covering_b.lp: Set covering problem: placing firestations, alternative version (Winston: "Operations Research")
- set_covering_b.lp4: Set covering problem: placing firestations, alternative version (Winston: "Operations Research")
- set_covering2.lp: Set covering problem: number of security telephones on campus (Taha: "Operations Research")
- set_covering2.lp4: Set covering problem: number of security telephones on campus (Taha: "Operations Research")
- set_covering3.lp: Set covering problem: assigning senators to committee (Katta G Murty)
- set_covering3.lp4: Set covering problem: assigning senators to committee (Katta G Murty)
- set_covering3_b.lp: Set covering problem: assigning senators to committee, symbolic version (Katta G Murty)
- set_covering3_b.lp4: Set covering problem: assigning senators to committee, symbolic version (Katta G Murty)
- set_covering4.lp: Set convering (and partition) problem (Lundgren, Rönnqvist, Värbrand "Optimeringslära")
- set_covering4.lp4: Set convering (and partition) problem (Lundgren, Rönnqvist, Värbrand "Optimeringslära")
- set_covering_deployment.lp: Set covering deployment
- set_covering_deployment.lp4: Set covering deployment
- set_covering_opl.lp: Set covering problem: selecting workers to build a house (from an OPL model)
- set_covering_opl.lp4: Set covering problem: selecting workers to build a house (from an OPL model)
- set_covering_skiena.lp: Set covering problem (Skiena)
- set_covering_skiena.lp4: Set covering problem (Skiena)
- set_partition.lp: Set partition problem: equal sums and sum squares for the two partitions (Koalog)
- set_partition.lp4: Set partition problem: equal sums and sum squares for the two partitions (Koalog)
- sicherman_dice.lp: Sicherman dice
- sicherman_dice.lp4: Sicherman dice
- ski_assignment.lp: Ski assigment problem (Jeffrey Lee Hellrung, Jr)
- ski_assignment.lp4: Ski assigment problem (Jeffrey Lee Hellrung, Jr)
- steiner.lp: Steiner triplets
- strimko2.lp: Strimko problem, strimko2.lp4
Problem instances:
- subset_sum.lp: Subset sum problem (Katta G. Murty)
- subset_sum.lp4: Subset sum problem (Katta G. Murty)
- sudoku.lp: Sudoku
- sudoku.lp4: Sudoku
- sudoku_pi.lp: Pi Day Sudoku (2009)
- sudoku_pi.lp4: Pi Day Sudoku (2009)
- sudoku_pi_gcc.lp: Pi Day Sudoku (2009), using occurrence count
- sudoku_pi_gcc.lp4: Pi Day Sudoku (2009), using occurrence count
- survo_puzzle.lp: Survo puzzle, survo_puzzle.lp4
Problem instances:
- traffic_lights.lp: Traffic lights problem (CSPLib problem 16)
- traffic_lightslp4: Traffic lights problem (CSPLib problem 16)
- who_killed_agatha.lp: Who killed Agatha? (The Dreadsbury Mansion Murder Mystery)
- who_killed_agatha.lp4: Who killed Agatha? (The Dreadsbury Mansion Murder Mystery)
- xkcd.lp: xkcd knapsack (subset sum) problem
- xkcd.lp4: xkcd knapsack (subset sum) problem
- young_tableaux.lp: Young tableaux and partitions
- zebra.lp: Zebra puzzle
- zebra.lp4: Zebra puzzle
- zebra_slow.lp: Zebra puzzle, a must slower version (testing some parameters)
- zebra_slow.lp4: Zebra puzzle, a must slower version (testing some parameters)
Also, see my pages about Constraint Programming systems:
* My Constraint Programming Blog
* Constraint Programming
* Common constraint programming problems
* My MiniZincZinc page
* My Zinc page
* My JaCoP page
* My Choco page
* My Gecode/R page
* My Comet page
* My Gecode page
* My ECLiPSe page
* My Tailor/Essence' page
* My SICStus Prolog page
* My Google CP Solver page
* My OscaR page
* My JSR-331 page
* My Numberjack page
* My AIMMS+CP page
* My B-Prolog page
* My Choco3 page
* My Picat page
* My z3/python page
* My SWI-Prolog page
Back to my homepage
Created by Hakan Kjellerstrand hakank@gmail.com