Using Small MUSes to Explain How to Solve Pen and Paper Puzzles
- URL: http://arxiv.org/abs/2104.15040v1
- Date: Fri, 30 Apr 2021 15:07:51 GMT
- Title: Using Small MUSes to Explain How to Solve Pen and Paper Puzzles
- Authors: Joan Espasa, Ian P. Gent, Ruth Hoffmann, Christopher Jefferson, Alice
M. Lynch
- Abstract summary: We present Demystify, a tool which allows puzzles to be expressed in a high-level constraint programming language.
We give several improvements to the existing techniques for solving puzzles with MUSes.
We demonstrate the effectiveness and generality of Demystify by comparing its results to documented strategies for solving a range of pen and paper puzzles by hand.
- Score: 4.535832029902474
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Pen and paper puzzles like Sudoku, Futoshiki and Skyscrapers are hugely
popular. Solving such puzzles can be a trivial task for modern AI systems.
However, most AI systems solve problems using a form of backtracking, while
people try to avoid backtracking as much as possible. This means that existing
AI systems do not output explanations about their reasoning that are meaningful
to people. We present Demystify, a tool which allows puzzles to be expressed in
a high-level constraint programming language and uses MUSes to allow us to
produce descriptions of steps in the puzzle solving. We give several
improvements to the existing techniques for solving puzzles with MUSes, which
allow us to solve a range of significantly more complex puzzles and give higher
quality explanations. We demonstrate the effectiveness and generality of
Demystify by comparing its results to documented strategies for solving a range
of pen and paper puzzles by hand, showing that our technique can find many of
the same explanations.
Related papers
- Solving Zebra Puzzles Using Constraint-Guided Multi-Agent Systems [25.0042181817455]
We introduce a multi-agent system, ZPS, that integrates Large Language Models with an off the shelf theorem prover.
This system tackles the complex puzzle-solving task by breaking down the problem into smaller, manageable parts.
We also introduce an automated grid puzzle grader to assess the correctness of our puzzle solutions and show that the automated grader is reliable by evaluating it in a user-study.
arXiv Detail & Related papers (2024-07-04T14:22:25Z) - Are Language Models Puzzle Prodigies? Algorithmic Puzzles Unveil Serious
Challenges in Multimodal Reasoning [24.386388107656334]
This paper introduces the novel task of multimodal puzzle solving, framed within the context of visual question-answering.
We present a new dataset, AlgoVQA, designed to challenge and evaluate the capabilities of multimodal language models in solving algorithmic puzzles.
arXiv Detail & Related papers (2024-03-06T17:15:04Z) - Solving Witness-type Triangle Puzzles Faster with an Automatically
Learned Human-Explainable Predicate [0.29005223064604074]
We develop a search-based artificial intelligence puzzle solver for The Witness game.
We learn a human-explainable predicate that predicts whether a partial path to a Witness-type puzzle is not completable to a solution path.
We prove a key property of the learned predicate which allows us to use it for pruning successor states in search.
arXiv Detail & Related papers (2023-08-04T18:52:18Z) - Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
We present a novel method for solving square jigsaw puzzles based on global optimization.
The method is fully automatic, assumes no prior information, and can handle puzzles with known or unknown piece orientation.
arXiv Detail & Related papers (2023-03-26T18:53:51Z) - Automated Graph Genetic Algorithm based Puzzle Validation for Faster
Game Desig [69.02688684221265]
This paper presents an evolutionary algorithm, empowered by expert-knowledge informeds, for solving logical puzzles in video games efficiently.
We discuss multiple variations of hybrid genetic approaches for constraint satisfaction problems that allow us to find a diverse set of near-optimal solutions for puzzles.
arXiv Detail & Related papers (2023-02-17T18:15:33Z) - Video Anomaly Detection by Solving Decoupled Spatio-Temporal Jigsaw
Puzzles [67.39567701983357]
Video Anomaly Detection (VAD) is an important topic in computer vision.
Motivated by the recent advances in self-supervised learning, this paper addresses VAD by solving an intuitive yet challenging pretext task.
Our method outperforms state-of-the-art counterparts on three public benchmarks.
arXiv Detail & Related papers (2022-07-20T19:49:32Z) - Divide & Conquer Imitation Learning [75.31752559017978]
Imitation Learning can be a powerful approach to bootstrap the learning process.
We present a novel algorithm designed to imitate complex robotic tasks from the states of an expert trajectory.
We show that our method imitates a non-holonomic navigation task and scales to a complex simulated robotic manipulation task with very high sample efficiency.
arXiv Detail & Related papers (2022-04-15T09:56:50Z) - End-to-end Algorithm Synthesis with Recurrent Networks: Logical
Extrapolation Without Overthinking [52.05847268235338]
We show how machine learning systems can perform logical extrapolation without overthinking problems.
We propose a recall architecture that keeps an explicit copy of the problem instance in memory so that it cannot be forgotten.
We also employ a progressive training routine that prevents the model from learning behaviors that are specific to number and instead pushes it to learn behaviors that can be repeated indefinitely.
arXiv Detail & Related papers (2022-02-11T18:43:28Z) - A new perspective of paramodulation complexity by solving massive 8
puzzles [0.4514386953429769]
A sliding puzzle is a combination puzzle where a player slide pieces along certain routes on a board to reach a certain end-configuration.
It turned out that by counting the number of clauses yielded with paramodulation, we can evaluate the difficulty of each puzzle.
arXiv Detail & Related papers (2020-12-15T11:47:47Z) - PuzzLing Machines: A Challenge on Learning From Small Data [64.513459448362]
We introduce a challenge on learning from small data, PuzzLing Machines, which consists of Rosetta Stone puzzles from Linguistic Olympiads for high school students.
Our challenge contains around 100 puzzles covering a wide range of linguistic phenomena from 81 languages.
We show that both simple statistical algorithms and state-of-the-art deep neural models perform inadequately on this challenge, as expected.
arXiv Detail & Related papers (2020-04-27T20:34:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.