Giter VIP home page Giter VIP logo

zed's Introduction

Z3-Python scripts to solve N-queens type puzzles on a Stratego board

Language Standard License

Fabienne : Whose motorcycle is this?
Butch : It's a chopper, baby.
Fabienne : Whose chopper is this?
Butch : It's Zed's.
Fabienne : Who's Zed?
Butch : Zed's dead, baby. Zed's dead.

Six Easy Pieces

This repository was inspired by a series of six puzzles initiated on the Stratego.com web forum. Below a brief description and solutions to all six puzzles, presented in increasing level of sophistication (which is not entirely the chronological order).
The solution diagrams use . to denote an empty square, # as an inaccessible and impassable lake, B as a bomb, and 2 as a scout (which is 2nd in the ranking of the various pieces).

Installation

All solutions were generated by Microsoft's open scource Z3-solver, using its Python bindings (and NumPy for array manipulations). You can easily reproduce the analyses on a machine with Python 3 and the pip package installer:

git clone https://github.com/rhalbersma/zed.git
cd zed
python3 -m pip install virtualenv
python3 -m virtualenv .env
source .env/bin/activate
pip install -r requirements.txt

and you are good to go to run the various scripts in this repo's src folder. All the dependencies are handled for you through the virtual environment. Once you are done with the analysis, you can run

deactivate

to get back your regular development environment.

I The minimum number of bombs on a Stratego setup area such that each 2x3 and 3x2 rectangle contains at least one bomb

This puzzle was first posted (without answer) in February 2014 by forum member maxroelofs.
In November 2017, I posted the answer (at the time, using a brute force C++ program to confirm my hand-made solution).
The minimum number of bombs satisfying the constraints == 6.
Z3 finds the solution by direct minimization within 1 second.

. . . . . . . . . .
. B . . B . . B . .
. . B . . B . . B .
. . . . . . . . . .

II The minimum number of bombs on a Stratego setup area such that each 2x3, 3x2 and 1x6 rectangle contains at least one bomb

This puzzle and its answer were first posted in February 2014 by forum member Napoleon 1er.
The link to the original answer no longer shows the solution diagram.
In November 2017, I posted the answer (at the time, using a brute force C++ program to confirm my hand-made solution).
The minimum number of bombs satisfying the constraints == 7.
Z3 finds the solution by direct minimization within 1 second.

. . . . . B . . . .
. B . . B . . B . .
. . B . . . . . B .
. . . . . B . . . .

III The minimum number of scouts on a Stratego board such that each square is occupied or threatened by a scout

In graph theory, this number is called the domination number.
In November 2017, I posted this puzzle and its answer (at the time, an unverified hand-made solution).
The minimum number of scouts satisfying the constraints == 8.
Z3 finds the solution by direct minimization within 1 second.

. 2 . . . . . . . .
. . . . . 2 . . . .
. 2 . . . . . . . .
2 . . . . . . . . .
. . # # . . # # . .
. . # # . . # # . .
. . . . . . . . . 2
. . . . . . . . 2 .
. 2 . . . . . . . .
. . . . 2 . . . . .

IV The maximum number of scouts on a Stratego board such that no scout threatens another scout

In graph theory, this number is called the the independence number.
This puzzle and its answer were first posted in February 2014 by forum user Napoleon 1er.
The link to the original answer no longer shows the solution diagram.
In November 2017, I posted the answer (at the time, an unverified hand-made solution).
The maximum number of scouts satisfying the constraints == 14.
Z3 finds the solution by direct minimization within 1 second.

. . . . . . 2 . . .
. . . 2 . . . . . .
. . . . . . . 2 . .
. . 2 . . . . . . .
2 . # # 2 . # # . 2
. 2 # # . 2 # # 2 .
. . . 2 . . . . . .
. . . . . . . 2 . .
. . 2 . . . . . . .
. . . . . . 2 . . .

V The maximum number of scouts on a Stratego board such that each scout threatens exactly one other scout

This puzzle was first posted (without answer) in February 2014 by forum member maxroelofs.
In July 2018, I posted the answer (using the Z3-solver).
The maximum number of scouts satisfying the constraints == 18.
Z3 proofs N == 18 within 1 second, and disproofs N == 20 within a minute.
Direct minimization seems out of reach since Z3 does not recognize that N has to be even.

2 . . . . . . . . .
. . . . . . . . . 2
. . . 2 . . . 2 . .
. . 2 . . . 2 . . .
. 2 # # . . # # . 2
2 . # # 2 2 # # 2 .
. . . . . . . . 2 .
. 2 . . . . . . . .
. . . . . . 2 2 . .
. . 2 2 . . . . . .

VI The maximum number of scouts on a Stratego board with at most 6 bombs in each setup area such that no scout threatens another scout

This puzzle was first posted (without answer) in February 2014 by forum member The Prof.
In July 2018, I posted the answer obtained from private communication with computer scientist Wieger Wesselink.
This solution had been found by Wesselink in collaboration with his colleague Hans Zantema (using the Z3-solver).
The maximum number of scouts satisfying the constraints == 24.
My current Z3 script proofs N == 24 within 15 minutes, and finds no disproof for N == 25 within an hour.
The Wesselink-Zantema approach manages to proof/disproof N == 24/25 within 10 seconds each.

. . . 2 B 2 . . . . 
. . 2 B 2 B 2 . . . 
. . . 2 B 2 B 2 . . 
. . . . 2 B 2 . . . 
2 . # # . . # # 2 . 
. . # # . 2 # # . 2 
. . . 2 . B 2 . . . 
. . 2 B . 2 B 2 . . 
. 2 B 2 B . 2 . . . 
. . 2 B 2 . . . . .

Contributing

The Z3-solver is easy to use, but also easy to misuse. In particular, it's hard to predict its performance.
A constraint rewrite, or even a reordering can induce a 10X speedup, or a 10X speed penalty.
The following open challenges are identified (pull requests welcome!):

  • Make problem 5 amenable to direct minimization
  • Push problem 6 to within the same ballpark as the Wesselink-Zantema approach

Apart from accepting answers to these challenges, this repo is in maintenance mode and no longer actively being developed.

Acknowledgments

Thanks to Wieger Wesselink for introducing me to the world of SMT solvers, for stimulating discussion, and for staying 100X ahead of me on the sixth and hardest puzzle.

License

Copyright Rein Halbersma 2018-2021.
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

zed's People

Contributors

dependabot[bot] avatar rhalbersma avatar

Stargazers

 avatar  avatar

Watchers

 avatar  avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.