/PuzzleSolver

50+ solvers for logical puzzles, with 5000+ dataset of them, including Sudoku-like puzzles, Slitherlink, Pentomino, Hitori, Shikaku, Heyawake, Mosaic, Tent, Creek, Atari, Suguru, Five Cells etc. Mainly solved via Solvers like ortools and Gurobi.

Primary LanguageJupyter Notebook

Puzzles Solvers & OR tutorials

EN CN

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 โœ…

Table of Other Puzzles ๐Ÿ‘‡.

ID Name of Other Puzzles Chinese Translation Solved? Note Dataset
1 Alphadoku 25 by 25 ๅญ—ๆฏ็‹ฌ โœ… - -
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 -
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 ๐Ÿ’ช Working
26 Patchwork
(aka: Tatami)
ๆฆปๆฆป็ฑณ โœ… Rules dataset
27 Kalkulu ่งฃ่ฐœๆธธๆˆ โœ… Rules -
28 Heyawake Heyawake โœ… Rules ๐Ÿ’ช Working
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

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 2,000 puzzles across 20+ 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
4
โœ…
8 Patchwork 12x12 142 โœ…
9 Kakuro 12x20
Others
62
230
โœ…
10 Thermometer 10x10 83 โœ…
11 Dominos 7x8
10x11
Others
92
40
32
โœ…

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