dlx/main.cpp at master · fritzm/dlx · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include "Iq.hpp"
#include "Pentominoes.hpp"
#include "Pyramid.hpp"
#include "Queens.hpp"
#include "Soma.hpp"
#include "Sudoku.hpp"

#include "boost/any.hpp"
#include "boost/program_options.hpp"

#include <functional>
#include <iostream>
#include <memory>
#include <string>
#include <utility>
#include <vector>

using namespace std;
namespace po = boost::program_options;


void validate(
    boost::any& v,
    const std::vector<std::string>& values,
    Pentominoes** target_type, int)
{
    static map<string, function<Pentominoes *()>> factories = {
        { "6x10", [](){ return new Pentominoes6x10(); }},
        { "5x12", [](){ return new Pentominoes5x12(); }},
        { "4x15", [](){ return new Pentominoes4x15(); }},
        { "3x20", [](){ return new Pentominoes3x20(); }}
    };

    po::validators::check_first_occurrence(v);
    auto s = po::validators::get_single_string(values);

    auto it = factories.find(s);
    if (it != factories.end()) {
        v = boost::any(it->second());
    } else {
        throw po::validation_error(po::validation_error::invalid_option_value);
    }
}


void checkGreaterZero(int value)
{
   if (value <= 0) {
       throw po::validation_error(po::validation_error::invalid_option_value);
   }
}


int main(int argc, const char *argv[])
{
    po::options_description opts;

    po::options_description puzzleOpts("Puzzle options (exactly one required)");
    puzzleOpts.add_options()
        ("iq", po::value<string>()->implicit_value(""),
            "IQ mini tiling puzzle (peg locations; empty will prompt, \"atlas\" will list")
        ("pentominoes", po::value<Pentominoes *>(),
            "pentominoes (one of: 6x10, 5x12, 4x15, or 3x20)")
        ("pyramid", po::bool_switch(),
            "Project Genius 3d pyramid puzzle")
        ("queens", po::value<int>()->notifier(checkGreaterZero),
            "n-queens (number of queens, greater than zero)")
        ("soma", po::bool_switch(),
            "Soma cube puzzle")
        ("sudoku", po::bool_switch(),
            "Sudoku solver (will prompt for puzzle input)");

    po::options_description generalOpts("General options");
    generalOpts.add_options()
        ("count", po::bool_switch(), "just print count of solutions")
        ("help,h", "produce help message");

    opts.add(puzzleOpts).add(generalOpts);

    auto usage = [&opts](){
        cout << opts << endl;
    };

    try {

        po::variables_map vm;
        po::store(po::parse_command_line(argc, argv, opts), vm);
        po::notify(vm);

        if ((argc == 1) || vm.count("help")) {
            cout << "Exact cover puzzle solver using Don Knuth \"Dancing Links\" algorithm" << endl;
            cout << "(see https://arxiv.org/abs/cs/0011047)" << endl;
            usage();
            return 1;
        }

        if ((vm.count("pentominoes")
            + (vm["pyramid"].defaulted() ? 0 : 1)
            + vm.count("queens")
            + (vm["soma"].defaulted() ? 0 : 1)
            + (vm["sudoku"].defaulted() ? 0 : 1)
            + (vm.count("iq")))
            != 1)
        {
            throw po::error_with_no_option_name("must specify exactly one puzzle option");
        }

        if (vm.count("pentominoes")) {
            unique_ptr<Pentominoes> puzzle(vm["pentominoes"].as<Pentominoes *>());
            puzzle->solve(vm["count"].as<bool>());
        } else if (vm.count("queens")) {
            auto puzzle = make_unique<Queens>(vm["queens"].as<int>());
            puzzle->solve(vm["count"].as<bool>());
        } else if (vm["pyramid"].as<bool>()) {
            auto puzzle = make_unique<Pyramid>();
            puzzle->solve(vm["count"].as<bool>());
        } else if (vm["soma"].as<bool>()) {
            auto puzzle = make_unique<Soma>();
            puzzle->solve(vm["count"].as<bool>());
        } else if (vm["sudoku"].as<bool>()) {
            auto puzzle = make_unique<Sudoku>();
            puzzle->solve(vm["count"].as<bool>());
        } else if (vm.count("iq")) {
            auto pegs = vm["iq"].as<string>();
            if (pegs == "atlas") {
                vector<pair<int, string>> atlas;
                for(auto p1: string("ABFGHILQ")) {
                    for(auto p2: string("DEJOTXY")) {
                        for(auto p3: string("MNPRUVW")) {
                            pegs = string("")+p1+p2+p3;
                            auto puzzle = make_unique<Iq>(pegs);
                            auto count = puzzle->solve(true, true);
                            atlas.push_back({count, pegs});
                        }
                    }
                }
                sort(atlas.begin(), atlas.end());
                for(auto& p: atlas) {
                    cout << p.second << ": " << p.first << endl;
                }
            } else {
                auto puzzle = make_unique<Iq>(pegs);
                puzzle->solve(vm["count"].as<bool>());
            }
        }

        return 0;
    }

    catch(po::error const& e) {
        cerr << e.what() << endl;
        usage();
        return 1;
    }
}