Inleiding
Afgelopen feestdagen kreeg ik een puzzelboekje cadeau met binaire puzzels. Al jaren maakte ik soortgelijke, maar kleinere, puzzels in de wekelijkse tv-gids. Nu kon ik zeker een aantal maanden vooruit!
Toen mijn helpende hand en ik eenmaal de vier mogelijke strategiën onder de knie hadden, waren de meeste puzzels binnen een kwartier compleet. Maar soms zagen we simpelweg niet waar de volgende stap zou zijn. De puzzel bleef dan voor alsnog onopgelost.
Voor dát geval wilde ik een stuk code schrijven dat mij een hint zou geven met welke strategie en in welke cel zich de volgende stap zou kunnen afspelen. Hieronder zal ik het proces van de totstandkoming bespreken, gevolgd door een korte analyse van de code zelf. Het eindresultaat is op FWieP.nl te bewonderen. De volledige broncode is sinds mei 2021 op Github beschikbaar.
Update
Meer dan drie jaar nadat ik dit artikel plaatste, nam John Segers met mij contact op en meldde dat mijn oplosser zich niet aan zijn eigen regels hield. Bij het oplossen van de door mij ingestelde voorbeeldpuzzel, bevatte de uiteindelijke puzzel drie verticale enen onder elkaar – en dat is absoluut niet toegestaan!
Met deze feedback ging ik op zoek in de code en vond de boosdoener. Na het succesvol toepassen van een strategie op een rij of kolom werd niet gecontroleerd of door deze stap de kruisende kolom of rij misschien ongeldig werd. Toen ik deze check inbouwde, bleek mijn voorbeeldpuzzel onoplosbaar! Dankjewel, John :).
Toen ik de code toch eenmaal onder handen had, besloot ik haar meteen PEAR-compatibel te maken, zoals al mijn huidige projecten. Tot slot gooide ik de volgorde van het toepassen van de verschillende strategiën om:
- eerst met strategie 1 alle rijen, dan kolommen
- dan met strategie 2 alle rijen, dan kolommen
- etc…
Aanpak
Aangezien ik thuis ben in PHP besloot ik er een webapplicatie van te maken. Eerst de logica en daarna de formulier(en) voor in de browser. Met die eerste stap was ik een behoorlijk tijdje zoet, en liep uiteindelijk tegen een beperking aan: ik kon bij één van de strategiën de vertaalslag van een procedure in mijn hoofd naar code niet maken. Ik zag niet hoe ik de handelingen die ik moeiteloos op papier uitvoerde, moest omzetten naar instructies voor mijn programma.
Gelukkig kwam er hulp uit onverwachte hoek. Karin Schaap, een bevriende programmeur, bood aan om mee te kijken en haar steen bij te dragen aan dit stukje software. Ondanks het feit dat ze nog nooit met PHP had gewerkt, bracht de samenwerking tussen ons een code-dialoog op gang. Afgewisseld door korte trial-error-trial-succes momenten leidde dit tot een werkende oplosser!
Uitbreiding
Natuurlijk ging ik direct op zoek naar puzzels om mijn code te testen. Ik vond, onder meer op binarypuzzle.com, een groot aantal puzzels die mijn code glansvol en zonder problemen oplostte. Tot ik ook de 'zeer moeilijke' (very hard) puzzels probeerde; mijn code was niet slim genoeg! Er moest nog minimaal één strategie zijn die ik niet kende…
De uitleg die ik als basis had genomen voor mijn code reikte tot en met vier strategiën. De vijfde werd kort aangehaald op een andere pagina, maar dat soort wiskunde gaat ver boven mijn pet. Gelukkig was er ook een beschrijving die ik wél snapte. Ik ging aan de slag en bouwde de ontbrekende schakel in mijn ketting om de code te kraken.
Code
In deze webapplicatie wordt een HTML-textarea gebruikt om de puzzel in te
voeren. In de constructor van de klasse Puzzle wordt de rauwe tekst eerst
opgeschoond en gecontroleerd op juistheid. Tot slot wordt de puzzel opgesplitst
in losse cellen ($this->_cells).
<?php
class Puzzle
{
public function __construct(string $in)
{
// Clean up input
$in = preg_replace("/[^01.\n]/", '', $in);
$lines = explode("\n", trim($in));
$width = strlen($lines[0]);
$height = count($lines);
$oneline = str_replace("\n", '', $in);
// Puzzels bigger than 16x16 are too big to solve...
if (strlen($oneline) > 256) {
return false;
}
// Ensure that both width and height are even
if ($width % 2 != 0 || $height % 2 != 0) {
return false;
}
$this->_unsolved = $oneline;
$this->_width = $width;
$this->_height = $height;
$this->_amountMaxWide = intdiv($width, 2);
$this->_amountMaxHigh = intdiv($height, 2);
$this->_cells = str_split($oneline);
}
// ...
}
Oplossen
De hoofdfunctie van de oplosser is solve(). Ze bestaat uit een
while(true)-loop die met beleid wordt onderbroken of opnieuw gestart.
Eerst wordt stategie 1 losgelaten op de rijen, daarna op de kolommen van de
puzzel. Daarna volgen de andere strategiën. Als er na het uitvoeren van zo'n
stap iets is veranderd (een lege cel is ingevuld), dan wordt het hele proces
opnieuw gestart. De code werkt dus met zo eenvoudig mogelijke middelen, totdat
het niet anders kan.
private function _isSolved() : bool
{
return strpos(implode('', $this->_cells), '.') === false;
}
public const STRATEGY_1 = 1;
public const STRATEGY_2 = 2;
public const STRATEGY_3 = 4;
public const STRATEGY_4 = 8;
public const STRATEGY_5 = 16;
public function solve(int $strategies) : bool
{
$doStrategy1 = ($strategies & self::STRATEGY_1) > 0;
// same goes for strategy 2, 3, 4 and 5
while (true) {
if ($this->_isSolved()) {
return true;
}
$oldCells = implode('', $this->_cells);
for ($i = 1; $i <= 5; $i++) {
if (!${'doStrategy'.$i}) {
continue;
}
foreach ($this->_getRows() as $ix => $item) {
if ($this->_executeStrategy($item, $i, self::PUZLLE_ROW, $ix)) {
continue 3;
}
}
foreach ($this->_getColumns() as $ix => $item) {
if ($this->_executeStrategy($item, $i, self::PUZLLE_COL, $ix)) {
continue 3;
}
}
}
// If all this work didn't bring any change, break the loop.
if (strcmp($oldCells, implode('', $this->_cells)) === 0) {
return false;
}
}
return false;
}
Strategiën
In een binaire puzzel moet een rij of kolom aan een aantal voorwaarden voldoen. De rij of kolom mag niet leeg zijn, niet groter of kleiner dan de rest van de puzzel, mag geen drie nullen of enen naast elkaar hebben, of méér dan het maximaal aantal toegestane nullen en enen.
private function _isValid(string $str, int $rowcol) : bool
{
if (strcmp($str, '') === 0) {
return false;
}
if (stripos($str, '000') !== false) {
return false;
}
if (stripos($str, '111') !== false) {
return false;
}
switch ($rowcol) {
case self::PUZLLE_ROW:
return $this->_isValidRow($str);
break;
case self::PUZLLE_COL:
return $this->_isValidColumn($str);
break;
}
return false;
}
private function _isValidRow(string $row) : bool
{
$amount0 = substr_count($row, '0');
$amount1 = substr_count($row, '1');
if ($amount0 > $this->_amountMaxWide) {
return false;
}
if ($amount1 > $this->_amountMaxWide) {
return false;
}
return true;
}
private function _isValidColumn(string $col) : bool
{
$amount0 = substr_count($col, '0');
$amount1 = substr_count($col, '1');
if ($amount0 > $this->_amountMaxHigh) {
return false;
}
if ($amount1 > $this->_amountMaxHigh) {
return false;
}
return true;
}
De functie die alle strategiën aanroept moet controleren of het resultaat van zo'n aanroep geldig is. Zo ja, wordt de nieuwe rij of kolom teruggeplaatst in de puzzel en kan het oplossen weer van voren af aan beginnen.
private function _validPuzzle() : bool
{
foreach ($this->_getRows() as $row) {
if (!$this->_isValid($row, self::PUZLLE_ROW)) {
return false;
}
}
foreach ($this->_getColumns() as $col) {
if (!$this->_isValid($col, self::PUZLLE_COL)) {
return false;
}
}
return true;
}
private function _executeStrategy(
string $oldItem, int $strategy, int $rowcol = -1, int $ix = -1
) : bool {
$newItem = $oldItem;
switch ($strategy) {
case 1: $newItem = $this->_strat1($oldItem, $rowcol);
break;
case 2: $newItem = $this->_strat2($oldItem, $rowcol);
break;
case 3: $newItem = $this->_strat3($oldItem, $rowcol);
break;
case 4: $newItem = $this->_strat4($oldItem, $rowcol);
break;
case 5: $newItem = $this->_strat5($oldItem, $rowcol);
break;
}
if (!$this->_isValid($newItem, $rowcol)) {
return false;
}
if (strcmp($newItem, $oldItem) !== 0) {
// See if new row causes the puzzle's columns to become invalid
// or if new column causes the puzzle's rows to become invalid
$dummyThis = clone $this;
switch ($rowcol) {
case self::PUZLLE_ROW:
$dummyThis->_setRow($newItem, $ix);
break;
case self::PUZLLE_COL:
$dummyThis->_setColumn($newItem, $ix);
break;
}
if (!$dummyThis->_validPuzzle()) {
return false;
}
$step = new PuzzleStep($strategy);
switch ($rowcol) {
case self::PUZLLE_ROW:
$step->setRowIndex($ix);
$this->_setRow($newItem, $ix);
break;
case self::PUZLLE_COL:
$step->setColIndex($ix);
$this->_setColumn($newItem, $ix);
break;
}
$step->setOldRowValue($oldItem);
$step->setNewRowValue($newItem);
$this->_steps[] = $step;
return true;
}
return false;
}
1: Duo's en trio's
Tussen twee nullen staat altijd een één: 0.0 wordt 010. Tussen twee enen
staat altijd een nul: 1.1 wordt 101. Naast twee nullen staat altijd een één:
00. wordt 001, .00 wordt 100. Naast twee enen staat altijd een nul:
11. wordt 110, .11 wordt 011.
private static function _strat1(string $str) : string
{
$replaceCount = 0;
$str = preg_replace('/00\./', '001', $str, 1, $replaceCount);
if ($replaceCount > 0) {
return $str;
}
$str = preg_replace('/\.00/', '100', $str, 1, $replaceCount);
if ($replaceCount > 0) {
return $str;
}
$str = preg_replace('/11\./', '110', $str, 1, $replaceCount);
if ($replaceCount > 0) {
return $str;
}
$str = preg_replace('/\.11/', '011', $str, 1, $replaceCount);
if ($replaceCount > 0) {
return $str;
}
$str = preg_replace('/0\.0/', '010', $str, 1, $replaceCount);
if ($replaceCount > 0) {
return $str;
}
$str = preg_replace('/1\.1/', '101', $str, 1, $replaceCount);
if ($replaceCount > 0) {
return $str;
}
return $str;
}
Een snellere en zeker efficiëntere methode van deze strategie zou gebruik maken
van str_replace, maar daarmee kun je niet elke vervanging (puzzelstap)
afzonderlijk vastleggen. En laat dát nou juist het doel zijn van deze oplosser :-)
2: Maximaal aantal 0's en 1's
Een rij (kolom) bevat altijd evenveel nullen als enen. Als de nullen 'op zijn', moeten de resterende cellen met enen worden gevuld; en vice versa.
private function _strat2(string $str) : string
{
$amount0 = substr_count($str, '0');
$amount1 = substr_count($str, '1');
$amountXX = substr_count($str, 'xx');
$amountEmp = substr_count($str, '.');
$amount0 += $amountXX;
$amount1 += $amountXX;
if ($amountEmp == 1) {
$toInsert = $amount0 < $amount1 ? '0' : '1';
$str = str_replace('.', $toInsert, $str);
return $str;
}
if ($amount0 == $this->_amountMax) {
$str = str_replace('.', '1', $str);
return $str;
}
if ($amount1 == $this->_amountMax) {
$str = str_replace('.', '0', $str);
return $str;
}
if ($amount0 == $this->_amountMax - 1) {
$options = [];
for ($i = 0; $i < $this->_size; $i++) {
if (substr($str, $i, 1) != '.') {
continue;
}
$tmpOption = substr_replace($str, '0', $i, 1);
$tmpOption = str_replace('.', '1', $tmpOption);
if (self::_isValidRow($tmpOption)) {
$options[] = $tmpOption;
} else {
$tmpOption = substr_replace($str, '1', $i, 1);
return $tmpOption;
}
}
if (count($options) == 1) {
$str = reset($options);
return $str;
}
}
if ($amount1 == $this->_amountMax - 1) {
$options = [];
for ($i = 0; $i < $this->_size; $i++) {
if (substr($str, $i, 1) != '.') {
continue;
}
$tmpOption = substr_replace($str, '1', $i, 1);
$tmpOption = str_replace('.', '0', $tmpOption);
if (self::_isValidRow($tmpOption)) {
$options[] = $tmpOption;
} else {
$tmpOption = substr_replace($str, '0', $i, 1);
return $tmpOption;
}
}
if (count($options) == 1) {
$str = reset($options);
return $str;
}
}
return $str;
}
3: 0..1 en 1..0 uitsluiten
Tussen een nul en één met twee cellen tussenruimte, staan altijd een nul en een
één. Bijvoorbeeld: 0..1 of 1..0. Dit gegeven kan worden gebruikt om met
strategie 2 deze twee lege cellen uit te sluiten.
private function _strat3(string $str) : string
{
$option = '';
if (strpos($str, '0..1') !== false) {
$option = preg_replace('/0\.\.1/', '0xx1', $str);
}
if (strpos($str, '1..0') !== false) {
$option = preg_replace('/1\.\.0/', '1xx0', $str);
}
if (!$option) {
return $str;
}
$newItem = self::_strat2($option);
$newItem = str_replace('xx', '..', $newItem);
return $newItem;
}
4: Unieke rijen vergelijken
Elke rij (kolom) is uniek. Als een rij (kolom) nog maar twee open cellen heeft, en er is een volledige rij (kolom) die verder identiek is, moeten de lege cellen 'andersom' worden ingevuld.
private function _strat4(string $str, int $rowcol) : string
{
if (substr_count($str, '.') != 2) {
return $str;
}
$optionA = $str;
$optionA = preg_replace('/\./', '1', $optionA, 1);
$optionA = preg_replace('/\./', '0', $optionA, 1);
$optionB = $str;
$optionB = preg_replace('/\./', '0', $optionB, 1);
$optionB = preg_replace('/\./', '1', $optionB, 1);
switch ($rowcol) {
case self::PUZLLE_ROW: $items = $this->_getRows();
break;
case self::PUZLLE_COL: $items = $this->_getColumns();
break;
default: $items = array();
break;
}
foreach ($items as $ix2 => $item2) {
if ($item2 == $optionA) {
$newItem = $optionB;
} else if ($item2 == $optionB) {
$newItem = $optionA;
} else {
$newItem = '';
}
if ($this->_isValidRow($newItem)) {
return $newItem;
} else {
continue;
}
}
return $str;
}
5: Alle mogelijkheden filteren
Maak een lijst van alle mogelijkheden voor het invullen van een rij (kolom) met lege cellen. Komen één of meer cellen daarvan overeen in alle mogelijkheden, dan is de inhoud van die cel zeker.
private function _strat5(string $str, int $rowcol) : string
{
if (!$this->_allPossibles) {
// Create the maximum binary number based on the puzzle's size
$size = $this->_size;
$maxBinary = str_repeat('1', $size);
// Get all possible numbers represented by the puzzle's rows (columns)
$all = range(0, bindec($maxBinary));
$all = array_map(
function ($x) use ($size) {
// Pad them with zeroes to the correct length
return sprintf("%0${size}b", $x);
}, $all
);
// Reduce to only valid rows (columns)
$all = array_filter($all, array(__CLASS__, '_isValidRow'));
// Cache for later usage
$this->_allPossibles = $all;
unset($all);
}
$possibles = array_filter(
$this->_allPossibles,
function ($x) use ($str) {
$xChars = str_split($x);
$strChars = str_split($str);
$charsCount = count($xChars);
// Find possible candidates for row (column) $str
for ($i = 0; $i < $charsCount; $i++) {
if ($strChars[$i] == '.') {
continue; // ... by skipping empty cells...
}
if ($strChars[$i] != $xChars[$i]) {
return false; // ... not including non-matching...
}
}
return true; // ... and keeping all others
}
);
switch ($rowcol) {
case self::PUZLLE_ROW: $items = $this->_getRows();
break;
case self::PUZLLE_COL: $items = $this->_getColumns();
break;
default: $items = [];
break;
}
// Exclude existing rows (columns)
$possibles = array_filter(
$possibles,
function ($x) use ($items) {
return array_search($x, $items) === false;
}
);
// Loop through $str by character
for ($i = 0; $i < $this->_size; $i++) {
if (substr($str, $i, 1) != '.') {
continue; // Skip empty cells
}
// Create a concatenated string of all possible values for this cell
$valuesOnIndexI = array_reduce(
$possibles,
function ($a, $b) use ($i) {
return $a.substr($b, $i, 1);
}, ''
);
// If the options only contain zeroes, then this cell MUST be 0
if (strpos($valuesOnIndexI, '0') !== false
&& strpos($valuesOnIndexI, '1') === false
) {
$str = substr_replace($str, '0', $i, 1);
return $str;
}
// If the options only contain ones, then this cell MUST be 1
if (strpos($valuesOnIndexI, '1') !== false
&& strpos($valuesOnIndexI, '0') === false
) {
$str = substr_replace($str, '1', $i, 1);
return $str;
}
}
return $str;
}