Utilities dlx

# The DLX Library

## The DLX library

The DLX library solves instances of the exact cover problem, using Dancing Links (Knuth’s Algorithm X).

Also included are programs that use the library:

• Suds: a sudoku solver that represents a sudoku puzzle as an exact cover problem instance.

• Grizzly: a "logic grid puzzle" solver. Requires my BLT library.

## Building everything

The following should work:

```\$ git clone https://github.com/blynn/blt
\$ git clone https://github.com/blynn/dlx
\$ cd dlx
\$ make
\$ ./suds < platinum.sud
\$ ./grizzly < zebra.gr```

## DLX example

Consider the following table, where the last column is optional:

0 1 2

0

1

0

1

1

0

1

1

2

0

1

0

3

1

1

0

Since covering the last column is optional, there are two solutions:

1. Rows 0 and 2.

2. Row 3 by itself.

The following program should confirm this.

```#include <stdio.h>
#include "dlx.h"
int main() {
// Initialize a new exact cover instance.
dlx_t dlx = dlx_new();

// Setup the rows
dlx_set(dlx, 0, 0);
dlx_set(dlx, 0, 2);
dlx_set(dlx, 1, 1);
dlx_set(dlx, 1, 2);
dlx_set(dlx, 2, 1);
dlx_set(dlx, 3, 0);
dlx_set(dlx, 3, 1);

// Mark the last column as optional.
dlx_mark_optional(dlx, 2);

void f(int row[], int n) {
printf("Solution: rows:");
for(int i = 0; i < n; i++) {
printf(" %d", row[i]);
}
printf("\n");
}
dlx_forall_cover(dlx, f);

// Clean up.
dlx_clear(dlx);
return 0;
}```

## Suds

Suds reads from standard input and ignores all characters except for the digits and ".". Nonzero digits represent themsleves and "0" or "." represents an unknown digit.

Shows step-by-step reasoning when run with `-v`.

See `platinum.sud` for an example input.

## Grizzly

We view a logic grid puzzle as follows. Given a MxN table of distinct symbols and some constraints, for each row except the first, we are to permute its entries so that the table satisfies the constraints.

Grizzly reads a logic grid puzzle from standard input and prints all its solutions. If run with `--alg=brute`, Grizzly employs brute force instead of Dancing Links.

The input should begin with M lines of N space-delimited fields, terminated by "%%" on a single line by itself. This should be followed by the constraints. Each constraint is described by a single line containing space-delimited fields. The first field is the constraint type, and the remainder are symbols.

An example 2x3 puzzle:

```Alice Bob Carol
bandoneon kazoo theremin
%%
! Carol kazoo
= Alice theremin```

The meaning of each constraint type is as follows:

 ! given symbols lie in distinct columns = given symbols lie in the same column < column of 1st symbol lies left of column of 2nd symbol > column of 1st symbol lies right of column of 2nd symbol A column of 1st symbol is adjacent to column of 2nd symbol 1 column of 1st symbol lies one to the left of the column of 2nd symbol i column of 1st symbol contains exactly one of the following symbols ^ at most one column contains 2 or more of the given symbols p first 2 symbols lie in distinct columns; next 2 symbols lie in distinct columns; each column contains exactly 0 or 2 of these 4 symbols X group symbols in pairs; at most one of these pairs lie in the same column

Thus in the above example, the original logic puzzle might have stipulated that "Carol does not play the kazoo." and "Alice plays the theremin."

Grizzly prints the transpose of the solution, possibly out of order. In other words, the symbols in the same row in the input are instead in the same column in the output, and the first symbols of the rows in the output may be in a different order than the symbols in the first row of the input.

```Alice theremin
Carol bandoneon
Bob kazoo```

See `zebra.gr`, which encodes the Zebra Puzzle.

I’m still working on the constraint language. I chose one-character commands for easy typing and parsing.

