jsgonsette / wizium Goto Github PK

View Code? Open in Web Editor NEW

55.0 5.0 17.0 1.66 MB

Insanely fast crossword generator

Home Page: https://jsgonsette.github.io/projects/wizium

License: GNU General Public License v3.0

CMake 0.74% C++ 80.25% Python 18.90% Batchfile 0.11%

crossword-generator crossword crossword-puzzle backtracking-algorithm

wizium's Introduction

Wizium

This project is a crosswords generator engine able to generate grids from dictionaries, as depicted below. The generator is very fast and can work with initial constraints like fixed black boxes pattern or words already in place on the grid.

The engine comes as a library written in C++. A python wrapper is available right now, other languages may be easily added.

A high level explanation of this project can be found on my blog (in French) or on Medium (in English).

How to compile the library

If you are on Windows and do not want to compile the library, you can simply use the pre-generated one available here and skip this step. Otherwise, any C++ compiler should fit your needs. Currently it has been tested with Visual Studio on Windows and GCC on Linux.

The CMakelists.txt file in the source directory let you use CMake for the generation on any platform.
On Windows, you can find Visual Studio projects in the Projects directory.

Compile on Windows with Visual Studio

Assuming Visual Studio is installed on your machine,

Launch the "Developer Command Prompt" from the start menu;
Run the command: msbuild ./Projects/VS2017/libWizium.vcxproj -p:Configuration=Release -p:Platform=x64;
The DLL should be created in the ./Binaries/Windows directory.

Compile with CMake on Windows

Assuming CMake and Visual Studio are installed on your machine,

Step in cmake directory
Run the command cmake -DCMAKE_GENERATOR_PLATFORM=x64 ..\Sources\
Run the command cmake --build . --config Release --target install
The DLL should be created in the ./Binaries/Windows directory.

Compile with CMake on Linux

Assuming CMake in installed on your machine,

Step in cmake directory
Run the command cmake ../Sources/ -DCMAKE_INSTALL_PREFIX="$(pwd)"
Run the command make
Run the command make install
The SO should be created in the ./Binaries/Linux directory.

Wrappers

C

The library API is declared in the file libWizium.h.

It contains the following functions:

WIZ_Init: Initialize the library;
WIZ_CreateInstance: Create a new independent module;
WIZ_DestroyInstance: Destroy a module;
DIC_Clear: Flush the dictionary content;
DIC_AddEntries: Add entries to the dictionary;
DIC_FindRandomEntry: Find a random entry in the dictionary, matching a mask;
DIC_FindEntry: Find a random entry in the dictionary, matching a mask;
DIC_GetNumWords: Return the number of words in the dictionary;
GRID_Erase: Erase the grid content;
GRID_SetSize: Set the grid size. Content can be lost when shrinking;
GRID_SetBox: Set the type of box at a given grid coordinate;
GRID_Write: Write a word on the grid;
GRID_Read: Read the whole content of the grid;
SOLVER_Start: Start the grid generation process;
SOLVER_Step: Move a few steps in the grid generation process;
SOLVER_Stop: Stop the grid generation process;

Python

libWizium.py is a Python wrapper giving full access to the engine capabilities. A Wizium module instance can be created through the Wizium class, provided the path to the libWizium library file. Except for the initialization that is handled automatically, there is a 1-to-1 correspondence between this class functions and the their equivalents in C.

This class provides the following API:

dic_clear: Flush the dictionary content;
dic_add_entries: Add entries to the dictionary;
dic_find_random_entry: Find a random entry in the dictionary, matching a mask;
dic_find_entry: Find a random entry in the dictionary, matching a mask;
dic_gen_num_words: Return the number of words in the dictionary;
grid_erase: Erase the grid content;
grid_set_size: Set the grid size. Content can be lost when shrinking;
grid_set_box: Set the type of box at a given grid coordinate;
grid_write: Write a word on the grid;
grid_read: Read the whole content of the grid;
solver_start: Start the grid generation process;
solver_step: Move a few steps in the grid generation process;
solver_stop: Stop the grid generation process;

The general philosophy consists in

Fill in the dictionary with any list of words;
Setup the grid canvas: size, holes, black boxes, imposed words;
Use the solver to complete the grid;

A functional out of the box example is provided in testWizium.py.

wizium's People

Contributors

Stargazers

Watchers

Forkers

rahuljain1310 luizv 0xflotus crsnplusplus psenough bozzzzo dingmingxin arkadiuminc vfraziers enatsek katahiromz themkots gutjuri workerjinqi guillaumepotier sopiarium hoverbird

wizium's Issues

