![[Dir]](../../../../dir-icon.png){kind=icon}
![[File]](../../../../file-icon.png){kind=icon}
Sudoku is reducible to Latin squares, therefore it is np-complete; Lorch2012Magic. Sudoku-solver was the most interesting homework problem in our Fall 2007 309-250 (Comp-250): Data Structures and Algorithms at McGill—Homework 5. Matthew Blanchette asked me to remove this source code because he was re-assigning it. I know that some of the students have Googled it from the future, some have asked Stack Overflow questions, so I am explaining my approach—but first…
Wikipedia's article on the most most popular Sudoku variant explains:
…the objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 [boxes] that compose the grid contains all of the digits from 1 to 9 …for a well-posed puzzle, has a single solution.
Finding a solution to a valid Sudoku and checking if it is a valid Sudoku are different aims. Sudoku.java (fall 2007) reads "You may add that check if you want to, but it is not necessary," so we will assume that there is one solution. I think checking would be slightly harder problem in which we would not be able to use short-circuiting.
Figure 1.
| 2 | 1 | ||
| 4 |
World's Hardest 4x4 Micro Sudoku, Fluttering3600, 2020, Ant Twin MicroSudoku, By Hippogonal#4902. Supposedly.
Different languages are used in different communities. The homework uses an np-hard version. The number of symbols in the alphabet (or digit, number, element) is n. This is the same n that is in the code: n×n of the board, which is composed of cells (or squares). As eg Hoffman2020Super, n is the square of the order; this is the size in the code. It is the one box dimension (or block, region, nonet) and the first number in the data files, order×order=n. Row, column, or box are collectively known as groups; there are 3n uniqueness contraints formed of overlapping groups of n cells. So for a standard Sudoku, the order is 3, 3x3 boxes, n=9, 9x9 grid, 9 symbol alphabet, and 27 group constraints. Figure 1 shows an order 2, 2x2 boxes, 4x4 grid, 4 symbol alphabet, 12 group constraints.
In general, classic Sudoku doesn't require square boxes; eg Dodeka Sudoku is 12x12-cell, 12-symbol alphabet, boxes are 4x3; or 8x8-cell, 8-symbol alphabet, 4x2 boxes. Killer Sudoku adds a second level of constraints called cages that form a connected disjoint set, and must add to the given number without repetition. Killer-X adds a constraint on diagonals. Jigsaw Sudoku relaxes the square-box, (not box, block, but now region, nonet). This doesn't matter for our purposes: here the boxes are square and the order is all one needs to define the board.
The test files in fall 2007 are: order 3, 9×9, popular Sudoku; order order 4, 16×16, Super-Doku Number Place Challenger; order 5, 25×25, Sudoku the Giant. The programme takes any number from [1–100]; though a 10 000x10 000-cell board is probably overkill for an np-hard puzzle. More code-coverage would be useful. Order 1 is just a single cell, there can be only 1 board, so that's easy to test with "1 *". Order 2, 4×4, is For Kids'. It gets harder to find examples as the order goes up: Philb "sdkvo": Sudoku & X-Sudoku Geants for monthly up to Sudoku-zilla, "expert" order 10, and order 12 (but this was very easy for my solver; order 10 was much harder).
I grabbed this off somewhere because I'd lost my original assignment.
COMP 250 - Homework #5
Due on December 3rd 2014, 23:59
Web search-engine or Sudoku (100 points)
For this assignment, you have the choice between two possible projects. You should do only one of the two.
Project #1: Web search-engine
For this final programming homework, we are going to write a mini-Google program that will… [Less interesting.]
Project #2: Sudoku solver
A Sudoku is a type of puzzle that has become extremely popular these days. You will find the rules of the Sudoku puzzle at: http://www.sudoku.com/
Your goal is to write a program that will attempt to solve Sudoku puzzles. We are giving you a simple java class to represent a Sudoku puzzle, and to read or write a Sudoku from and to a file. You are asked to write the solve() method, which modifies the Sudoku object on which it is called and should fill all the empty squares in the Sudoku to produce a valid solution.
The code is at: http://www.cs.mcgill.ca/~blanchem/250/hw5/sudoku.html [Dead link.]
You will also find there a set of sudoku puzzles, sorted in increasing order of difficulty. To get full credits for this project, your program should be able to solve any 3x3 puzzles in less than 10 seconds of running time.
There are many ways your program could attempt to solve the Sudoku. It is totally up to you to decide which approach to use. I would suggest that you try to solve a few Sudokus manually before trying to write a program. One classical way to approach this kind of problem is to use a backtracking search as described in class for the 8-queens problem. What will determine how quickly your program will find a solution is the criteria you use to decide in what order the backtracking search should be performed. This project is totally open-ended. Use your imagination!
Evaluation
The program succeeds at solving all 3x3 cases correctly in less than 1 minute. 50% Originality of the solution. 30% Style and documentation 20% Sudoku tournament
To identify a winner for the Sudoku tournament, each program will be given one minute to solve each Sudoku puzzle on our computer. The ranking of the programs will be established based on the number of Sudokus it succeeds at solving, from a set of 10 problems ranging from very easy to very difficult. The actual problems that will be used for the tournament will not be released before the tournament, but a set of equally difficult problems will be given for training. To keep the competitive spirit going, teams will have the possibility of using MyCourses to report which problems they are able to solve.
1st place: 20 bonus points 2nd place: 10 bonus points 3rd place: 5 points
The 10 s is very generous.
I'd leaned Java in comp-202; in 2007 comp-250 was still teaching an older version of Java. Java came out with J2SE 5.0 in 2004 which introduced a lot of new features, including more type-safety with generics. I don't think 5 was even installed on all the computers on campus. Surely that's been updated now? Here are more things that I'd wished I'd known for this project.
cardinality. This is the Hamming weight, C++20's popcount. Would have probably been a bit twiddling hack before SSE4.2 in 2008. On today's processors, I think one can reliably say most functions take 𝒪(1) in hardware.
The homework mentions the eight queens problem. This is a good hint to use Sudoku with backtracking search and constraint satisfaction. Although not the fastest approach, it is simple to get a working solver and—assuming there is a solution—it will find it. Simple enough to do as homework. I've learned that backtracking is not well received in the Sudoku community because it's a form of brute-force guessing. Namely, people play with the added rule of deducing a move before playing—the equivalent of playing in pen. The backtracking algorithms are a depth-first-search on the state space. One must store enough information to get back to the subsequent and initial states. One can discard the failed board positions and re-use the, now, stack.
The homework also hints that the order is crucially important. Wikipeda now has a section on backtracking specifically for Sudoku. The example (2026) has candidates selected from left to right. The chances of finding the right symbol in the cell this step are denominated by the number of potential symbols in the cell. Therefore this can be improved by selecting one of minumum number of guesses remaning first. This also protects against an adversary constructing a puzzle to work against in-order backtracking.
It's still exponential in the number of undecided squares. Any pruning early on saves potentially lots of work later; kind of like branch-and-bound from Comp-424. The homework encourages one to do it by hand; when done, it becomes apparent that most of the guesses are completely spurious. By doing a little work eliminating these possibilities before we branch, one can save a lot of work later.
I taught myself a little bit about how to solve Sudoku puzzles so I could teach the computer to solve them in a similar manner; not necessary the optional solution. I assume the complex methods are less useful to detect. So singles in row-column-box, naked pairs, triples, happens way more than x-wing, finned swordfish, death blossom. I set up a short-circuit where immediately upon successfully modifying the board with a more complex method, it reverts to the most simple method and tries again. Only when it runs though and doesn't change anything will the branching occur. I only had single and multiple in the end, so this was probably overkill.
Turns out, of the examples, only veryHard4x4.txt even gets to the branch step; the other ones just solve themselves on one iteration of the bound step. On the flip side, in the most diabolical puzzles, more complicated solvers actually take more time than guessing (backtracking). So for example, Arto Inkala, 2012 Everest is/was the "Hardest Sudoku In The World" becomes quite easy with backtracking.
I handed in 2 .java files and didn't know until after the mark change period that the marking script didn't know how to run it and the TA gave me 0% on the whole project. Don't do this: stick with the structure and the files you have been given.
| .. | Algorithms and Data-Structures. |
| 16×16 hard not prober.txt (1 KB) | |
| 2012-everest.txt (0 KB) | |
| 4x4-kid.txt (0 KB) | |
| 6x6.txt (2 KB) | |
| 705-unsolvable.txt (0 KB) | |
| AI Escargot.txt (0 KB) | |
| cs.link (0 KB) | I tried running it as a CGI, but www.cs.mcgill.ca does'n't like that. |
| g100_209d.txt (49 KB) | |
| g144.txt (57 KB) | |
| g49_210d.txt (12 KB) | |
| g64_211d.txt (20 KB) | |
| gs22-100.txt (101 KB) | |
| Hippogonal#4902.txt (0 KB) | |
| Makefile (0 KB) | |
| odin.link (0 KB) | No, this does'n't work eiter. |
| one.txt (0 KB) | |
| Rico Alan 2008.txt (1 KB) | |
| sudoku-puzzles_net#t14d3p1.txt (0 KB) | |
| Tim Stellmach 2017.txt (1 KB) |
π