Originally, "=" meant that one column contained at least 2 of the given symbols. This is easy to check in the brute force solver, and allows some puzzles to be encoded with fewer types of rules, but it is a troublesome constraint for the Dancing Links solver so I changed the meaning to the above.

The "p" constraint (I chose "p" for "pairs") can be rewritten as two "i" constraints plus one "!" constraint, but numerous puzzles contained clues describing equalities between sets of size 2, such as: "Of Jack and Jill, one is wearing mukluks and the other was born in Timbuktu."

I found no puzzles depended on the order of the input symbols in any row apart from the first, so I shelved my original plans to support this. Puzzles only seem to care about the order of the symbols in the first row.

The "X" constraint functions as a catch-all to handle constraints that seem tricky to otherwise describe.

See `COPYING` for details.

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

##### Command-line arguments parsing library.

argparse argparse - A command line arguments parsing library in C (compatible with C++). Description This module is inspired by parse-options.c (git)

##### A cross platform C99 library to get cpu features at runtime.

cpu_features A cross-platform C library to retrieve CPU features (such as available instructions) at runtime. Table of Contents Design Rationale Code

##### Standards compliant, fast, secure markdown processing library in C

Hoedown Hoedown is a revived fork of Sundown, the Markdown parser based on the original code of the Upskirt library by Natacha Porté. Features Fully s

##### CommonMark parsing and rendering library and program in C

