NYCJUG/2012-10-10

generating Sudoku, enumerating Sudoku, language learning, board game to learn HTML, web platform

Location:: BEST

Agenda

             Meeting Agenda for NYCJUG 20121010
             ----------------------------------

1. Show-and-tell + Beginner's regatta: Sudoku generation by John - see "Sudoku
Generation from John Randall.pdf"; Sudoku generation by Devon - see "Counting
Sudoku.pdf", "Sudoku Generation Code.pdf", "Example of Generating a Samurai
Sudoku.pdf"; also see "EnumeratingPossibleSudokuGrids.pdf" and "Encrypt Images
Using Mathematics of Sudoku.pdf" [also "Sudoku-Associated Two-Dimensional
Bijection.pdf"].


2. Advanced topics: see "Selections from HAP All Partitions Paper.pdf".


3. Learning, teaching and promoting J, et al.: See "Language Learning Makes
the Brain Grow.pdf", "APL on FPGA.pdf", "cHTeMeLe is a board game about
HTML.pdf", "Web Platform announcement.pdf".

Show-and-Tell + Beginner's Regatta

Constructing Sudoku - Method 1

We construct solved Sudoku grids row by row. Given a partial solution P, we find all possible extensions, the permutations of i.9 that differ from the rows of P in every position. We then check the 3x3 cells (including partial cells) for uniqueness.

The verb run finds solutions depth-first using a stack.

Our solutions have >:i.9 as the first row: all others can be obtained by multiplication of permutations.

NB. Table of all permutations

tap=: i.@! A. i.
PT=:|: P=:tap 9

NB. Test whether permutations differ in all positions.

dr=:*./ .~:
9!:7 '+++++++++|-'
0 : 0
Quick start:

   block &.> print &.> <"_1 display run 5
+-------------+-------------+-------------+-------------+-------------+
|+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+|
||123|456|789|||123|456|789|||123|456|789|||123|456|789|||123|456|789||
||456|789|123|||456|789|123|||456|789|123|||456|789|123|||456|789|123||
||789|123|456|||789|123|456|||789|123|456|||789|123|456|||789|123|456||
|+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+|
||214|365|897|||214|365|897|||214|365|897|||214|365|897|||214|365|897||
||365|897|214|||365|897|214|||365|897|214|||365|897|214|||365|897|214||
||897|214|365|||897|214|365|||897|214|365|||897|214|365|||897|214|365||
|+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+|
||531|642|978|||531|642|978|||531|642|978|||531|642|978|||531|642|978||
||642|978|531|||648|971|532|||672|938|541|||678|931|542|||942|578|631||
||978|531|642|||972|538|641|||948|571|632|||942|578|631|||678|931|542||
|+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+|+---+---+---+|
+-------------+-------------+-------------+-------------+-------------+

Given a partial solution, find all extensions: permutations that differ from the partial solution in every position.

xtend=:,"_ 1 P #~ *./@:(dr&PT"1)

Given the result of xtend, check the partial 3x3 cells for uniqueness.