On square grids, the code tends to find the same fill words up and across

This is a great code, and about 8x faster than what I had coded up in pure python (not too surprising). However, below is just one example of many different results that I've gotten when running Wizium on an empty square grid:

      BOLANCI
      OHANIAN
      LAAGERS
      ANGELIA
      NIELSON
      CARIOLE
      INSANER

It looks like the solver could use some logic to keep from using the same words down and across?

Some feedback: Get chosen words list? and issues when generating

Thanks for the library, it works quite well. I have some feedback, not sure if the project is still maintained.

Can the python wrapper return the list of words eventually used in the crossword puzzle? I think it would be helpful if you want to generate the hints and numbers.
The status (draw() function) doesn't appear to be filled it. I just get a grid shown with # and .
If the library couldn't generate a crossword, is it possible to provide a reason? Especially if there is a lack of words of a certain length, that could be very helpful. I ran into this as there aren't readily and available lists of words + hints, I made my own one, but it lacked a bit of 3 letter words.

Mac users

Hello! Great project. I'm trying to learn more about crossword generator algorithms and found your repository and articles. I'm a Mac user and not so experienced with cross platforms.

Do you have any tips about how I could run it on a Mac? At least the python wrapper? I tried cmake, but with no success. Meanwhile I'll keep trying to make it work.

Thank you!

Choose grid type when generating with black square placement

When we generate a grid with black square placement by the library it always creates a uk style grid, is it possible to create a USA style one?

Support for barred grids

Do you think the project can be modified to also support barred grids? Are you interested in supporting them?
If it's straightforward, I might try to implement it myself.

Compiling with project files result in a faulty .dll file

Hello, thanks for this great project!

I was trying to add a few functions to the c++ code, but I noticed that I can't use the dll I get out of compiling the projects in the Projects folder.

If I try to use the resulting dll, I get the following error message when trying to run testWizium.py:

Traceback (most recent call last):
File "C:\Users\Xeon\source\repos\TxtToJson\Wizium-master\TestWizium.py", line 263, in
example_1()
File "C:\Users\Xeon\source\repos\TxtToJson\Wizium-master\TestWizium.py", line 168, in example_1
wiz = Wizium (os.path.join (os.getcwd (), PATH),alphabet="abcdefghijklmnopqrstuvwxyz")
File "C:\Users\Xeon\source\repos\TxtToJson\Wizium-master\libWizium.py", line 129, in init
api = proto ((func_name, self._dll), None)
AttributeError: function 'WIZ_Init' not found
Exception ignored in: <function Wizium.del at 0x00000141AC6851F0>
Traceback (most recent call last):
File "C:\Users\Xeon\source\repos\TxtToJson\Wizium-master\libWizium.py", line 156, in del
self._wiz_destroy_instance ()
File "C:\Users\Xeon\source\repos\TxtToJson\Wizium-master\libWizium.py", line 445, in _wiz_destroy_instance
instance = ctypes.c_ulonglong (self._instance)
AttributeError: 'Wizium' object has no attribute '_instance'

However this error is not present with the sample dll you provided.

I have tried:

Using VS2019 and setting sdk to 10.17134 and platform tools to v141
Using VS2017
Using cmake

and couldn't make it work.

Prevent Solver to re-use a word already on Grid

Hi there,

First of all, thanks a lot for this great project!

I'd like to add a feature/option in the Solver, to avoid picking again a word already used in the Grid. I first thought to create a Dictionary.removeEntry once a word is put in the Grid but it won't do because of the generating process, the word in the Grid could be removed later if we find a dead-end, and without it in the Dictionary anymore it could be a mess..

Do you have any idea on how to implement that?

Maybe a forbiddenMask/forbiddenWords on the findEntry method?

Thanks a lot for your help.

Best

Can you explain what the heuristic_level does?

Can you explain what the heuristic_level in wiz.solver_start does?

Possibly missing instructions to compile on linux

The instructions for linux didn't work for me, when running make install I got the following error:

Consolidate compiler generated dependencies of target libWizium
[100%] Built target libWizium
Install the project...
-- Install configuration: ""
CMake Error at cmake_install.cmake:52 (file):
  file cannot create directory: /usr/local/./../Binaries/Linux.  Maybe need
  administrative privileges.
make: *** [Makefile:100: install] Error 1

Apparently there is some prefix that needs to be configured, I got it to work if I run CMAKE_INSTALL_PREFIX=/path/to/cloned/Wizium/ cmake ../Sources/ at the start of the instructions instead.

I don't know cmake etc. well so I don't know if it's the best way to solve this.

Platform:

Ubuntu 22.04
cmake 3.22.1