There is a 5×5 grid in front of you. You have to fill 25 squares with only 0 and 1.
But, every pair of neighboring squares (that is not diagonally adjacent) needs to have a product equal to 0.
How many possible grids are there?
The program below counts 37,869, a sampling (every thousandth grid shown) of which is:
0 0 0 0 0
0 0 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 1 0 1
0 1 0 1 0
0 0 1 0 0
1 0 0 1 0
0 0 0 0 0
0 1 0 1 0
0 0 1 0 0
1 0 0 0 1
0 0 0 1 0
0 0 0 0 0
1 0 0 1 0
0 0 1 0 1
0 0 0 0 0
0 1 0 1 0
0 0 0 0 1
0 0 0 0 0
0 1 0 1 0
0 0 1 0 1
0 1 0 1 0
0 0 0 0 1
0 0 1 0 0
1 0 0 1 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 1
1 0 0 0 0
0 0 1 0 0
1 0 0 0 0
0 1 0 1 0
0 0 0 1 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 1 0 0
0 1 0 1 0
1 0 0 0 1
0 0 1 0 0
0 0 0 1 0
0 1 0 0 1
0 0 0 1 0
1 0 1 0 1
0 1 0 0 0
0 0 0 1 0
1 0 1 0 0
0 0 0 1 0
1 0 1 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 0 1
0 0 0 1 0
0 0 0 0 0
1 0 0 1 0
0 0 1 0 0
0 1 0 0 0
1 0 0 0 0
0 0 0 0 0
1 0 1 0 0
0 0 1 0 0
1 0 0 0 0
0 0 1 0 0
0 1 0 0 0
1 0 1 0 0
0 0 1 0 1
0 0 0 0 0
0 1 0 0 0
0 0 0 0 1
0 0 0 1 0
0 0 1 0 1
0 1 0 0 0
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 1 0 1
1 0 0 1 0
0 0 1 0 0
0 1 0 1 0
1 0 0 0 0
0 1 0 0 0
0 0 0 0 1
1 0 0 0 0
0 0 1 0 1
1 0 0 1 0
0 1 0 0 0
0 0 1 0 1
0 0 0 1 0
0 0 0 0 0
0 1 0 0 0
0 1 0 0 0
1 0 0 1 0
0 0 0 0 1
0 1 0 1 0
1 0 0 0 0
0 1 0 0 1
0 0 0 0 0
0 1 0 0 0
1 0 0 0 1
0 1 0 1 0
0 1 0 0 1
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 1 0 0 1
1 0 1 0 0
0 1 0 0 1
1 0 0 0 0
0 0 0 0 0
0 1 0 1 0
0 0 0 0 1
1 0 1 0 0
0 0 0 1 0
0 0 0 0 0
0 1 0 1 0
1 0 0 0 0
0 0 1 0 1
1 0 0 0 0
0 0 1 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 0 0 0 1
0 1 0 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 0 1
0 1 0 0 0
1 0 1 0 0
1 0 0 0 0
0 0 1 0 1
1 0 0 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
0 1 0 1 0
1 0 0 0 0
0 0 0 1 0
1 0 1 0 0
1 0 0 0 1
0 0 0 1 0
1 0 0 0 0
0 1 0 1 0
0 0 1 0 0
1 0 0 0 1
0 1 0 1 0
0 0 0 0 0
1 0 1 0 0
0 0 0 0 0
1 0 0 1 0
0 0 0 0 1
0 0 1 0 0
1 0 0 0 1
0 1 0 0 0
1 0 0 1 0
0 1 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 1 0
1 0 1 0 0
0 0 0 0 0
0 1 0 0 0
1 0 1 0 1
0 1 0 0 0
1 0 1 0 0
0 0 0 1 0
1 0 0 0 1
0 0 1 0 0
0 0 0 0 0
1 0 1 0 0
0 1 0 1 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 0 1 0 1
0 0 0 1 0
1 0 0 0 0
0 0 1 0 0
1 0 0 1 0
In placing each bit, If the bit above and the bit to the left were both zero, the newly placed bit was tried out as both zero and one and so on in a branching tree. If either the bit above or the bit to the left was a 1, only a zero was allowed to continue on with the placements.
DefDbl A-Z
Dim crlf$, grid(5, 5), ct
Private Sub Form_Load()
Text1.Text = ""
crlf$ = Chr(13) + Chr(10)
Form1.Visible = True
DoEvents
addon 1, 1
Text1.Text = Text1.Text & ct & " done"
End Sub
Sub addon(row, col)
DoEvents
If grid(row - 1, col) = 0 And grid(row, col - 1) = 0 Then allow1 = 1 Else allow1 = 0
r = row
c = col + 1: If c > 5 Then c = 1: r = r + 1
If r < 6 Then
grid(row, col) = 0
addon r, c
If allow1 Then
grid(row, col) = 1
addon r, c
End If
Else
ct = ct + 1
If ct Mod 1000 = 0 Then
For r = 1 To 5: For c = 1 To 5
Text1.Text = Text1.Text & grid(r, c) & " "
Next: Text1.Text = Text1.Text & crlf: Next: Text1.Text = Text1.Text & crlf
End If
End If
End Sub
Edited on April 26, 2019, 12:40 pm
|
|
Posted by Charlie
on 2019-04-26 12:39:15 |
computer solution
