lionaneesh
March 11th, 2012, 02:32 PM
After trying for 2-3 hours I was able to find a solution to the following puzzle (http://www.enterthetank.com/bombtrap.html) :-
Problem Description :-
Given a 8 x 8 , board with 64 boxes fill 8 of these boxes in such a way that no two filled boxes fall on the same straight
line - horizontally, vertically or diagonally!
Checker (source (http://www.go4expert.com/forums/showthread.php?t=27993)) :-
#!/bin/env/python
# Checker for a 8x8 bomb trap
# Correct Solution
game = [
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0]
]
def check_ones(array) :
ones = 0
for h in array:
if isinstance(h, list) :
ones = ones + check_ones(h)
elif h == 1:
ones = ones + 1
return ones
def diagonal_check(game):
errors = ''
for i in range(0, 7):
for j in range(0, 7):
if game[i][j] != 1:
continue
# diagonal 1
diag1 = []
h, k = i, j
# addition loop
while h <= 7 and h >= 0 and k <= 7 and k >= 0:
diag1.append(game[h][k])
h = h + 1
k = k + 1
# subtration loop
h, k = i-1, j-1
while h <= 7 and h >= 0 and k <= 7 and k >= 0:
diag1.append(game[h][k])
h = h - 1
k = k - 1
# diagonal 2
diag2 = []
# add k loop
h, k = i, j
while h <= 7 and h >= 0 and k <= 7 and k >= 0:
diag2.append(game[h][k])
h = h - 1
k = k + 1
# add h loop
h, k = i + 1, j - 1
while h <= 7 and h >= 0 and k <= 7 and k >= 0:
diag2.append(game[h][k])
h = h + 1
k = k - 1
# at this point we have 2 diagonal arrays and we can simply check
# for multiple 1's, if there are multiple 1's in any diag list
# it means we have 2 points in a diagonal i.e check failed
if check_ones(diag1) > 1:
errors += "Diagonal 1 check @ point [%d, %d] evaluated to FALSE\n" % (i+1, j+1)
if check_ones(diag2) > 1:
errors += "Diagonal 2 check @ point [%d, %d] evaluated to FALSE\n" % (i+1, j+1)
if errors != '':
print errors
return False
return True
check1 = True # Let's be +ve ;)
errors = ''
# let the game begin
if check_ones(game) != 8:
print "Please fill up exactly 8 places."
exit()
for i in range(0, 7):
horizontal = []
vertical = []
for j in range(0, 7):
horizontal.append(game[i][j])
vertical.append(game[j][i])
if check_ones(horizontal) > 1:
errors += "Multiple mines in Horizontal, @ Row [%d]\n" % (i + 1)
if check_ones(vertical) > 1:
errors += "Multiple mines in Vertical, @ Column [%d]\n" % (i + 1)
if errors != '':
print errors
check1 = False
# Lets do some diagonal checking now
check2 = diagonal_check(game)
if check1 and check2 :
print "Correct :)"
Now my questing is how can i go about making a solver for this puzzle, To be frank i solved this using absolute hit and trial. SO writing a brute-forcer for this puzzle would be quite foolish, please suggest some ideas to go about writing a solver.
Problem Description :-
Given a 8 x 8 , board with 64 boxes fill 8 of these boxes in such a way that no two filled boxes fall on the same straight
line - horizontally, vertically or diagonally!
Checker (source (http://www.go4expert.com/forums/showthread.php?t=27993)) :-
#!/bin/env/python
# Checker for a 8x8 bomb trap
# Correct Solution
game = [
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0]
]
def check_ones(array) :
ones = 0
for h in array:
if isinstance(h, list) :
ones = ones + check_ones(h)
elif h == 1:
ones = ones + 1
return ones
def diagonal_check(game):
errors = ''
for i in range(0, 7):
for j in range(0, 7):
if game[i][j] != 1:
continue
# diagonal 1
diag1 = []
h, k = i, j
# addition loop
while h <= 7 and h >= 0 and k <= 7 and k >= 0:
diag1.append(game[h][k])
h = h + 1
k = k + 1
# subtration loop
h, k = i-1, j-1
while h <= 7 and h >= 0 and k <= 7 and k >= 0:
diag1.append(game[h][k])
h = h - 1
k = k - 1
# diagonal 2
diag2 = []
# add k loop
h, k = i, j
while h <= 7 and h >= 0 and k <= 7 and k >= 0:
diag2.append(game[h][k])
h = h - 1
k = k + 1
# add h loop
h, k = i + 1, j - 1
while h <= 7 and h >= 0 and k <= 7 and k >= 0:
diag2.append(game[h][k])
h = h + 1
k = k - 1
# at this point we have 2 diagonal arrays and we can simply check
# for multiple 1's, if there are multiple 1's in any diag list
# it means we have 2 points in a diagonal i.e check failed
if check_ones(diag1) > 1:
errors += "Diagonal 1 check @ point [%d, %d] evaluated to FALSE\n" % (i+1, j+1)
if check_ones(diag2) > 1:
errors += "Diagonal 2 check @ point [%d, %d] evaluated to FALSE\n" % (i+1, j+1)
if errors != '':
print errors
return False
return True
check1 = True # Let's be +ve ;)
errors = ''
# let the game begin
if check_ones(game) != 8:
print "Please fill up exactly 8 places."
exit()
for i in range(0, 7):
horizontal = []
vertical = []
for j in range(0, 7):
horizontal.append(game[i][j])
vertical.append(game[j][i])
if check_ones(horizontal) > 1:
errors += "Multiple mines in Horizontal, @ Row [%d]\n" % (i + 1)
if check_ones(vertical) > 1:
errors += "Multiple mines in Vertical, @ Column [%d]\n" % (i + 1)
if errors != '':
print errors
check1 = False
# Lets do some diagonal checking now
check2 = diagonal_check(game)
if check1 and check2 :
print "Correct :)"
Now my questing is how can i go about making a solver for this puzzle, To be frank i solved this using absolute hit and trial. SO writing a brute-forcer for this puzzle would be quite foolish, please suggest some ideas to go about writing a solver.