Thread replies: 2
Thread images: 1
Thread images: 1
File: chrome.png (123KB, 2086x646px) Image search:
[Google]
123KB, 2086x646px
working on:
projecteuler.net/problem=544
Let F(r,c,n) be the number of ways to color a rectangular grid with r rows and c columns using at most n colors such that no two adjacent cells share the same color.
found a generalized formula for F(2, 2, n)
looking to extend this to F(r, c, n)
I have:
((n-1)*(n-1)*(n-2)+(n-1))*n
for 2x2 grids
because 1st cell has n choices, 2 cells adjacent will have n-1 choices followed by the last corner of (2n-3)
applying my logic to the 4*3 grid, i get something like 6*5^8*4*4*3 which is off by about 10 million.
any guidance?
>>
>>7813073
I have done a similar algorithm in the past.
I assigned a color for each digit (0,1,2,...,9)
(so it worked for up to 10 colors ...)
Tested all permutations (some optimization allowed to only test reasonable permutations).
In the case of a 2x2 matrix and 3 colors it worked like this
0000
Test: "fail, add one in base 3"
0001
Test "fail, add one in base 3"
0002
Test "fail, add one in base 3"
0010
Test "fail, add one in base 3"
....
2222
Test "fail"
end
I realized it would be much better if my test function would actually tell the algorithm what digit to increment.
0000
Test: "fail, at digit #2"
0100
Test "fail at digit #3"
0110
Test "win, increment count"
0111
...
There's probably better ways to do this (either with proper combinatorics or with a most efficient algorithm) but I was looking for a programming challenge for "beginners" at the time ...
Thread posts: 2
Thread images: 1
Thread images: 1