Puzzles Solvers & OR tutorials

This repo provides useful, problem-tailored solvers for some interesting logic puzzles. The main tool I used in the repo is Google Operations Research software ORtools, especially its CS-SAT solver. Commercial solver Gurobi (Licence required, of course) is also used for specific puzzle (Like Slitherlink).

Most other solvers of those problems are based on logical methods, instead, this repo provides solvers based on mathematical Programming (Integer Programming(IP), Constraint Programming(CP) etc..). Just In case, I must say I always admire those who quickly come up with logic-based solutions for those problems, and this repo is NOT aimed at replacing logic method with Computer solvers. This repo is just for fun.

Besides, this repo also contains some dataset ( 2000+ instances for now) of specific puzzles. Details can be found in catalog. More dataset would be added in the future.

Lastly, this repo also contains some self-learning materials for Operations Research (OR).

✅ Python Environment: Python 3.10.12,

✅ Gurobi Optimizer Version: 10.0.3.

✅ ortools Optimizer Version: 9.7.2996

Catalog

---

Sudoku and variants puzzles

1. Ortools for diversified Sudoku-like Puzzles: 🥰 The very beginning of my repo. In this note, most of the sudokus (and variants) are well-designed so you can easily add or integrate different constraints types and solve comprehensive Sudoku grid, such as "Killer sudoku with Thermo Constraints" or "Anti-Knight Diagnoal Sudoku". A very good example can be found Here.

Other logic Puzzles

1. Solvers for Logic Puzzles using CS-SAT or MILP. More INTERESTING and brain-burning logic puzzles. Including path-finding, digit-filling and flag-placing puzzles. The puzzles that have been solved:

Table of Sudoku and its variants, with dataset. 👇

ID	Sudoku & variants	In Chinese	Done & Tested	Note	Dataset size	# of dataset	With Sol?
1	Standard Sudoku	标准数独	✅	Rules	9x9	-	-
2	Killer Sudoku	杀手数独	✅	Rules	9x9	155	✅
3	Jigsaw Sudoku	锯齿数独	✅	Rules	9x9	128	✅
4	Consecutive Sudoku	连续数独	✅	Rules	9x9	-	-
5	Sandwich Sudoku	三明治数独	✅	Rules	9x9	-	-
6	Thermometer Sudoku	温度计数独	✅	Rules	9x9	-	-
7	Petite-Killer Sudoku	小杀手数独	✅	Rules	9x9	-	-
8	Anti-Knight Sudoku	无马数独	✅	Rules	9x9	-	-
9	Anti-King Sudoku	无缘数独	✅	Rules	9x9	-	-
10	Greater-Than Sudoku	不等式数独	✅	Rules	9x9	-	-
11	Diagonal Sudoku	对角线数独	✅	Rules	9x9	-	-
12	Vudoku	V宫数独	✅	Rules	9x9	-	-
13	Arrow Sudoku	箭头数独	✅	Rules	9x9	-	-
14	XV Sudoku	XV数独	✅	Rules	9x9	-	-
15	Window Sudoku	窗口数独	✅	Rules	9x9	-	-
16	Kropki Sudoku	黑白点数独	✅	Rules	9x9	-	-
17	Even-Odd Sudoku	奇偶数独	✅	Rules	9x9	129	✅
18	Samurai Sudoku	武士数独	🐌	-	21x21	272	✅
19	Shogun Sudoku	将军数独	🐌	-	21x45	90	✅
20	Sumo Sudoku	Sumo数独	🐌	-	33x33	110	✅
21	Sohei Sudoku	Sohei数独	🐌	-	21x21	120	✅
22	Clueless Sudoku2	无提示数独2	🐌	-	27x27	40	✅
23	Butterfly Sudoku	蝴蝶数独	🐌	-	12x12	77	✅
24	Windmill Sudoku	风车数独	🐌	-	21x21	150	✅
25	Gattai-8 Sudoku	Gattai-8数独	🐌	-	21x33	120	✅
26	Clueless Sudoku1	无提示数独1	🐌	-	27x27	29	✅
27	16 x 16 Sudoku	16 x 16 Sudoku	🐌	-	16x16	124	✅

Table of Other Puzzles 👇.

