SOKUKU
Sokuku will show the steps in the solution of a Sudoku puzzle, or generate puzzles.
This program has no warranty. Use it at your own risk.
Licensing conditions are found in the README file here. Remember, it is still work in progress. Please report any bugs to me.
To run it from this site, you will need to enable Java applets in your browser. It is your machine that will do the heavy optimisation computations when creating new puzzles for you to try, so a slow machine could be very slow.
The program is interactive and allows you to make the decisions which rules to apply, or you can ask it to complete the solution itself and report what it has done and why it did it. You can also ask on individual moves why it makes that move and it will highlight the relevant cells.
The executable for the applet
contains the source within its archive, which you are welcome to take
and modify for your own purposes. Licensing details are inside the
archive.
After I retired from a software development job, I thought I would learn some of the new languages and techniques that were completely different from anything I had been doing up to that point. So I tried Java, a language I knew almost nothing about, but which I realised was an easy choice if the resulting programs were to run on as wide a range of common machines as possible. I also wanted to write something interactive, again not what I was used to. At about that time, Sudoku was all the rage, and it seemed just the type of project I was looking for. Write a solver in Java, and allow it to be invoked from a web-site. This is the result so far. It is still work in progress.
The rules which it can use to help it resolve a puzzle are described briefly below. These descriptions are not sufficient in themselves to write algorithms directly. They are intended to give a clear idea of what they are, so you can follow what the program does.
First some terminology. Call each location where a sign is to be placed, a cell. Call any set of N cells which are to contain N different signs, a tuple. It is largely irrelevant whether these are rows, columns or boxes. Call the cells that are common to two tuples, their intersection. Call an intersection that contains more than one cell, a segment. During the solving process, call those signs that have not yet been eliminated for a given cell, the candidates for that cell. Some cells have been assigned signs at the start of the puzzle; others will be identified, and they will then become fixed.
Unique in tuple: If a cell C in tuple T has fixed value V, then we can eliminate all candidates of value V in the other cells in T.
Singles: If a cell C has only a single candidate V left, then it can be fixed at V.
Places: If a tuple T has only one cell C containing candidate of value V, then V can be fixed in C.
Groups: If the union U of candidate values in a set S of size N of cells in tuple T is also of size N, then the candidates of values in U can be eliminated from (T-S).
Segments: If tuples (T1, T2) intersect in segment S, and in T1 candidates of value V occur only in S, then V can be eliminated from (T2-S).
Pairs: If cells C1, C2 in tuple T contain only candidates of values V1, V2, then it is clear that V1 and V2 must lie in C1 and C2, but must be different. In this way, all connected cells containing only candidates V1 and V2 can be divided into two sets {S1}, {S2} such that all cells in S1 contain one of {V1, V2}, and those in S2 contain the other. All candidates V1, V2 which lie at the intersection of T1, T2, where T1 contains a cell from S1, and T2 a cell from S2, can be eliminated.
Nets: Define a net of size N as a pair of sets (S1,S2) of tuples such that: (a) both S1 and S2 contain N tuples, and (b) no two tuples in S1 intersect (e.g. rows), and (c) no two tuples in S2 intersect (e.g. columns), and (d) each tuple in S1 intersects all tuples in S2 (and hence vice versa), and (e) candidate V occurs in each tuple of set S1 only at the intersections of S1 with a tuple in S2 (but not necessarily at every such intersection), then V is restricted to those intersections and can be eliminated from cells in tuples in S2 not at the intersections.
Chains: Define a closed chain S of N tuples {T1, T2, ..., TN} such that: (a) N is even, and (b) each Tn intersects its successor T(n+1), and TN intersects T1, and (c) candidates of value V occur in at least one cell at all intersections, and (d) in even numbered links, {T2, T4, ...} V occurs nowhere else but at the intersections, then V is restricted to the intersections and can be eliminated from cells in the odd numbered links that are not at the intersections.
Twins: Define a closed cycle S of N tuples {T1, T2, ..., TM, ..., TN} such that: (a) N is odd, and M<N is even, and (b) each Tn intersects its successor T(n+1), and TN intersects T1, and (c) candidates of value V occur only in the intersections in {T1, T2, ...,TM}, and (d) V does not occur in any of {T(M+2), T(M+4),..., T(N-1)} except at the intersections, then V can be eliminated from both the intersections between {TN, T1} and between {TM, T(M+1)}. [Note: This rule eliminates simultaneously more than one candidate, which is why I call it Twins.]
Triangles: Define a closed cycle S of N tuples {T1, T2, ..., TN} such that: (a) N is odd, and (b) each Tn intersects its successor T(n+1), and TN intersects T1, and (c) tuples T2, ... T(N-1) all contain the candidate value V only at the intersections with their neighbours, and (d) cell C is in the intersection of T1 and TN, then V can be eliminated from C. C is at the apex of a sort of triangle in which the two vertices at the ends of the base must account for V, and so C cannot have V.
Loops: Consider candidate of value V1 in cell C1 in the intersection between tuples T1 and T2. Then if in T2, there is a cell C2 containing two candidates, V1 and V2, then if C1 has V1, then C2 has V2. But C2 is also at the intersection of T2 and another tuple, say T3. This might force another cell C3 in T3 to have the value V3, say. In this way a chain of inferences can be built up. If such a chain leads back to a value of V1 at cell Cn (not C1) in T1, then clearly C1 cannot contain V1 and V1 can be eliminated from C1. [Note: It is a moot point whether this constitutes a look-ahead, since all information is visible, and no changes are made temporarily to be backed out later. However, some think it does. More work can be done on this to generalise the inferences at each step.]
Then finally, if all else has failed, it looks for a candidate among the cells with fewest candidates to resolve the puzzle. But if there is no solution, or there are more than one, then it will not proceed further.
I have not included any rules that assume there is a unique
solution, because to my mind, that is being provided with information
that you cannot know in advance. It would perhaps be interesting to
see what types of problems could be resolved if that is known in some
way. But why should the solver believe the setter? Anyone can make a
mistake.
I know that it is restricted to a fixed size of window, merely because I haven't found time to change it.
I hope you enjoy it, but I would welcome feedback at andy (at) pepsplace (dot) org (dot) uk
Updated: 2005-12-01
Last updated: 2011-04-12 (trivial edits when moving from one site to another)