Essays/ChessboardPuzzle
Here's another task from a puzzle site I solved with J.
Cut a 6 times 6 chessboard to 18 black and 18 white squares. Assemble them to a 6 times 6 board in such a way that each row and column has 3 black and 3 white squares, every row is different, and every column is different. How many boards can you get this way? The rows and columns of the board are numbered, so boards that differ in rotation or flipping count as different.
Here are the J commands I used to solve this puzzle.
NB. KöMaL teszt 2007 ápr-máj Informatika 11-12. osztályosoknak 5. feladat
vari =: [{."_1]A.~#@:]([(]*i.@:%)&!-)[
lines =: (#~(3:=+/)"1)>,{6$<0 1
#allc =: 5 vari lines
NB. sampc =: (?1000$#allc){allc
NB. (3!:1 sampc)1!:2<'sampc'
NB. #sampc =: 3!:2]1!:1<'sampc'
NB. #sampb =: (#~ [: */"1 [: (2&<:*.<:&3) +/"2) sampc
NB. #sampa =: (#~ (*./@:~:@:|:)"2) sampb
NB. #sampf =: (#~ (*./@:~:)"2) (,3:>+/)"2 sampa
#allb =: (#~ [: */"1 [: (2&<:*.<:&3) +/"2) allc
#alla =: (#~ (*./@:~:@:|:)"2) allb
#allf =: (#~ (*./@:~:)"2) (,3:>+/)"2 alla
NB. 194400
The first few lines enumerate all 5 times 6 boards in which all 5 lines are different and they each have three zeros and three ones in each line. The large array of such boards are put into allc. I use the verb vari here which I've already posted at Phrases/Sets.
The commented lines that follow take a sample of 1000 boards of these so I could experiment on them without the verbs taking too much.
Then, we filter those boards where each columns have two or three white squares (note that the columns are only 5 squares high here), because only that way can the whole table have columns with 3 white and 3 black each. These boards get into allb.
After this, we filter only those boards if which no two columns are the same. The verb to be used here is *./@:~: which returns true iff the input array has only unique items. The result goes to alla.
Finally, we fill out the last line of the boards. This is easy, and can be done in a unique way, because we just have to add a square that completes the above column to three black and three white squares. This is required so we can check that the last line is not the same as any of the five lines above.
After this last filtering step, we get the list of all possible solutions in allf. (It can be verified easily that they are in lexicographic order.)
The result is that there are exactly 194400 boards. The correctness of this solution has not yet been verified. The official solution is 237600, but that solution seems almost certainly wrong. I do not post here the throwaway code I used to compare their solution to mine. (Update: the official solution has now been corrected.)
The puzzle and official solution is at [1].
-- B Jonas <<DateTime(2007-05-16T11:10:54Z)>>
The possible rows are all the boolean vector of length 6 with exactly three 1s. There are 3!6 such vectors.
U=: (#~ 3 = +/"1) #: i.2^6 $U 20 6 U 0 0 0 1 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0
The chessboards with all different such rows, without regard to ordering, are (6 comb #U){U . Of these, only those with three 1s in each column are permitted; moreover, only those with all different columns are permitted. Thus:
comb=: 4 : 0 NB. All size x combinations of i.y
k=. i.>:d=.y-x
z=. (d$<i.0 0),<i.1 0
for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
; z
)
b=: (6 comb #U){U
$b
38760 6 6
b=: (#~ ((6$3) -: +/)"2) b NB. 3 1s in each column
$b
330 6 6
b=: (#~ ((6$1) -: ~:@|:)"2) b NB. all different columns
$b
270 6 6
Each of these 270 boards can have its rows permuted in !6 different ways, obtaining 194400 = 270*!6 different solutions.
perm=: i.@! A. i. NB. all permutations of i.n
b=: ,/ (perm 6){"2 b
$b
194400 6 6
Some assertions on the solutions:
test=: 3 : 0 assert. ~: y NB. unique assert. 3=+/"2 y NB. each column has three 1s assert. 3=+/"1 y NB. each row has three 1s assert. ((6$1) -: ~: )"2 y NB. rows are unique assert. ((6$1) -: ~:@|:)"2 y NB. columns are unique 1 ) test b 1
At the puzzle website the official answer has 237600 entries, but contains obvious errors. The first few entries are as follows. Note that the first 2 columns are identical in each entry.
Ez a(z) 1. megoldas: 000111 001011 001101 110010 110100 111000 Ez a(z) 2. megoldas: 000111 001011 001101 110010 111000 110100 Ez a(z) 3. megoldas: 000111 001011 001101 110100 110010 111000
If the official answer is saved in the file \junk\tv274.txt , the following code converts the file into a boolean array and tests it.
t=. ('E'&= <;.1 ]) _8}. CR -.~ 1!:1 <'\junk\tv274.txt'
t=. '1'=];._2&> (1+t i.&>LF)}.&.> t
$t
237600 6 6
test t
|assertion failure: test
| ((6$1)-:~:@|:)"2 y
That is, the official answer fails the "unique columns" test. If entries with duplicate columns are removed, then the sorted such entries match our sorted entries.
p=: ((6$1) -: ~:@|:)"2 t NB. select entries with unique columns +/p 194400 $b NB. our entries 194400 6 6 b -:&(/:~) p#t NB. sorted entries match our entries 1
-- Roger Hui <<DateTime(2007-05-16T22:07:33Z)>>
There's a second part of this story now, told at Seven by seven farming puzzle. There we solve the following harder variant of this task.
A seven by seven cell table has to be filled in such a way that each row and each column must have exactly two cells with a 0, two cells with a 1, and three cells with a 2 in them; no two rows can be exactly the same; and no two columns can be exactly the same. Given the contents of the first two rows, compute the number of ways the rest of the table can be filled.
-- -- B Jonas <<DateTime(2010-02-03T23:53:54+0200)>>