ID	Name of Other Puzzles	Chinese Translation	Solved?	Note	Dataset
1	Alphadoku	25 x 25 16 x16 Sudoku	✅	-	dataset
2	Akari (aka: light UP!)	照明	✅	Rules	💪 Working
3	Cryptarithmetic Puzzles	破译密码	✅	-	-
4	Norinori	海苔	✅	Rules	💪 Working
5	Number Link (aka: Arukone)	数链	🐌	Rules	💪 Working
6	Minesweeper	静态扫雷	✅	Rules	dataset
7	Simple Loop (aka: Loopy~)	简单回路	✅	🚀 Gurobi required	-
8	Siltherlink	环	✅	🚀 Gurobi required, rules	dataset
9	Mosaic	马赛克	✅	Rules	dataset
10	Tent	帐篷	✅	Rules	💪 Working
11	Nonogram	数织	✅	No use of ortools, rules	💪 Working
12	Aquaium	水箱	✅	-	-
13	Kakurasu	方阵和	✅	Rules	💪 Working
14	Starbattle	星战	✅	-	💪 Working
15	LITS	LITS	❌	-	-
16	Pentomino	五联骨牌	✅	Rules	💪 Working
17	Suguru	🤔️	✅	Rules	💪 Working
18	Shikaku	直角	✅	Rules	dataset
19	Kakuro	交叉和	✅	Rules	dataset
20	Binario	二进制	✅	Rules	💪 Working
21	Five Cells (aka: Faibuseruzu)	五空格	✅	Rules	-
22	Fobidoshi (aka: Forbidden Four)	禁止四连	✅	Rules	-
23	Hitori	请勿打扰	✅	🚀 Gurobi required, rules	dataset
24	Monotone	单调性	✅	🚀 Gurobi required	-
25	Creek	小溪	✅	🚀 Gurobi required, rules	dataset
26	Patchwork (aka: Tatami)	榻榻米	✅	Rules	dataset
27	Kalkulu	解谜游戏	✅	Rules	-
28	Heyawake	Heyawake	✅	Rules	dataset
29	Gappy	盖比!	✅	Rules	dataset
30	GrandTour	旅途	✅	🚀 Gurobi required, Rules	dataset
31	Honeycomb 1 & 2	蜂巢	✅	🚀 Gurobi required, Rules	-
32	Maze-A-pix	迷宫绘画	✅	Rules	dataset
33	Dominos	多米诺骨牌	✅	Rules	dataset
34	Thermometer	温度计	✅	Rules	dataset
35	Pills	药丸	✅	Rules	dataset
36	Magnetic	吸铁石	✅	Rules	dataset

---

Dataset of some puzzles

• Many puzzle sources found online are in PDF format, which makes it difficult to use them directly for automated solving. For that reason, this repository also offers easy-to-use web crawlers that extract puzzle data in a structured format, rather than as images or PDF data. See Utils. Currently, we support structured data and corresponding final solutions for over 3,000 puzzles across 30+ different puzzle types. A detailed list of the available datasets is provided below. Please note that Sudoku datasets are already covered in a previous section and are omitted here.

• Additionally, for puzzles where bulk datasets are not yet available, at least one test case is provided to validate the correctness of the solving algorithm. Contributions of more datasets are welcome and encouraged.

ID	Puzzle name	Size of puzzle	# of puzzle	With Sol?
1	SlitherLink	10x18 14x24 20x36 20x30 16x19 30x25 60x60 Others	220 91 58 33 28 9 1 44	✅
2	Mosaic	25x25 20x20 15x15 Others	38 50 40 26	✅
3	Gappy	12x12 10x10 11x11	60 87 39	✅
4	Hitori	17x17 15x15 10x10	153 96 172	✅
5	GrandTour	11x11	126	✅
6	Akari	14x24 23 x 33 17 x 17 100x100 Others	72 17 18 1 21	✅
7	Heyawake	14x24 Others	272 125	✅
8	Patchwork	12x12 10x10	142 69	✅
9	Kakuro	12x20 Others	62 230	✅
10	Thermometer	10x10	83	✅
11	Dominos	7x8 10x11 Others	92 40 32	✅
12	Pills	10x10	163	✅
13	Minesweeper	17x17 Others	43 45	✅

---

Some OR materials

This section contains several materials when learning(and coding) Operations Research. Mostly IP and CP, with some classical Combinatorial Optimization Problems. More appendix, like mathematical models, can be found in Notes (Written in Mandarin) on my personal website.

1. Ortools for Linear Programming : Tutorials.
2. Ortools for Mixed Integer Programming: Tutorials.
3. Ortools for Constraint Programming: Tutorials.
4. Ortools for Knapsack Problem: Tutorials.
5. Ortools for VRP: Variants and ortools codes( of official website for self-learning).
6. Ortools & Gurobi for TSP: Two main methods for TSP.
7. Column Generation Method: Large-Scale Linear Programming and Cutting Stock Problems: Team Meeting report.
8. Branch & Price for Parallel Machine Scheduling: 🐌...
9. Some basic / classic Operations Research Modeling :

---

Reference

• ORtools Official
• Hakank's ORtools tutorials
• Puzzle data: Raetsel's Janko, Puzzle