Champagne,

Since I am a bit behind finishing my basic description of solving with permutations, I will put a preliminary copy here. The only difference is this is brief and not carefully checked. Later I will replace this with a referecne to the finishedwork.

The only thing you might want is about selecting the next set, which is most inportant in keeping the number of permutations down. Aslo see about starting different kinds of logic.

PART I, Second Order Solver - PermutationsBasic SetsBasic sets are the 324 given constraints in Sudoku expressed as sets. There are 4 groups of 81 sets each for rows, columns, cells, and boxes. Each conventional row has 9 row sets, one for each digit.

PermutationsA permutation is one possible (legal) arrangement of candidates for any form of logic including sets, chains, fish, or an entire puzzle. An unsolved puzzle can have an extreme number of permutations. A valid solved puzzle has only one permutation, which is the answer. Each solution to a non-unique puzzle is a different permutation.

- Code: Select all
`A set with 3 candidates, A, B, C, has 3 legal permutations.`

set{A, B, C} = 100, 010, 001

The permutations of a basic set are called candidate vectors. The candidate vectors for any basic set are orthogonal, i.e., they cannot be combined.

Permutation DatabaseA permutation database D is simple, it a list of permutations for some logic L where each column represents a candidate. It is useful to have a mask to know which candidates are already in D. The database for the single set above is:

- Code: Select all
`cand. ABC-- `

mask 11100

p1 100..

p2 010..

p3 001..

Adding PermutationsFinding all legal permutations for any logic is done by adding the permutations of all subunits that make up the logic. Subunits are usually basic sets but can be chains, ALS, etc. The single operation of permutation addition does all the logic work of the solver:

Adding two permutations P1 and P2 requires that all shared candidates must have the same value. The resulting permutation then contains all candidates from P1 and P2.

- Code: Select all
`X-Wing Example`

(1) = true candidate, (0) = false candidate, (.) = empty location

Row{A,B} = (1,0),(0,1)

Row{C,D} = (1,0),(0,1)

Col{A,C,X} = (1,0,0),(0,1,0),(0,0,1)

Col{B,D} = (1,0),(0,1)

1. Add first row to the database

ABCDE (database)

10...

01...

2. Adding remaining sets to the database

ABCDE +(..CD.) +(A.C.X) +(.B.D.)

10... --> 1010. -->

1001. --> 10010 --> 10010

01... --> 0110. --> 01100 --> 01100

0101. -->

^-- Elimination

Simple SearchA path (or search) is made by adding one set S at a time to make a group of sets G. After each addition, the permutation database D contains all of, and only, the allowed permutations for logic G.

- Code: Select all
`choose_first_set(); `

loop{

choose_next_set();

add_next_set();

}

The permutation database D can grow exponentially or shrink depending on which sets are added. Each line in the database is equivalent to a branch in a search tree.

A set with M candidates that does not not overlap any candidates in the database will generate N new permutations for each permutation in the database.

A set that overlaps most or all candidates in the database can reduce the size of the database or even eliminate all permutations in the database.

Choosing the Next SetThe most important part about choosing the next set is to keep the number of permutations low, and there are several ways to do this. If D is the database, M is a bit mask of candidates in D, and X is a bit mask of candidates for the set under test.

- Code: Select all
`Check all remaining sets to find a minimum or a maximum values of (choose one):`

1. M (and) X, ... the maximum bits that overlap

2. (not)M (and) X, ... the minimum bits that do not overlap,

3. D(perm add)A, ... the minimum number permutations generated by adding A to D.

4. (other ways), ... anything the helps minimize the no. of permutations in D.

Method.3 works well but is time consuming. The add_set() procedure used for addingc can be changed to count new permutations would be generated, but not generate them or change the database.

Starting a Set to solve a puzzleThe basic solver is like a logic machine, what comes out depends on what goes in. A basic set with n candidates contains one true candidate and n-1 false candidates. Thus, starting a whole set guarantees that a solution is in the database. Below, candidate A is true in the solution.

- Code: Select all
`{A,B,C} ---->`

set permutations possible results

--------------------------------------------------------------

ABC ABCDEFGHIJKL...

100 --> 100XXXXXXXXX... ---> 1001100011010... (the solution)

010 --> 010XXXXXXXXX... ---> <n=0> (no perms)

001 --> 001XXXXXXXXX... ---> <n=0>

Starting a Set to find a contradictionEliminations occur long before the puzzle is solved. Any candidate whose column becomes all zeros can be eliminated becasue that candidate cannot be 1 in the logic.

- Code: Select all
`{A,B,C} ---->`

set permutations possible results

--------------------------------------------------------------

ABC ABCDEFGHIJKL...

100 --> 100XXXXXXXXX... ---> 1001XXX0XX0X...

010 --> 010XXXXXXXXX... ---> 0100XXX0XX0X...

001 --> 001XXXXXXXXX... ---> 0010XXX0XX1X...

^------- elimination

Starting a single candidateThe search process can be started with any logic including a single candidate vector or a single candidate. The results depend on whether the initial candidates are true of false. Again A is true and B is false.

- Code: Select all
`A is true:`

set permutations possible results

--------------------------------------------------------------

ABC ABCDEFGHIJKL...

100 --> 100XXXXXXXXX... ---> 1001100011010... (the solution)

or

1 --> 1XXXXXXXXXXX... ---> 1001100011010... (the solution)

B is false:

set permutations possible results

--------------------------------------------------------------

ABC ABCDEFGHIJKL...

010 --> 010XXXXXXXXX... ---> <n=0>

or

1 --> X1XXXXXXXXXX... ---> <n=0>

Starting a false candidate eventually leads to the addition of a set, Sn, that results in zero permutations. In this case, the database contradicts set Sn, i.e., for example the columns for candidates in Sn may = {000}.

.

.Edit: fixed X-Wing example.

.Edit: removed the term node in favor of the term candidate.