For a single matrix this means: Let r be the number of rows. Let t be the number of rows in excess (base 1) of a multiple of 3 (could be t=.(3|r) { 3 1 2). We are just going to test the last t rows. If t=1, there is nothing to check. If t=2 or 3, we rearrange the matrix so that the items to be tested for uniqueness are in the rows. The matrix has shape t,9. We transpose it to shape 9,t and then reshape it to shape 3,3*t, and test the rows. The verb trim does this for a list of matrices, and filters out those that do not satisfy the uniqueness condition.

trim=:3 : 0
r=.1{$y
t=.3&|&.<: r
if. 1=t do. y return. end.
R=.((3,3*t) ($,) |:)@((-t)&{.)"_1 y
y #~ *./@:(-: ~."1)"_1 R
)

NB. Display list of anagram indices as Sudoku grid.
display=:A.&(>:i.9)

NB. Show matrix as 3x3 blocks
block=:(3 3,:3 3) <;._3 ]

NB. Print in minimal space
print=:1j0&":

run y generates the first y solutions, given as a list of anagram indices. Use display to get the grids. They can be further formatted using block and print.

run=:3 : 0
n=.0
r=.0 9 $ 0
stack=.,<,:i.9
while. (#stack) *. n<y do.
  top=.>{: stack
  NB. smoutput (#stack), A. top
  stack=.}: stack
  if. 9=# top do.
    NB. smoutput A. top
    r=.r,A. top
    n=.>:n
  else.
    stack=.stack,|. <"_1 trim xtend top
  end.
end.
r
)

Constructing Sudoku - Method 2

Counting Sudoku

How many possible 3^4 (regular Sudoku) are there?

     !9         NB. Possibilities per square
  362880
  +--+--+--+
  |!9|!9|!9|    NB. General possibilities within each square
  +--+--+--+
  |!9|!9|!9|
  +--+--+--+
  |!9|!9|!9|
  +--+--+--+

     (!9)^9    NB. Search space
  1.09111e50
     (!3^2)^3^2
  1.09111e50

The number of valid Sudokus is so much smaller than this that it doesn’t pay to generate random grids and test them for correctness. How do we know how many valid Sudokus there are? We could just look it up on Wikipedia and find this:

Mathematics of Sudoku

A completed Sudoku grid is a special type of Latin square with the additional property of no repeated values in any of the 9 blocks of contiguous 3×3 cells. The relationship between the two theories is now completely known, after it was proven that a first-order formula that does not mention blocks (also called boxes or regions) is valid for Sudoku if and only if it is valid for Latin Squares (this property is trivially true for the axioms and it can be extended to any formula).^[15]^

The number of classic 9×9 Sudoku solution grids is 6,670,903,752,021,072,936,960 (sequence A107739 in OEIS), or approximately 6.67×10^21^. This is roughly 1.2×10^−6^ times the number of 9×9 Latin squares.^[16]^ Various other grid sizes have also been enumerated—see the main article for details. The number of essentially different solutions, when symmetries such as rotation, reflection, permutation and relabelling are taken into account, was shown to be just 5,472,730,538^[17]^ (sequence A109741 in OEIS).

The maximum number of givens provided while still not rendering a unique solution is four short of a full grid (77); if two instances of two numbers each are missing from cells which occupy the corners of an orthogonal rectangle, and exactly two of these cells are within one region, there are two ways the numbers can be assigned. Since this applies to Latin squares in general, most variants of Sudoku have the same maximum…. Over 48,000 examples of Sudoku puzzles with 17 givens resulting in a unique solution are known.^[citation needed]^

But what fun is this? Also, how do we know it’s correct? We could take a look at a web page purporting to calculate this number, where we might find something like this assertion [from http://www.afjarvis.staff.shef.ac.uk/sudoku/bertram.html]

There are 6670903752021072936960 Sudoku grids Bertram Felgenhauer and Frazer Jarvis

This page contains details of the enumeration of Sudoku grids. See www.sudoku.com for more details. The algorithm is a brute force count: all programs were written by Bertram Felgenhauer, incorporating several ideas of mine which reduce considerably the size of the brute force search.

We have written a short article, which is now available.

In addition, this page contains a program due to Ed Russell which independently verified the original calculations. (Thanks to Ed for allowing us to make this available on this page.)

Bertram Felgenhauer's programs and data Programs to reduce the configuration list * sudoku.hs: a Haskell program which reduced the configuration list from 36288 to 306. [Now obsolete]

sudoku_equiv.cc: a C++ program which refines the earlier idea, with a more effective data structure to store the equivalences, thus reducing the number of equivalence classes from 36288 to 71.
sudoku_verify.py: a Python program to verify the reduction to the 71 classes.

Reduced list of configurations * jobs1.txt: the job list for the 306 configurations produced by the Haskell program (this was Bertram's original calculation, which first gave the result).

jobs2.txt: the job list for the 71 configurations produced by the C++ program.
tree.txt (2133KB), gzipped version (263KB): longer output from sudoku_equiv.cc, documenting how the 36288 configurations are related. The Python program takes this as its input, and verifies that the rules were applied correctly.

Program to count number of completions of a configuration to a fill grid * sudoku2.cc: given a configuration produced in the above list, this program counts (by means of an exhaustive search) the number of completions to a full Sudoku grid.

Independent Verification(?) in J

Here’s how I went about generating Sudokus, and counting them in J. One of my guides was the idea that however I accomplished this, I’d like to generalize it to other regular Sudoku such as 4^4, 5^4, and so on.

We start with the upper-left square – at index (0, 0) in the grid – and build out along rows and columns of the grid from there. Let’s choose the simplest value for the (0, 0) square, then generate the possibilities for the one next to it – the (0, 1) square.

   rc00=. 3 3 $ 0 A. I9
   allrc01=. genAllRC rc00

where

   genAllRC=: (<3 3) $&.> 9 allunq [: , [: ;&.> [: { 3 allunq&.> [: ([: , {)&.> [: (3 $ <)&.> (<1+i.9) -.&.> <"1

and

   allunq=: ] #~ [ = [: ([: # ~.)&> ]

Already we’ve sacrificed generality by hard-coding threes and nines into the code but one of the nice features of succinct code is that there’s little to change when we revamp it.

Now that we’ve generated all possible squares one over, we notice that generating the squares one down is the same operation applied to the transpose of our initial square:

   allrc10=. |:&.>genAllRC&.|:rc00

How many possible “over” and “down” squares do we have and how many independent combinations are there?

   #&>allrc01;<allrc10
12096 12096
   */#&>allrc01;<allrc10
146313216

What do we have so far? Looking at our initial square and the first of each of our over and down possibilities, it looks like this:

     (rc00;{.allrc01),:,{.allrc10
+-----+-----+
|1 2 3|4 5 6|
|4 5 6|7 8 9|            ß "over"
|7 8 9|1 2 3|
+-----+-----+
|2 1 4|     |
|3 6 7|     |            ß "down"
|5 9 8|     |
+-----+-----+

One important thing to notice at this stage is the blank square at grid co-ordinates (1, 1) is constrained by the squares above (the “over”) and to the left (the “down”) of it. This allows us to reduce the number of items we have to consider for that square. So let’s look at only some of the possibilities for the (1, 1) square and count how many there are:

   $some11=. exactlyAllPoss (>{.allrc10) showDOPossibs >{.allrc01
392
   3{.some11
+-----+-----+-----+
|3 6 5|3 6 5|3 6 5|
|8 9 1|8 9 1|8 9 4|
|2 4 7|2 7 4|2 1 7|
+-----+-----+-----+

where

  showDOPossibs=: (<1+i.9) -.&.> ([: <"1 [) ,&.>/ [: <"1 [: |: ]
  exactlyAllPoss=: 3 : 0
     tmb=. 3 (] #~ [ = [: ([:#~.)&> ]) &> <"1 ,"3 {"1 y  NB. Top middle bottom rows
     9 (] #~ [ = [: ([: # [: ~. ,)&> ]) ,>&.>{<"1 tmb    NB. Combos w/9 unique.
)

Are there always 392 possibilities for a square constrained by an arbitrary pair of squares above and below it? Let’s take a larger random sample and count them.

   rp=: (10 (] {~ [ ? [: # ])  NB.* rp: Randomly pick x items from vector y.
   $rand11=. exactlyAllPoss &.> (10 rp allrc10) showDOPossibs &.>/ 10 rp allrc01
10 10
   #&>rand11
392 392 400 384 400 392 400 384 400 400
392 400 400 392 400 384 384 448 400 400
  . . .
  (+/%#) ,#&>rand11     NB. Average of sample
402

So it looks like there are about 400 possibilities for each (1, 1) square given an arbitrary pair of neighbors above and below it. What does this give us so far in terms of estimated number of Sudokus?

     */400,#&>allrc01;<allrc10
  5.85253e10

We’re up to about 58 billion possibilities so far – not counting the !9 permutations of each of these which pushes the total number up to about 2.1E16. However, once we make arbitrary choices for the initial 2 x 2 corner of the Sudoku grid, the remaining squares are much more highly constrained. So, at this point we've reached a peak in the number of subsequent possibilities we need to consider.

Constraints After the Peak

Let’s take the first of our 392 possibilities for (1, 1) to give us this partial Sudoku so far:

   ]sudoku=. (rc00;{.allrc01),:({.allrc10),{.some11
+-----+-----+
|1 2 3|4 5 6|
|4 5 6|7 8 9|
|7 8 9|1 2 3|
+-----+-----+
|2 1 4|3 6 5|
|3 6 7|8 9 1|
|5 9 8|2 4 7|
+-----+-----+

Fortunately, since we defined “genAllRC” to be sufficiently general, we can re-use it to generate all possible side-adjacent squares (over and down) the same way we generated the initial two from our seed square. So we generate “somerc02” – some of the (0, 2) grid possibilities – constrained by the rows to its left, e.g.

   >,.&.>/sudoku{~0 0;0 1
1 2 3 4 5 6
4 5 6 7 8 9
7 8 9 1 2 3

The greater constraint makes it clear why we have only 216 possible choices here: there are only 3 values possible for each row and !3, or 6, orderings for each row, so there are 6^3, or 216, possibilities for this square.

   $somerc02=. genAllRC >,.&.>/sudoku{~0 0;0 1
216

Here's what a few of these possible values look like:

   5{.somerc02
+-----+-----+-----+-----+-----+
|7 8 9|7 8 9|7 8 9|7 8 9|7 8 9|
|1 2 3|1 2 3|1 2 3|1 2 3|1 2 3|
|4 5 6|4 6 5|5 4 6|5 6 4|6 4 5|
+-----+-----+-----+-----+-----+

The next grid point we'll address is the one at position (1, 2), the blank square seen here:

   sudoku,.2{.{.somerc02
+-----+-----+-----+
|1 2 3|4 5 6|7 8 9|
|4 5 6|7 8 9|1 2 3|
|7 8 9|1 2 3|4 5 6|
+-----+-----+-----+
|2 1 4|3 6 5|     |
|3 6 7|8 9 1|     |
|5 9 8|2 4 7|     |
+-----+-----+-----+

We can see that the blank square is constrained by the union of the rows to its left and the columns above it, as seen here, so its generation is more complex than that of the (0, 2) square:

   sudoku,.2{.{.somerc02
+-----+-----+-----+
|1 2 3|4 5 6|7 8 9|
|4 5 6|7 8 9|1 2 3|
|7 8 9|1 2 3|4 5 6|
+-----+-----+-----+
|2 1 4|3 6 5|     |
|3 6 7|8 9 1|     |
|5 9 8|2 4 7|     |
+-----+-----+-----+

  somerc12=. exactlyAllPoss &.> (,.&.>/sudoku{~1 0;1 1) showDOPossibs &.> somerc02

We introduce two new verbs here: exactlyAllPoss and showDOPossibs. This latter one, applied first, shows us all possible values for each cell given a “down” and “over” neighbor, i.e. all the row values to the left and the column values above:

Constraints on the Left	Constraints Above
>,.&.>/sudoku{~0 0;0 1 1 2 3 4 5 6 4 5 6 7 8 9 7 8 9 1 2 3	>{.somerc02 7 8 9 1 2 3 4 5 6

Details on Generating Constrained Possibilities

The two new verbs, “showDOPossibs” and “exactlyAllPoss”, deserve deeper scrutiny. The first of these is defined as follows:

   showDOPossibs=: (<1+i.9) -.&.> ([: <"1 [) ,&.>/ [: <"1 [: |: ]

These are both necessary for the (1, 2) square, but not the (0, 2) square, because the former is more highly constrained: it is also constrained by the (0, 2) square above it. The first-evaluated phrase on the right of "showDOPossibs" combines the columns of the "over" square (above the blank) with the row elements of the "down" square (to the left of the blank):

   ]downsqs=. >,.&.>/sudoku{~1 0;1 1
2 1 4 3 6 5
3 6 7 8 9 1
5 9 8 2 4 7
   ]oversq=. >{.somerc02
7 8 9
1 2 3
4 5 6

   downsqs (([: <"1 [) ,&.>/ [: <"1 [: |: ]) oversq
+-----------------+-----------------+-----------------+
|2 1 4 3 6 5 7 1 4|2 1 4 3 6 5 8 2 5|2 1 4 3 6 5 9 3 6|
+-----------------+-----------------+-----------------+
|3 6 7 8 9 1 7 1 4|3 6 7 8 9 1 8 2 5|3 6 7 8 9 1 9 3 6|
+-----------------+-----------------+-----------------+
|5 9 8 2 4 7 7 1 4|5 9 8 2 4 7 8 2 5|5 9 8 2 4 7 9 3 6|
+-----------------+-----------------+-----------------+

Next, by removing these dis-allowed values from the possible ones, we get the possible values for each cell:

   I9
1 2 3 4 5 6 7 8 9
   ]posstbl=. (<I9) -.&.> downsqs (([: <"1 [) ,&.>/ [: <"1 [: |: ]) oversq
+---+-----+-----+
|8 9|7 9  |7 8  |
+---+-----+-----+
|2 5|4    |2 4 5|
+---+-----+-----+
|3 6|1 3 6|1    |
+---+-----+-----+

 The next verb – "exactlyAllPoss" –generates all instances of 3x3 squares that can be made from the above.

  exactlyAllPoss=: 3 : 0
  tmb=. 3 (] #~ [ = [: ([:#~.)&> ]) &> <"1 ,"3 {"1 y  NB. Top middle bottom rows
  9 (] #~ [ = [: ([: # [: ~. ,)&> ]) ,>&.>{<"1 tmb    NB. Combs w/9 unique.
)

The first line starts by generating all possible combinations for each row of the possibilities table:

   ${"1 posstbl     NB. For each of 3 rows, 2 elements in first, then up to 3...
3 2 3 3
   $,"3 {"1 posstbl NB. Collapse last three dimensions
3 18
   ,"3 {"1 posstbl
+-----+-----+-----+-----+-----++-----+++-----+-----+-----+-----+-----++-----+++
|8 7 7|8 7 8|     |8 9 7|8 9 8||     |||9 7 7|9 7 8|     |9 9 7|9 9 8||     |||
+-----+-----+-----+-----+-----++-----+++-----+-----+-----+-----+-----++-----+++
|2 4 2|2 4 4|2 4 5|     |     ||     |||5 4 2|5 4 4|5 4 5|     |     ||     |||
+-----+-----+-----+-----+-----++-----+++-----+-----+-----+-----+-----++-----+++
|3 1 1|     |     |3 3 1|     ||3 6 1|||6 1 1|     |     |6 3 1|     ||6 6 1|||
+-----+-----+-----+-----+-----++-----+++-----+-----+-----+-----+-----++-----+++

Obviously many of these are invalid in a Sudoku because of repeated elements, so eliminate those:

   ~.&.>,"3 {"1 posstbl
+---+---+-----+-----+---++-----+++-----+-----+---+-----+---++---+++
|8 7|8 7|     |8 9 7|8 9||     |||9 7  |9 7 8|   |9 7  |9 8||   |||
+---+---+-----+-----+---++-----+++-----+-----+---+-----+---++---+++
|2 4|2 4|2 4 5|     |   ||     |||5 4 2|5 4  |5 4|     |   ||   |||
+---+---+-----+-----+---++-----+++-----+-----+---+-----+---++---+++
|3 1|   |     |3 1  |   ||3 6 1|||6 1  |     |   |6 3 1|   ||6 1|||
+---+---+-----+-----+---++-----+++-----+-----+---+-----+---++---+++

Many of these are invalid because they don't have the necessary three elements, so retain only those with three unique items:

   ]tmb=. 3 (] #~ [ = [: ([:#~.)&> ]) &> <"1 ,"3 {"1 posstbl
+-----+-----+
|8 9 7|9 7 8|
+-----+-----+
|2 4 5|5 4 2|
+-----+-----+
|3 6 1|6 3 1|
+-----+-----+

On the second line, we do something very similar to what we did on the first line: we generate all combinations of the valid top, middle, and bottom rows:

   ${<"1 tmb
2 2 2
   ,>&.>{<"1 tmb
+-----+-----+-----+-----+-----+-----+-----+-----+
|8 9 7|8 9 7|8 9 7|8 9 7|9 7 8|9 7 8|9 7 8|9 7 8|
|2 4 5|2 4 5|5 4 2|5 4 2|2 4 5|2 4 5|5 4 2|5 4 2|
|3 6 1|6 3 1|3 6 1|6 3 1|3 6 1|6 3 1|3 6 1|6 3 1|
+-----+-----+-----+-----+-----+-----+-----+-----+

Then we keep only those with nine unique items (which happens to be all of them in this case):

   9 (] #~ [ = [: ([: # [: ~. ,)&> ]) ,>&.>{<"1 tmb
+-----+-----+-----+-----+-----+-----+-----+-----+
|8 9 7|8 9 7|8 9 7|8 9 7|9 7 8|9 7 8|9 7 8|9 7 8|
|2 4 5|2 4 5|5 4 2|5 4 2|2 4 5|2 4 5|5 4 2|5 4 2|
|3 6 1|6 3 1|3 6 1|6 3 1|3 6 1|6 3 1|3 6 1|6 3 1|
+-----+-----+-----+-----+-----+-----+-----+-----+

Now that we have seen how these two verbs work, let's use them to generate all possible squares for the (1, 2) grid square in our evolving Sudoku:

   $exactlyAllPoss &.> (,.&.>/sudoku{~1 0;1 1) showDOPossibs &.> somerc02
216
   ~.$&>exactlyAllPoss &.> (,.&.>/sudoku{~1 0;1 1) showDOPossibs &.> somerc02
8

So, we have 216 sets of 8 squares each for possible values of this (1, 2) square. How many are there in total and how many of these are unique?

   $;exactlyAllPoss &.> (,.&.>/sudoku{~1 0;1 1) showDOPossibs &.> somerc02
1728
   $~.;exactlyAllPoss &.> (,.&.>/sudoku{~1 0;1 1) showDOPossibs &.> somerc02
216

We can apply this same process for generating the possibilities of the (0, 2) and (1, 2) grid points to the first two squares on the bottom row:

   somerc20=. |:&.>genAllRC |:>,&.>/sudoku{~0 0;1 0
   somerc21=. a:-.~exactlyAllPoss &.> (,&.>/sudoku{~0 1;1 1) showDOPossibs~ &.> somerc20
   #&>somerc02;somerc12;somerc20;<somerc21
216 216 216 192

Finishing up

Here is one possible Sudoku so far:

   (sudoku,.({.somerc02),{.>{.somerc12),({.somerc20),{.>{.somerc21
+-----+-----+-----+
|1 2 3|4 5 6|7 8 9|
|4 5 6|7 8 9|1 2 3|
|7 8 9|1 2 3|4 5 6|
+-----+-----+-----+
|2 1 4|3 6 5|8 9 7|
|3 6 7|8 9 1|2 4 5|
|5 9 8|2 4 7|3 6 1|
+-----+-----+-----+
|6 3 1|5 7 4|     |
|8 4 2|9 1 2|     |
|9 7 5|6 3 8|     |
+-----+-----+-----+

We see that the final blank square is highly constrained. Perhaps we can apply the methods we've already developed to generate this final part of the puzzle. Here are the constraints:

   ((>{.somerc20),.>{.>{.somerc21);(>{.somerc02),>{.>{.somerc12
+-----------+-----+
|6 3 1 5 7 4|7 8 9|
|8 4 2 9 1 2|1 2 3|
|9 7 5 6 3 8|4 5 6|
|           |8 9 7|
|           |2 4 5|
|           |3 6 1|
+-----------+-----+

Taking a look at what our possibilities are, we run into a problem:

   'down2 over2'=. ((>{.somerc20),.>{.>{.somerc21);(>{.somerc02),>{.>{.somerc12
   down2 showDOPossibs over2
+---+---+---+
|9  |   |2 8|
+---+---+---+
|5 6|3 7|   |
+---+---+---+
|   |1  |2 4|
+---+---+---+

Some of the cells are too highly constrained: they have no possible values! Fortunately, at this point we have few enough possibilities for this last column and row of the grid that we can simply generate all of them and check which combinations over-constrain the final square.

   check0rows=: [: *./ [: (# = [: # ~.)&> <"1
   check0cols=: [: ([: *./ [: (# = [: # ~.)&> <"1) |:

  $rows=. (check0rows&>,rows)#,rows
1536
  $cols=. (check0cols&>,cols)#,cols
1728

   6!:2 'rr=. rows (([: ([: -. 0 e. [: #&> ,) showDOPossibs)&>/) cols'
25.0832
   $rr
1536 1728
   2 2{.rr
0 0
0 0
   +/,rr
337536

   $valcombs=. |:(([:$])#:[:I.[:,]) rr
2 337536
   5{."1 valcombs
0 0  0  0  0
4 5 13 17 21

   'ixr ixc'=. valcombs{"1~?1{$valcombs
   ixr,ixc
841 325

  ixc{cols
+-----+
|7 9 8|
|1 2 3|
|6 4 5|
|9 8 7|
|4 5 2|
|3 6 1|
+-----+

   ]rc22=. ,/>exactlyAllPoss (>ixr{rows) showDOPossibs >ixc{cols
5 7 6
8 1 4
2 3 9

   sudoku=. sudoku,.1 0 0 1 0 0<;.1]>ixc{cols
   sudoku=. sudoku,|:&.>1 0 0 1 0 0<;.1]|:>ixr{rows
   ]sudoku=. (<rc22) (<2 2)}sudoku
+-----+-----+-----+
|1 2 3|4 5 6|7 9 8|
|4 5 6|7 8 9|1 2 3|
|7 8 9|1 2 3|6 4 5|
+-----+-----+-----+
|2 1 4|3 6 5|9 8 7|
|3 6 7|8 9 1|4 5 2|
|5 9 8|2 4 7|3 6 1|
+-----+-----+-----+
|8 3 2|9 1 4|5 7 6|
|9 7 5|6 3 2|8 1 4|
|6 4 1|5 7 8|2 3 9|
+-----+-----+-----+

   ]numpercell=. 3 3$ (!9),(#allrc01),1,(#allrc10),400,1,1,1,1{$valcombs
362880 12096      1
 12096   400      1
     1     1 337536

   */,numpercell
7.16847e21
   */ x: numpercell      NB. Does not agree with the "official" count.
7168473431594237952000

   6670903752021072936960%7168473431594237952000
0.930589
   400*6670903752021072936960%7168473431594237952000
372.236
   0.930589*337536
314107
   3 3$(!9),(#allrc01),1,(#allrc10),400,1,1,1,314407
362880 12096      1
 12096   400      1
     1     1 314407

   */x: ,3 3$(!9),(#allrc01),1,(#allrc10),400,1,1,1,314407
6677267687616282624000
   12j10":6670903752021072936960x%6677267687616282624000x
0.9990469252

   314407*0.9990469252
314107
   */x: ,3 3$(!9),(#allrc01),1,(#allrc10),400,1,1,1,314107
6670896390837633024000
   16j14":6670903752021072936960x%6670896390837633024000x
1.00000110347741
   314107*1.00000110347741
314107

   */x: ,3 3$(!9),(#allrc01),1,(#allrc10),402,1,1,1,314107
6704250872791821189120
   16j14":6670903752021072936960x%6704250872791821189120
0.99502597360936
   314107*0.99502597360936
312545

   */x: ,3 3$(!9),(#allrc01),1,(#allrc10),402,1,1,1,312545
6670911788138181427200
   16j14":6670903752021072936960x%6670911788138181427200x
0.99999879534952

Advanced Topics

Learning, Teaching, and Problem-solving

Materials

. -- Devon McCormick <<DateTime>>