# Solving a Binary Puzzle

A while ago I started solving Binary Puzzles (also known as "binero"). Not having done much C++ in my life, although it feels like I have a pretty good understanding of C++ in general, I figured it was time to do some C++!

The rules for a Binary Puzzle are:

• The entire grid should be filled up with 1's and 0's.
• There cannot be more than two 1's and 0's consecutively together.
• There are an equal amount of 1's and 0's in each row and each column.
• All columns are unique and all rows are unique.

This code is able to solve all Easy and Medium puzzles on binarypuzzle.com. I realized later that I could solve these kinds of puzzles much easier using some already existing Java code I have written, which will be shown in an upcoming question.

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <fstream>
#include <string>

class BineroTile {
public:
BineroTile() {
clear();
}

bool zero;
bool one;

void clear() {
zero = true;
one = true;
}

bool hasValue() {
return zero ^ one;
}

int getValue() {
if (!hasValue()) {
return -1;
}
return one ? 1 : 0;
}

void set(int value) {
zero = value == 0;
one = value == 1;
}
friend std::ostream& operator<<(std::ostream& os, const BineroTile& dt);

void operator=(const int &value) {
set(value);
}

bool operator == (const BineroTile &other) const {
if (this->zero && this->one) {
return false;
}
return (this->zero == other.zero) && (this->one == other.one);
}
};

std::ostream &operator<<(std::ostream &os, const BineroTile &m) {
if (m.one && m.zero) {
return os << "_";
}
if (!m.one && !m.zero) {
return os << "#";
}
return os << (m.one ? "1" : "0");
}

class BineroMatch {
std::vector<BineroTile*> tiles;
int unknown;

public:
BineroMatch(std::vector<BineroTile*> tiles) : tiles(tiles) {
}

bool scan() {
bool simplified = false;
unsigned int zeros = 0;
unsigned int ones = 0;
for (unsigned int i = 0; i < tiles.size(); i++) {
BineroTile* current = tiles[i];

if (current->getValue() == 0) {
zeros++;
}
if (current->getValue() == 1) {
ones++;
}

if (i < tiles.size() - 1) {
BineroTile* next = tiles[i + 1];

// Find Pairs - compare the current value with the next value
if (*current == *next) {

int value = 1 - current->getValue();

if (i > 0) {
BineroTile* before = tiles[i - 1];
simplified |= !before->hasValue();
before->set(value);
}
if (i < tiles.size() - 2) {
BineroTile* after = tiles[i + 2];
simplified |= !after->hasValue();
after->set(value);
}
}

// Avoid trios - compare the current value with the value two steps next
if (i < tiles.size() - 2) {
BineroTile* twoNext = tiles[i + 2];
if (*current == *twoNext) {
int value = 1 - current->getValue();
simplified |= !next->hasValue();
next->set(value);
}
}
}
}

// Complete rows and columns
if (zeros + ones < tiles.size()) {
int halfSize = tiles.size() / 2;
int maxKnown = std::max(zeros, ones);
int value = zeros > ones ? 1 : 0;
if (halfSize == maxKnown) {
for (unsigned int i = 0; i < tiles.size(); i++) {
if (!tiles[i]->hasValue()) {
tiles[i]->set(value);
simplified = true;
}
}
}
}

if (tiles.size() - zeros - ones != unknown) {
unknown = tiles.size() - zeros - ones;
}

// Not implemented: Eliminate impossible combinations in this line
// Not implemented: Eliminate impossible combinations based on completed rows and columns
return simplified;
}

};

class BineroMatchSet {
std::vector<BineroMatch> matches;

public:
BineroMatchSet(std::vector<BineroMatch> matches) : matches(matches) {
}

bool scan() {
bool simplified = false;
for (auto match : matches) {
simplified |= match.scan();
}
return simplified;
}
};

class BineroPuzzle {
public:
int width;
int height;
std::vector<std::vector<BineroTile>> grid;
std::vector<BineroMatchSet> match_sets;

BineroPuzzle(int width, int height) : width(width), height(height) {
std::vector<BineroMatch> rows;
std::vector<BineroMatch> columns;

for (int y = 0; y < height; y++) {
std::vector<BineroTile> a;
std::vector<BineroTile*> rowPointers;
for (int x = 0; x < width; x++) {
BineroTile tile;
a.push_back(tile);
}
grid.push_back(a);
}

for (int x = 0; x < width; x++) {
std::vector<BineroTile*> columnTiles;
for (int y = 0; y < height; y++) {
BineroTile* tile = &grid[y][x];
columnTiles.push_back(tile);
}
columns.push_back(BineroMatch(columnTiles));
}

for (int y = 0; y < height; y++) {
std::vector<BineroTile*> rowTiles;
for (int x = 0; x < width; x++) {
BineroTile* tile = &grid[y][x];
rowTiles.push_back(tile);
}
rows.push_back(BineroMatch(rowTiles));
}

match_sets.push_back(BineroMatchSet(rows));
match_sets.push_back(BineroMatchSet(columns));
}

void print() {
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
std::cout << grid[y][x];
}
std::cout << "\n";
}
}

