Curtis Bright: New Applications
https://www.maplesoft.com/applications/author.aspx?mid=345070
en-us2021 Maplesoft, A Division of Waterloo Maple Inc.Maplesoft Document SystemFri, 07 May 2021 15:37:49 GMTFri, 07 May 2021 15:37:49 GMTNew applications published by Curtis Brighthttps://www.maplesoft.com/images/Application_center_hp.jpgCurtis Bright: New Applications
https://www.maplesoft.com/applications/author.aspx?mid=345070
Graph Colouring with SAT
https://www.maplesoft.com/applications/view.aspx?SID=154550&ref=Feed
A colouring of a graph is an assignment of colours to its vertices such that every two adjacent vertices are coloured differently. Finding a colouring of a given graph using the fewest number of colours is a difficult problem in general. In this worksheet we demonstrate how to solve the graph colouring problem by translating it into Boolean logic and using Maple's built-in efficient SAT solver. This approach is now available as an option to Maple’s ChromaticNumber function, which also solves the graph colouring problem. Using SAT can dramatically improve the performance of this function in some cases, including the “queen graphs” problem shown in this application.<img src="https://www.maplesoft.com/view.aspx?si=154550/queens_colouring.png" alt="Graph Colouring with SAT" style="max-width: 25%;" align="left"/>A colouring of a graph is an assignment of colours to its vertices such that every two adjacent vertices are coloured differently. Finding a colouring of a given graph using the fewest number of colours is a difficult problem in general. In this worksheet we demonstrate how to solve the graph colouring problem by translating it into Boolean logic and using Maple's built-in efficient SAT solver. This approach is now available as an option to Maple’s ChromaticNumber function, which also solves the graph colouring problem. Using SAT can dramatically improve the performance of this function in some cases, including the “queen graphs” problem shown in this application.https://www.maplesoft.com/applications/view.aspx?SID=154550&ref=FeedMon, 09 Sep 2019 04:00:00 ZCurtis BrightCurtis BrightSolving the 15-puzzle
https://www.maplesoft.com/applications/view.aspx?SID=154509&ref=Feed
The 15-puzzle is a classic "sliding tile" puzzle that consists of tiles arranged in a 4 by 4 grid with one tile missing. The objective is to arrange the tiles in a sorted order only by making moves that slide a tile into the empty space. In this worksheet we demonstrate how this puzzle can be solved by encoding its rules into Boolean logic and using Maple's SAT solver.<img src="https://www.maplesoft.com/applications/images/app_image_blank_lg.jpg" alt="Solving the 15-puzzle" style="max-width: 25%;" align="left"/>The 15-puzzle is a classic "sliding tile" puzzle that consists of tiles arranged in a 4 by 4 grid with one tile missing. The objective is to arrange the tiles in a sorted order only by making moves that slide a tile into the empty space. In this worksheet we demonstrate how this puzzle can be solved by encoding its rules into Boolean logic and using Maple's SAT solver.https://www.maplesoft.com/applications/view.aspx?SID=154509&ref=FeedWed, 19 Dec 2018 05:00:00 ZCurtis BrightCurtis BrightInteractive Sudoku
https://www.maplesoft.com/applications/view.aspx?SID=154507&ref=Feed
This worksheet contains an interactive Sudoku game that allows one to play a game of Sudoku in Maple. New puzzles can be randomly generated, read from a file, or loaded an online source, and puzzles can be automatically solved.
No knowledge of Sudoku solving or puzzle generation was used in the implementation. Instead, the rules of Sudoku were encoded into Boolean logic and Maple's built-in SAT solver was used; source code and implementation details are included.<img src="https://www.maplesoft.com/view.aspx?si=154507/suduko.png" alt="Interactive Sudoku" style="max-width: 25%;" align="left"/>This worksheet contains an interactive Sudoku game that allows one to play a game of Sudoku in Maple. New puzzles can be randomly generated, read from a file, or loaded an online source, and puzzles can be automatically solved.
No knowledge of Sudoku solving or puzzle generation was used in the implementation. Instead, the rules of Sudoku were encoded into Boolean logic and Maple's built-in SAT solver was used; source code and implementation details are included.https://www.maplesoft.com/applications/view.aspx?SID=154507&ref=FeedMon, 03 Dec 2018 05:00:00 ZCurtis BrightCurtis BrightClique Finding with SAT
https://www.maplesoft.com/applications/view.aspx?SID=154502&ref=Feed
A clique of a graph is a subset of its vertices that are all mutually connected. Finding a clique of a given size in a graph is a difficult problem in general.
In this worksheet we demonstrate how to solve the clique finding problem by translating it into Boolean logic and using Maple's built-in efficient SAT solver. This approach even can out-perform the built-in Maple function FindClique which also solves the clique finding problem.<img src="https://www.maplesoft.com/view.aspx?si=154502/graph20.png" alt="Clique Finding with SAT" style="max-width: 25%;" align="left"/>A clique of a graph is a subset of its vertices that are all mutually connected. Finding a clique of a given size in a graph is a difficult problem in general.
In this worksheet we demonstrate how to solve the clique finding problem by translating it into Boolean logic and using Maple's built-in efficient SAT solver. This approach even can out-perform the built-in Maple function FindClique which also solves the clique finding problem.https://www.maplesoft.com/applications/view.aspx?SID=154502&ref=FeedThu, 15 Nov 2018 05:00:00 ZCurtis BrightCurtis BrightFinding Graeco-Latin Squares
https://www.maplesoft.com/applications/view.aspx?SID=154499&ref=Feed
A Latin square is an n by n arrangement of n items such that each item appears exactly once in each row and column. A Graeco-Latin square is a pair of two Latin squares such that all n^2 pairs of the items arise when one square is superimposed onto the other.
In this worksheet we use Maple's built-in efficient SAT solver to find Graeco-Latin squares without using any knowledge of search algorithms or construction methods.<img src="https://www.maplesoft.com/view.aspx?si=154499/Graeco-Latin-10.png" alt="Finding Graeco-Latin Squares" style="max-width: 25%;" align="left"/>A Latin square is an n by n arrangement of n items such that each item appears exactly once in each row and column. A Graeco-Latin square is a pair of two Latin squares such that all n^2 pairs of the items arise when one square is superimposed onto the other.
In this worksheet we use Maple's built-in efficient SAT solver to find Graeco-Latin squares without using any knowledge of search algorithms or construction methods.https://www.maplesoft.com/applications/view.aspx?SID=154499&ref=FeedWed, 07 Nov 2018 05:00:00 ZCurtis BrightCurtis BrightSolving the Einstein Riddle
https://www.maplesoft.com/applications/view.aspx?SID=154484&ref=Feed
The "Einstein Riddle" is a logic puzzle apocryphally attributed to Albert Einstein and is often stated with the remark that it is only solvable by 2% of the world's population. We can solve this puzzle using Maple's built-in efficient SAT solver.<img src="https://www.maplesoft.com/view.aspx?si=154484/Einstein_Riddle.jpg" alt="Solving the Einstein Riddle" style="max-width: 25%;" align="left"/>The "Einstein Riddle" is a logic puzzle apocryphally attributed to Albert Einstein and is often stated with the remark that it is only solvable by 2% of the world's population. We can solve this puzzle using Maple's built-in efficient SAT solver.https://www.maplesoft.com/applications/view.aspx?SID=154484&ref=FeedThu, 04 Oct 2018 04:00:00 ZCurtis BrightCurtis BrightSolving the World's Hardest Sudoku
https://www.maplesoft.com/applications/view.aspx?SID=154483&ref=Feed
Sudoku is a popular puzzle that appears in many puzzle books and newspapers. We can use Maple's built-in efficient SAT solver to quickly solve the "world's hardest Sudoku" without any knowledge of Sudoku solving techniques.<img src="https://www.maplesoft.com/view.aspx?si=154483/72f8a9282f0b80d9423ca565563bb9d6.gif" alt="Solving the World's Hardest Sudoku" style="max-width: 25%;" align="left"/>Sudoku is a popular puzzle that appears in many puzzle books and newspapers. We can use Maple's built-in efficient SAT solver to quickly solve the "world's hardest Sudoku" without any knowledge of Sudoku solving techniques.https://www.maplesoft.com/applications/view.aspx?SID=154483&ref=FeedThu, 04 Oct 2018 04:00:00 ZCurtis BrightCurtis BrightThe n-Queens Problem
https://www.maplesoft.com/applications/view.aspx?SID=154482&ref=Feed
The n-Queens problem is to place n queens on an n by n chessboard such that no two queens are mutually attacking. We can use Maple's built-in efficient SAT solver to quickly solve this problem.<img src="https://www.maplesoft.com/view.aspx?si=154482/nQueens.PNG" alt="The n-Queens Problem" style="max-width: 25%;" align="left"/>The n-Queens problem is to place n queens on an n by n chessboard such that no two queens are mutually attacking. We can use Maple's built-in efficient SAT solver to quickly solve this problem.https://www.maplesoft.com/applications/view.aspx?SID=154482&ref=FeedThu, 04 Oct 2018 04:00:00 ZCurtis BrightCurtis Bright