I suppose one is here about sudoku-solver homework 5 in 309-250 (Comp-250): Data Structures and Algorithms. Matthew Blanchette asked me to remove this code because he was re-assigning it; it has since become a staple of undergraduate-cs at McGill. Students have landed on this page after Googling it from the future and asked Stack Overflow questions. It's interesting for good reason: sudoku n×n is reducible to Latin squares, therefore the decision problem is np-complete; Lorch2012Magic. The oeis number of (completed) sudokus stops at order 3. A super-legit problem.
Project in Fall 2014
I lost my original problem statement in the constant updating of webct (whatever it's called now), but I yoinked this, probably off some student who came to CSUS:hd.
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… [Web search-engine is 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 to solve a 9×9 is very generous. However, as the size increases, it becomes increasingly difficult—assuming one is planning to solve n×n sudokus. I have the original code timings that I wrote in 2007, Figure compare-original. I have lost the example files, but of the supplied files, veryHard4x4.txt (16×16 number place challenger) was by far the hardest. Only one or two required backtracking at all. Notice that veryHard5x5.txt (25×25 sudoku the giant) is actually an easy puzzle.
Figure compare-original. This was run on willy.cs.mcgill.ca in 2007, also lab6-2.cs.mcgill.ca was way faster, but neither of them is accessable for me anymore. veryHard4x4.txt which took 134.3 ms on willy took 95 ms on lab6-2. Other than veryHard4x4.txt, the solutions was found mostly without backtracking at all; I suspect mostly set-up and naked-singles. The order-3 is 81-cells and 27-constraints vs the order-5 is 625-cells and 75-constraints; increased time in veryHard5x5.txt is probably a matter of fillrate.
There are many different types of sudoku
I had never played sudoku, and the advice to play a few rounds is sound: one gets a sense of what information is important to store. I suggest reading Wikipedia's new glossary of sudoku beforehand. Wikipedia's article on the most most popular classic 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…
That is, there are 3n row, column, and box overlapping permutation constraints. The intended version of this assignment uses a np-hard varient n×n proper sudoku (where n=9 in classic) with n=[1..10 000] (essentially variable) defined by a single-parameter ("size" in the code); this is box dimension and the square-root of n ("N" in the code). In the 2026 literature (egHoffman2020Super) size is known as order. order×order is n, the cardinality of digit, and the dimension of the grid. Here, digits are elements of an alphabet: they have no arithmetic meaning and are symmetric with any relabelling. This includes square classic sudoku, subdoku, and superdoku, but: not jigsaw, which relaxes the square-not-box, block, but now region, nonet; not killer, adds a second level of constraints called cages that form a connected disjoint set; not killer-x, which further adds a constraint on diagonals; also not classic sudoku with non-square boxes, such as: not 3×2 boxes of 6×6-cell; not 4×2 boxes of 8×8-cell; not dodeka 4x3 boxes of 12x12-cell; etc.
…for a well-posed puzzle, has a single solution.
Sudoku.java (fall 2007) reads "You may add that check if you want to, but it is not necessary", and a trap. Finding a solution to a valid sudoku is a sub-problem (namely, short-circuit) of checking if it is valid.
Following the homework's hints
The homework mentions the eight queens problem. This is a good hint to use sudoku with backtracking search and constraint satisfaction. Backtracking is simple to get a working solver but—assuming there is a solution—eventually it will find it. The backtracking algorithms are a depth-first-recursive-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. This can be, for example, an entry in a linked-list, recopying the entire board, or even treating is as an exact-cover problem and applying egdancing-links.
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. When we follow simple backtracking, it becomes apparent that most of the guesses are completely spurious. Not ever considering the state (for example, having a pool of digits from which one chooses) or discarding state-trees early leads to a more performant solution—like branch-and-bound from Comp-424.
The homework also hints that the order is important. Wikipeda now has a section on backtracking specifically for sudoku. The example (2026) has candidates selected from left to right, but we can do better. The probability of finding the right symbol in the cell are denominated by the number of potential symbols in the cell.
I handed in 2 .java files and the marking script didn't know how to run it; this means I got 0% on the whole project and didn't know it until later. Don't do this: stick with the structure and the files you have been given.
Picking obvious symmetry-breaking like the top-left or lowest-first leaves one open to puzzles that are designed to work against you, such as Rico Alan's Star Burst Polar. On the other hand, it can also be extremely useful when debugging, comparing one's solver to another's—on the internet or in class—because they probably choose the same.
Results
I had just leaned Java in comp-202, and it has become much more expressive since then. Particularly,
In 2004 Java 1.5 (J2SE 5.0) was a huge update. Before the use of generics, all containers were of type Object and type-safety was only checked at run-time. As well, none of the introspection, for-each, and functional programming were possible. I took comp-250 in 2007, but only about half the computers at McGill were even upgraded to 1.5. I uncommented all that.
I used a boolean array for sets of digits, sets of cells in the grid, and sets of cells in houses. While the size is machine-dependent, it's probably sparse, and loops are slow. Instead, extending BitSet is super-useful and concise. It allows operations to be carried out in parallel over 64-bits. In addition, Intel made Nehalem SSE4.2 in 2008; since, one can be pretty certain hardware support for bitfields exists automatically. Replacing bit twiddling hacks with egC++20'spopcount and now a default in Java is -XX:+UsePopCountInstruction.
Didn't have much effect on run-time, but about half my code manually implemented an esoteric sort for integer references to pairs. I replaced that with Java's implementation of a heap, PriorityQueue.
In Figure compare, the boolean array is not-changed-much code from Figure compare-original—which has the same y-axis as compare. The two order 3, backtracking 1, (9x9 Rico Alan 2008.txt, 9x9 Tim Stellmach 2017.txt) are probably comparable to it. The rest of the difficulty is inherent in the more difficult problems themselves.
Figure compare and compare-log. This was run on my 2011greymac in 2026. The 25x25 mega, g49_210d, and g144 are clipped significantly at the top of compare, see the compare-log. The "expert" order 8 g64_211d and order 10 gs22-100 didn't complete in the 2 minites it took for my display to go to sleep.
The sudokus and individual automated runs are below.
sudoku-puzzles.net. Solution. A more difficult sudoku. My solver picks the two-candidate top-left lowest-first cell and it's right 97/98 times. That's lucky?
Sudokuwiki. Solution. Unsolvable #705. That is, by Andrew Stuart's very complete deterministic solver (as are others on this list). On the other hand, backtracking is guaranteed to get a solution if there is one.
Rico Alan from Wikipedia. Solution. Star Burst from Sudoku solving algorithms' "A Sudoku designed to work against the brute force algorithm", that is, left-top first backtracking. However, it requires no backtracking at all if one does hidden and naked-singles.
Philb "sdkvo": Sudoku & X-Sudoku Geants. (Spam output suppressed.) "G49_210 / DIFFICULT" order 7. This is the hardest sudoku that I had the patience to complete, clocking in at boolean array and sort 1.75 minute and bitset and heap 0.31 minute. This difference is only going to increase with increasing order.
![[Dir]](../../../../dir-icon.png){kind=icon}
![[File]](../../../../file-icon.png){kind=icon}