void clear() {
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
grid[y][x].clear();
}
}
}

void set(int x, int y, int value) {
grid[y][x].set(value);
}

void solve() {
bool simplified = false;
do {
simplified = false;
for (auto set : match_sets) {
simplified |= set.scan();
}
}
while (simplified);
}

};

struct Puzzle {
public:
BineroPuzzle puzzle;
Puzzle() : puzzle(BineroPuzzle(4, 4)) {}
};

std::cout << "Enter Dimension: ";
int size;
std::cin >> size;
BineroPuzzle* puzzle = new BineroPuzzle(size, size);

for (int y = 0; y < size; y++) {
for (int x = 0; x < size; x++) {
char ch;
std::cin >> ch;
if (ch == '1') {
puzzle->set(x, y, 1);
}
else if (ch == '0') {
puzzle->set(x, y, 0);
}
else if (ch == 'x') {
}
else {
std::cout << "Unknown char: " << ch;
}
}
}
return puzzle;
}

void readLine(BineroPuzzle* puzzle, const int y, const std::string line) {
for (unsigned int x = 0; x < line.length(); x++) {
char ch = line[x];
if (ch == '1') {
puzzle->set(x, y, 1);
}
else if (ch == '0') {
puzzle->set(x, y, 0);
}
}
}

std::ifstream file;
file.open(fileName);
std::string line;
if (file.is_open()) {
getline(file, line);
unsigned int size = line.length();
BineroPuzzle* puzzle = new BineroPuzzle(size, size);
for (unsigned int y = 1; y < size; y++) {
getline(file, line);
}
file.close();
return puzzle;
}
file.close();
BineroPuzzle* puzzle = new BineroPuzzle(1, 1);
return puzzle;
}

int main() {

puzzle->print();
std::cin.get();
std::cout << puzzle->width << " x " << puzzle->height << "\n";
puzzle->solve();
std::cout << "Solution:\n";
puzzle->print();
std::cin.get();
delete puzzle;
return 0;
}


Example puzzle.dat:

xxxx00
xxxxxx
x1xxxx
01x1xx
0xxx0x
xx1xxx


Primary questions:

• Am I making good usage of the operator functionalities of C++?

I know I could have created a more user-friendly menu and such, instead of switching the commented line or changing file name. This code is not really meant to be user-friendly, but I hope it is programmer-friendly.

• What do BineroTile, BineroMatch, BineroMatchSet, and BineroPuzzle translate into in English? My guess is BinaryTile, BinaryMatch, BinaryMatchSet, and BinaryPuzzle. – R Sahu Feb 19 '15 at 22:06
• @RSahu The reason why I am calling them Binero is because when I first encountered this puzzle, it went by the name of "Binero". The term Binary is so much wider than Binero, I would rather name it BinaryPuzzleTile, BinaryPuzzleMatch... which I feel would be too long. – Simon Forsberg Feb 19 '15 at 22:13

• You said

The entire grid should be filled up with 1's and 0's.

That means the only state in BineroTile should be a bool - true for 1 and false for 0. It's not clear why you need two bool members to capture BineroTile's state. What does it mean when one is true and zero is true? What's the state of that tile?

I am guessing that you want to capture "unspecified" as a state. In that case, an enum would be better.

class BineroTile {
public:
enum State { UNSPECIFIED = -1, ZERO, ONE };
State state;

// ...
};

• The operator= function

Idiomatically speaking, it's perfectly reasonable to use:

BineroTile tile;
tile = 1;


However, the signature of the function and the implementation need to be updated to be idiomatic:

BineroTile& operator=(const int &value) {
set(value);
return *this;
}


Then, you can use:

BineroTile tile1;
BineroTile tile2;
tile1 = tile2 = 1;

• Redundant data in BineroPuzzle

width and height are redundant member variables. Please remove them. You can get them from the grid member variable.

• Better initialization of BineroPuzzle::grid

