NYCJUG/2012-09-11
Sudoku, statistics, distributions, effect of noise on short-term memory, data chunking, mathematical brain area
Location:: ThomasNet
Meeting Agenda for NYCJUG 20120911
1. Beginner's regatta: generating complete Sudokus - how many are there? See "CodeGolf-SudokuGenerator.pdf" and "SolvedSudokuPuzzleGeneration.pdf". 2. Show-and-tell: Building families of statistical distributions - Poisson and Beta - see "Beta distribution - selections.pdf". 3. Advanced topics: an example of high-dimensional data presentation - see "Interactive High-Dimensional data presentation - GGobi.pdf" and "interface-classification-boundariesInHighDimensions.pdf". 4. Learning, teaching and promoting J, et al.: data on how we think and what makes us more or less effective as thinkers: see "Noisy surroundings take toll on short.pdf", "Inattention blindness due to brain load.pdf", "Applying New Rules Costly.pdf", "Motor Chunking - how our brains parse and concatenate learned actions.pdf", "General Information about Chunking.pdf", "Using Motor-Chunking in Education.pdf", and " Mathematics or Memory - collision course in brain.pdf" An example of a fun introduction to a language: see "Land of Lisp.pdf". See "Pretty Pictures in J.pdf" and "Less Than Brute Force.pdf".
Proceedings
...
Beginner's Regatta
The following is from [From: http://codegolf.stackexchange.com/questions/5693/minimal-sudoku-generator this CodeGolf page.]
Minimal Sudoku Generator
Ask questions if you need to, I'll elaborate on anything that needs clarified. My challenge is to unsolve a sudoku to a minimal state. Basically take a supplied, solved, sudoku board and unsolve it as far as possible while keeping the solution unique. I'll leave input up to you, I don't like forcing anything which would make some solutions longer. Output can be anything reasonable, as long as it spans the nine lines it'll take to display the sudoku board, for example:
{[0,0,0], [0,0,0], [0,1,0]} ┐ {[4,0,0], [0,1,0], [0,0,0]} ├ Easily understood to me {[1,2,0], [0,0,0], [0,0,0]} ┘ 000000010 ┐ 400010000 ├ A-OKAY 120000000 ┘ 000, 000, 010 ┐ 400, 010, 000 ├ Perfectly fine 120, 000, 000 ┘ 000000010400010000120000000 <-- Not okay!Example
input:
693 784 512 487 512 936 125 963 874 932 651 487 568 247 391 741 398 625 319 475 268 856 129 743 274 836 159output:
000 000 010 400 000 000 020 000 000 000 050 407 008 000 300 001 090 000 300 400 200 050 100 000 000 806 000Most minimal answer in shortest time is the winner.
Solved Sudoku Puzzles: How Many?
A “solved Sudoku puzzle” is a 3x3 arrangement of 3x3 tables where each table contains the digits one through nine, as does each line of digits across the rows and down the columns throughout the arrangement of tables. The number of possible arrangements of nine tables without paying attention to what makes an arrangement a valid sudoku, is
9^~!9 1.09111e50
This large number is simple enough to calculate but does not address the more difficult question of how many valid sudoku arrangements there are. How might we figure out this number? To start with, let's consider only the top leftmost square in isolation. Obviously, there are !9 ways to permute these nine values, or 362,880. Since any permutation will do, let's start with the simplest one for the square in the position (0,0):
]I9=: >:i.9 NB. The digits we care about 1 2 3 4 5 6 7 8 9 ]sq00=. 3 3 $ 0 A. I9 NB. Their 0th “anagram” 1 2 3 4 5 6 7 8 9
An Interesting Wrong Turn
Now consider the next table, the one to left of this first one. The first row of this first table over can contain any of our nine digits except those in the first row of sq00, or
(0{sq00) -. I9
Similarly, the second row of this next table over can have any digits except those in the second row of sq00, or
(1{sq00) -. I9
The same logic applies to the third row. Combining these ideas, the possibilities for each row of the next table over is
(<I9)-.&.> <"1 sq00 +-----------+-----------+-----------+ |4 5 6 7 8 9|1 2 3 7 8 9|1 2 3 4 5 6| +-----------+-----------+-----------+
Taking all combinations of these possibilities
$ { (<I9)-.&.> <"1 sq00 6 6 6 $, { (<I9)-.&.> <"1 sq00 216 5{., { (<I9)-.&.> <"1 sq00 +-----+-----+-----+-----+-----+ |4 1 1|4 1 2|4 1 3|4 1 4|4 1 5| +-----+-----+-----+-----+-----+
Looking at these first few, we see an obvious problem but, since there are so few possibilities, it's simple enough to weed out the obviously wrong ones.
3!6 20 $ixs3of6=. ~./:~"1 ] 3{."1 (i.!6) A. i.6 20 3 /:~ ~. ,ixs3of6 0 1 2 3 4 5 20^3 8000 ${ (<ixs3of6) {&.> (<I9)-.&.> <"1 sq00 20 3 20 3 20 3 $0 2 4 1 3 5|:{ (<ixs3of6) {&.> (<I9)-.&.> <"1 sq00 20 20 20 3 3 3 $~.>,<"2]0 2 4 1 3 5|:{ (<ixs3of6) {&.> (<I9)-.&.> <"1 sq00 2400 3 3 $ { (<I9)-.&.> <"1 sq00 6 6 6 $ >{ (<I9)-.&.> <"1 sq00 6 6 6 3 allPossRows=. { (<I9)-.&.> <"1 sq00 +/,3=#&>~.&.> allPossRows 162 162^3 4.25153e6 rp=. (<I9)-.&.> <"1 sq00 apr=. (,allPossRows)#~,3=#&>~.&.> allPossRows $apr e.&.>/ rp 162 3 3{.apr e.&.>/ rp +-----+-----+-----+ |1 0 0|0 1 1|1 1 1| +-----+-----+-----+ |1 0 0|0 1 1|1 1 1| +-----+-----+-----+ |1 0 1|0 1 0|1 1 1| +-----+-----+-----+ $3=&>|:+/&.>apr e.&.>/ rp 3 162 'r0 r1 r2'=. 3=&>|:+/&.>apr e.&.>/ rp +/&>r0;r1;r2 36 36 36 */+/&>r0;r1;r2 46656 216^2 46656 $>(r0#apr),&.>/(r1#apr),:&.>/r2#apr 36 36 36 3 3 $(r0#apr),&.>/(r1#apr),:&.>/r2#apr 36 36 36 $,(r0#apr),&.>/(r1#apr),:&.>/r2#apr 46656 1 10 100 1000{,(r0#apr),&.>/(r1#apr),:&.>/r2#apr +-----+-----+-----+-----+ |4 7 5|4 7 5|4 7 5|4 7 5| |7 1 2|7 1 2|7 2 1|9 2 3| |4 1 3|4 3 5|6 2 1|6 2 1| +-----+-----+-----+-----+ apr=. ,(r0#apr),&.>/(r1#apr),:&.>/r2#apr $apr#~9=([: # [: ~. ,)&>apr 432 $apr=. apr#~9=([: # [: ~. ,)&>apr 432 1 10 100{apr +-----+-----+-----+ |4 7 5|4 7 5|5 8 4| |8 9 1|9 8 3|7 9 3| |6 3 2|6 1 2|6 1 2| +-----+-----+-----+ 432^2 186624
Now find the tables below:
allPoss=. { cp=. (<I9)-.&.> <"1 |:sq00 apc=. (,allPoss)#~,3=#&>~.&.> allPoss 'c0 c1 c2'=. 3=&>|:+/&.>apc e.&.>/ cp apc=. ,(c0#apc),&.>/(c1#apc),:&.>/c2#apc $apc=. |:&.>apc#~9=([: # [: ~. ,)&>apc 432 3{.apc +-----+-----+-----+ |2 6 8|2 6 8|2 6 8| |3 9 4|3 9 7|3 9 1| |5 1 7|5 1 4|5 4 7| +-----+-----+-----+ isValidDO 4 : 0 rawPoss=. (<I9)-.&.>(<"1 x),&.>/<"1|:y -.0 e. ,#&>(,&.>/~i.3) possibleIntersection &.> <rawPoss NB.EG valmat=. down isValidDO&>/ over ) 6!:2 'valcombs=. (([:$])#:[:I.[:,]) apc isValidDO &>/ apr' 58.7522 $valcombs 26880 2 possibleIntersection 4 : '(,{(0{x){y)([#~[ e. ]) ,{(1{x){"1 y' 2 2$4{.sq00;(0{apr),_1{apc +-----+-----+ |1 2 3|4 7 5| |4 5 6|8 9 1| |7 8 9|6 2 3| +-----+-----+ |9 3 5| | |6 7 1| | |8 4 2| | +-----+-----+
Better than Brute Force Solution?
The empty square shown above will be a recurring theme as we fill in successive squares of this puzzle. Currently, I have a “brute force” solution to generate all possible values for the blank square based on the restrictions introduced by the square above and to the left of it.
above;left +-----+-----+ |4 7 5|9 3 5| |8 9 1|6 7 1| |6 2 3|8 4 2| +-----+-----+ (<"1 left) ,&.>/ <"1 |:above +-----------+-----------+-----------+ |9 3 5 4 8 6|9 3 5 7 9 2|9 3 5 5 1 3| +-----------+-----------+-----------+ |6 7 1 4 8 6|6 7 1 7 9 2|6 7 1 5 1 3| +-----------+-----------+-----------+ |8 4 2 4 8 6|8 4 2 7 9 2|8 4 2 5 1 3| +-----------+-----------+-----------+ ]poss=. (<I9)-.&.>(<"1 left) ,&.>/ <"1 |:above +---------+-------+---------+ |1 2 7 |1 4 6 8|2 4 6 7 8| +---------+-------+---------+ |2 3 5 9 |3 4 5 8|2 4 8 9 | +---------+-------+---------+ |1 3 5 7 9|1 3 5 6|6 7 9 | +---------+-------+---------+
The problem I have not solved is how to quickly generate all possible solutions given the restrictions embodied in poss.
Show-and-Tell
The following [From http://en.wikipedia.org/wiki/Beta_distribution is from Wikipedia.]
Beta Distribution
Not to confused with Beta function.
Advanced Topics
...
Learning, teaching and promoting J
...
Attachments
- File:CodeGolf-SudokuGenerator.pdf
- File:SolvedSudokuPuzzleGeneration.pdf
- File:Beta distribution - selections.pdf
- File:Interactive High-Dimensional data presentation - GGobi.pdf
- File:Interface-classification-boundariesInHighDimensions.pdf
- File:Noisy surroundings take toll on short.pdf
- File:Inattention blindness due to brain load.pdf
- File:Applying New Rules Costly.pdf
- File:Motor Chunking - how our brains parse and concatenate learned actions.pdf
- File:General Information about Chunking.pdf
- File:Using Motor-Chunking in Education.pdf
- File:Mathematics or Memory - collision course in brain.pdf
- File:Land of Lisp.pdf
- File:Pretty Pictures in J.pdf
- File:Less Than Brute Force.pdf