cmark cmark is the C reference implementation of CommonMark, a rationalized version of Markdown syntax with a spec. (For the JavaScript reference impl

##### A cross-platform protocol library to communicate with iOS devices

libimobiledevice A library to communicate with services on iOS devices using native protocols. Features libimobiledevice is a cross-platform software

##### Platform independent Near Field Communication (NFC) library

*- * Free/Libre Near Field Communication (NFC) library * * Libnfc historical contributors: * Copyright (C) 2009 Roel Verdult * Copyright (C) 2009

##### A C library for parsing/normalizing street addresses around the world. Powered by statistical NLP and open geo data.

libpostal: international street address NLP libpostal is a C library for parsing/normalizing street addresses around the world using statistical NLP a

libvldmail Your friendly e-mail address validation library. Why? Did you know that parentheses, spaces and - according to the RFC 6531 document - emoj

##### A protocol buffers library for C

PBC PBC is a google protocol buffers library for C without code generation. Quick Example package tutorial; message Person { required string name =

• #### Having trouble debugging a memory leak

First -- this is almost assuredly my fault. But I have not had any luck in tracking down the problem.

Second -- the code works properly, and I get the correct solutions in a wide range of test cases. But there are memory leaks that eventually cause a crash when iterating over large numbers of variations of problems to solve with the dlx approach.

I created a minimal example that replicates the problem:

``````dlx_t dlx = dlx_new();

dlx_set(dlx, 0, 0);
dlx_set(dlx, 0, 1);
dlx_set(dlx, 1, 0);
dlx_set(dlx, 1, 1);
dlx_set(dlx, 2, 0);
dlx_set(dlx, 2, 1);

dlx_remove_row(dlx, 1);

dlx_clear(dlx);
``````

When run through `valgrind --leak-check=full --show-leak-kinds=all ./run_tests`, I get things like this:

``````==298812== 96 (48 direct, 48 indirect) bytes in 1 blocks are definitely lost in loss record 6 of 6
==298812==    at 0x4842839: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==298812==    by 0x115533: new1.0 (dlx.c:133)
==298812==    by 0x11561D: dlx_set (dlx.c:142)
==298812==    by 0x114EDB: Test_leak (trait_dlx.c:776)
==298812==    by 0x1163CB: CuTestRun (CuTest.c:190)
==298812==    by 0x116B4B: CuSuiteRun (CuTest.c:336)
==298812==    by 0x1172DB: RunAllTests (AllTests.c:84)
==298812==    by 0x11735D: main (AllTests.c:101)
``````

Removing the `dlx_remove_row()` call causes the memory leak to disappear.

Any thoughts as to what I am doing wrong?

Thanks!!

opened by fletcher 3
• #### compilation problem

Hi there blynn (I am still a little unsure of github etiquette; apologies if I'm not getting it right).

I followed the instructions in `dlx/README.asciidoc` but encountered some errors. Following edited slightly for clarity:

``````rstudio % git clone https://github.com/blynn/blt
Cloning into 'blt'...
[snip]
rstudio % git clone https://github.com/blynn/dlx
Cloning into 'dlx'...
[snip]
rstudio % cd dlx
dlx % make
cc -O3 --std=gnu99 -Wall -o grizzly grizzly.c dlx.c -I ../blt ../blt/blt.c
In file included from grizzly.c:19:
../blt/blt.h:65:21: error: function definition is not allowed here
int f(BLT_IT *it) { return fun(it), 1; }
^
../blt/blt.h:66:28: error: use of undeclared identifier 'f'
blt_allprefixed(blt, "", f);
^
[other similar errors here]
``````

I'm on macos 10.13.6. Can you advise?

opened by RobinHankin 2
###### Problem solutions and notes for upcoming intern season lol.

Problem solutions and notes for upcoming intern season lol.

4 Nov 28, 2021
###### The libxo library allows an application to generate text, XML, JSON, and HTML output using a common set of function calls. The application decides at run time which output style should be produced.

libxo libxo - A Library for Generating Text, XML, JSON, and HTML Output The libxo library allows an application to generate text, XML, JSON, and HTML

253 Dec 10, 2022
###### Sqrt OS is a simulation of an OS scheduler and memory manager using different scheduling algorithms including Highest Priority First (non-preemptive), Shortest Remaining Time Next, and Round Robin.

A CPU scheduler determines an order for the execution of its scheduled processes; it decides which process will run according to a certain data structure that keeps track of the processes in the system and their status. A process, upon creation, has one of the three states: Running, Ready, Blocked (doing I/O, using other resources than CPU or waiting on unavailable resource).

18 Apr 15, 2022
###### The C++ REST SDK is a Microsoft project for cloud-based client-server communication in native code using a modern asynchronous C++ API design. This project aims to help C++ developers connect to and interact with services.

The C++ REST SDK is a Microsoft project for cloud-based client-server communication in native code using a modern asynchronous C++ API design. This project aims to help C++ developers connect to and interact with services.

7.2k Jan 2, 2023
###### Example of transferring file data over BLE using an Arduino Nano Sense and WebBLE

BLE File Transfer Example of transferring file data over BLE to an Arduino Nano Sense using WebBLE. Overview This is an example of how to use Bluetoot

33 Dec 19, 2022
###### A chatroom made using C lang and websockets

Proc-C-mity A chatroom made using C lang and websockets

5 May 3, 2021
###### Hybrid Detect demonstrates CPU topology detection using multiple intrinsic and OS level APIs.

Hybrid Detect Hybrid Detect demonstrates CPU topology detection using multiple intrinsic and OS level APIs. First, we demonstrate usage of CPUID intri

38 Dec 23, 2022
###### Tool based in nodes to build GLSL shaders without any programming knowledge written in C using OpenGL and GLFW.

FNode Tool based in nodes to build GLSL shaders without any programming knowledge written in C using OpenGL and GLFW (raylib library). It contains a c

80 Dec 26, 2022
###### Isocline is a pure C library that can be used as an alternative to the GNU readline library

Isocline: a portable readline alternative. Isocline is a pure C library that can be used as an alternative to the GNU readline library (latest release

136 Dec 30, 2022
###### A linux library to get the file path of the currently running shared library. Emulates use of Win32 GetModuleHandleEx/GetModuleFilename.

whereami A linux library to get the file path of the currently running shared library. Emulates use of Win32 GetModuleHandleEx/GetModuleFilename. usag

3 Sep 24, 2022