You can use

BineroPuzzle(int width, int height) :
grid(height, std::vector<BineroPuzzle>(width, BineroTile())) {


to initialize grid. That will remove a block of code from BineroPuzzle's constructor.

• An enum definitely makes sense here. It is true that I want to capture the unspecified state. Both zero and one should not be true at the same time. About that tile1 = tile2 = 1; , if I understand that correctly, then tile1 and tile2 will refer to the same object after that assignment? (Unless I also implement the operator= that Jamal suggested?) – Simon Forsberg Feb 19 '15 at 23:15
• No, tile1 and tile2 will continue to be different objects. Their states will be identical. – R Sahu Feb 19 '15 at 23:21

I'll start with some of the basic conventions now. There is quite a bit of code here.

• This looks unusual for a constructor:

BineroTile() {
clear();
}


The call to a function called clear() makes this look like a destructor, though that's not even what's being done here.

If you're just trying to set initial values, use an initializer list:

BineroTile()
: zero(true)
, one(true)
{}

• This doesn't quite look right:

int getValue() {
if (!hasValue()) {
return -1;
}
return one ? 1 : 0;
}


What value is it getting? It looks like it'll return a boolean value depending on the state of one. Perhaps this should've been named something else.

• This operator= overload isn't in the proper form:

void operator=(const int &value) {
set(value);
}


You would typically use the argument as the right-hand operand to set the current object (this) to that operand. You're not doing that at all here.

Here's what it should look like:

BineroTile& operator=(const BineroTile &rhs) {
zero = rhs.zero;
one = rhs.one;
return *this;
}


In case you may need to check for self-assignment as well:

if (this != &rhs) {
zero = rhs.zero;
one = rhs.one;
}

return *this;


Moreover, you don't really have to overload operator= if you're just doing simple assignments. The compiler automatically generates a default assignment operator for you. One good reason to define your own operator= is if you have pointer members, which will not be handled properly automatically by the compiler. This is because the compiler-generated version performs a shallow copy instead of a deep copy.

• print() should also be const. This applies to all member functions, especially print functions, that don't modify any data members. Any attempts at modifying data members within such functions will result in a compiler error.

• In readFromFile(), I don't think the last close() is needed if file fails to open. This is usually only necessary for error-checking.

• Also in readFromFile(), there doesn't appear to be a need for new. In C++, unlike in Java, manual memory allocation is used very sparingly in favor of the classes in the standard library that handle memory itself. You are properly deallocating afterwards as you should, but again, it doesn't appear to be necessary here.

• the = operator was to quickly assign the tile to an int value, your version of the operator doesn't even compile! (or else I am missing something significant in C++...) There's no such thing as rhs.zero when rhs is an int. tile = 1 sets tile.one = true; tile.zero = false; So I'd say that I am using the argument as right-hand operand to set the current object... – Simon Forsberg Feb 19 '15 at 18:44
• @SimonAndréForsberg: You're right; I forgot to change something. The argument type should be BineroTile. – Jamal Feb 19 '15 at 18:46
• I don't want to set a tile to the same value as another tile, I want to set the tile's properties to the values of an int! (Judging by your answer though, I guess that's not really the usual practice, huh?) – Simon Forsberg Feb 19 '15 at 18:47
• @SimonAndréForsberg: In that case, operator= is not needed for that. Just a separate function will do. – Jamal Feb 19 '15 at 18:48
• I knew that it wasn't needed, I just wanted to use some of the features available to me in C++. – Simon Forsberg Feb 19 '15 at 18:50

## Separate interface from implementation

It makes the code somewhat longer for a code review, but it's often very useful to separate the interface from the implementation. In C++, this is usually done by putting the interface into separate .h files and the corresponding implementation into .cpp files. It helps users (or reviewers) of the code see and understand the interface and hides implementation details.

## Make data members private

The zero and one members of BineroTile are public but they really ought to be private members. Similarly, data members for BineroPuzzle should be made private. If you need accessors, you could use simple const ones like this:

int Width() const { return width; }
int Height() const { return height; }


## Use const where practical

The hasValue and getValue member functions of BineroTile do not alter the underlying object and therefore should be declared const.

## Isolate platform-specific code

If you must have stdafx.h, consider wrapping it so that the code is portable:

#ifdef WINDOWS
#include "stdafx.h"
#endif


## Avoid reusing the same name for different things

Inside your BinaroPuzzle::solve() function, you use a variable set for each match_set, but there is also a member function set. Although it's unambiguous to the compiler, it could be clearer to a reader of the code if that variable were named something else.

## Don't rely on uninitialized variables

In side the BinerorMatch::scan function, we have this peculiar code:

if (tiles.size() - zeros - ones != unknown) {
unknown = tiles.size() - zeros - ones;
}


The first problem is that unknown is, well, unknown at that point the first time through the code, so your code is making a decision based on an uninitialized value which is an error. It works anyway because unknown is then set to a particular value. Why not just set the value?

unknown = tiles.size() - zeros - ones;


## Prefer references to raw pointers

Within BineroMatch::scan(), variables current, next, before and after are all declared and used as pointers to BinaroTile but what you really want is a reference. The difference is that a reference cannot be nullptr and must actually point to an object, which is exactly the guarantee your code relies on anyway. Instead, I would do it like this:

BineroTile& current = *tiles[i];

if (current.getValue() == 0) {
zeros++;
}
// etc.


## Make your functions match typical usage

Every instance of use of hasValue() negates the result to use it. That strongly suggests that the function should probably be this instead:

bool isUnknown() const {
return zero == one;
}


Similarly, the code includes this:

if (current->getValue() == 0) {
zeros++;
}
if (current->getValue() == 1) {
ones++;
}


I would instead be inclined to write that as:

if (current->hasValue()) {
if (current->isZero()) {
++zeroes;
} else {
++ones;
}
}


## Use an idiomatic operator=

Your current BineroTile::operator=() is this:

void operator=(const int &value) {
set(value);
}


It should actually return BineroTile& and not void, otherwise chained operations such as a = b = c can't work. Since the result of this is just a simple copy, delete the whole function and let the compiler automatically generate it. However, you might want to create another form, like this:

BineroTile &operator=(bool value) {
one = value;
zero = !value;
return *this;
}


## Provide for more natural syntax

Rather than the somewhat strange thing that's being done with value inside BineroMatch::scan(), you might want to use the suggested operator= above and this:

bool operator!() const {
return zero;
}


That will allow you write much more clearly, as with this example:

if (i > 0) {
BineroTile& before = *tiles[i - 1];
simplified |= before.isUnknown();
before = !current;
}


## Eliminate unused structures and classes

The Puzzle struct is unused and should be deleted.

## Separate input from output

The BineroPuzzle::readFromInput() both prompts and reads. Better design would be to separate prompts from the actual input. Alternatively, since it's unused in this sample program, you could omit it.

## Reconsider your choice of data structures

The code currently uses a number of std::vectors for things that might be better expressed as std::valarray. Using a std::valarray would allow you to use a std::slice which seems like a better fit for this particular problem.

## Prefer constructors to special member functions

The readFromFile function has two problems, as I see it. First, it's a free-standing function and not a member function even though it's clearly closely associated with the BineroPuzzle class. Second, it returns a raw pointer rather than an actual object. Finally, the use of new and delete is really not needed here, especially since the value returned is never checked for nullptr. You can solve all of those problems by refactoring this as a constructor taking std::ifstream& as an input.

BineroPuzzle::BineroPuzzle(std::istream &file) {
std::string line;
getline(file, line);
unsigned int size = line.length();
BineroPuzzle puzzle(size, size);
for (unsigned int y = 1; y < size; y++) {
getline(file, line);
}
std::swap(*this, puzzle);
}


This could (and should!) be refactored further, including making readLine a private member function but I'll leave that to you.

## Prefer a stream inserter to a custom print routine

Your custom BineroPuzzle::print routine could instead be written as a stream inserter:

friend std::ostream& operator<<(std::ostream &out, const BineroPuzzle &bp) {
for (int y = 0; y < bp.Height(); y++) {
for (int x = 0; x < bp.Width(); x++) {
out << bp.grid[y][x];
}
out << "\n";
}
return out;
}


## Prefer for to do ... while

In BinaroPuzzle::solve() the loop is this:

void solve() {
bool simplified = false;
do {
simplified = false;
for (auto set : match_sets) {
simplified |= set.scan();
}
}
while (simplified);
}


A clearer alternative would be this:

void solve() {
for (bool simplified = true; simplified; ) {
simplified = false;
for (auto set : match_sets) {
simplified |= set.scan();
}
}
}


Or you could also use std::for_each and a lambda:

void solve() {
for (bool simplified = true; simplified; ) {
simplified = false;
std::for_each(match_sets.begin(), match_sets.end(),
[&simplified](BineroMatchSet &bms){
return simplified |= bms.scan();
}
);
}
}


## Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main.