磁铁拼图|回溯-9

5211

拼图游戏磁铁涉及将一组多米诺骨牌形状的磁铁（或驻极体或其他极化物体）放置在电路板上插槽的子集中，以满足一组约束条件。例如，左边的拼图有右边显示的解决方案： 图片[1]-磁铁拼图|回溯-9-yiteyi-C++库 每个插槽包含一个空白条目（用“x”表示），或一个带有正负端的“磁铁”。左侧和顶部的数字显示特定行或列中“+”正方形的数量。右侧和底部的符号显示特定行或列中的“-”符号数。一端或两端没有数字的行和列对于“+”或“-”符号的数量不受限制，这取决于不存在哪个数字。除了满足这些数值约束外，谜题解决方案还必须满足以下约束：两个正交接触的正方形不能有相同的符号（对角连接的正方形不受约束）。

null

我们为您提供了top[]、bottom[]、left[]、right[]数组，它们分别表示沿顶部（+）、底部（-）、左侧（+）和右侧（-）边的+或–计数。值-1表示任意数量的+和–符号。同样给定的矩阵规则[][]包含任意一个T、B、L或R字符。对于电路板中的垂直插槽，T表示其顶端，B表示其底端。对于电路板中的水平插槽，L表示左端，R表示右端。

例如： 

Input : M = 5, N = 6
        top[] = { 1, -1, -1, 2, 1, -1 }
        bottom[] = { 2, -1, -1, 2, -1, 3 }
        left[] = { 2, 3, -1, -1, -1 }
        right[] = { -1, -1, -1, 1, -1 }
        rules[][] = { { L, R, L, R, T, T },
                      { L, R, L, R, B, B },
                      { T, T, T, T, L, R },
                      { B, B, B, B, T, T },
                      { L, R, L, R, B, B }};
Output : + - + - X - 
         - + - + X + 
         X X + - + - 
         X X - + X + 
         - + X X X - 

Input : M = 4, N = 3
        top[] = { 2, -1, -1 }
        bottom[] = { -1, -1, 2 }
        left[] = { -1, -1, 2, -1 }
        right[] = { 0, -1, -1, -1 }
        rules[][] = { { T, T, T },
                      { B, B, B },
                      { T, L, R },
                      { B, L, R } };
Output : + X +
         – X –
        + – +
        – + –

我们可以使用 回溯 .

# Write Python3 code here
M = 5
N = 6
top = [ 1 , - 1 , - 1 , 2 , 1 , - 1 ]
bottom = [ 2 , - 1 , - 1 , 2 , - 1 , 3 ]
left = [ 2 , 3 , - 1 , - 1 , - 1 ]
right = [ - 1 , - 1 , - 1 , 1 , - 1 ]
rules = [[ "L" , "R" , "L" , "R" , "T" , "T" ],
[ "L" , "R" , "L" , "R" , "B" , "B" ],
[ "T" , "T" , "T" , "T" , "L" , "R" ],
[ "B" , "B" , "B" , "B" , "T" , "T" ],
[ "L" , "R" , "L" , "R" , "B" , "B" ]];
def canPutPatternHorizontally(rules,i,j,pat):
if j - 1 > = 0 and rules[i][j - 1 ] = = pat[ 0 ]:
return False
elif i - 1 > = 0 and rules[i - 1 ][j] = = pat[ 0 ]:
return False
elif i - 1 > = 0 and rules[i - 1 ][j + 1 ] = = pat[ 1 ]:
return False
elif j + 2 < len (rules[ 0 ]) and rules[i][j + 2 ] = = pat[ 1 ]:
return False
return True
def canPutPatternVertically(rules,i,j,pat):
if j - 1 > = 0 and rules[i][j - 1 ] = = pat[ 0 ]:
return False
elif i - 1 > = 0 and rules[i - 1 ][j] = = pat[ 0 ]:
return False
elif j + 1 < len (rules[ 0 ]) and rules[i][j + 1 ] = = pat[ 0 ]:
return False
return True
def doTheStuff(rules,i,j):
if rules[i][j] = = "L" or rules[i][j] = = "R" :
#        option 1 +-
if canPutPatternHorizontally(rules,i,j, "+-" ):
rules[i][j] = "+"
rules[i][j + 1 ] = "-"
solveMagnets(rules,i,j)
#        option 2 -+
#        option 3 xx
def checkConstraints(rules):
pCountH = [ 0 for i in range ( len (rules))]
nCountH = [ 0 for i in range ( len (rules))]
for row in range ( len (rules)):
for col in range ( len (rules[ 0 ])):
ch = rules[row][col]
if ch = = "+" :
pCountH[row] + = 1
elif ch = = "-" :
nCountH[row] + = 1
pCountV = [ 0 for i in range ( len (rules[ 0 ]))]
nCountV = [ 0 for i in range ( len (rules[ 0 ]))]
for col in range ( len (rules[ 0 ])):
for row in range ( len (rules)):
ch = rules[row][col]
if ch = = "+" :
pCountV[col] + = 1
elif ch = = "-" :
nCountV[col] + = 1
for row in range ( len (rules)):
if left[row] ! = - 1 :
if pCountH[row] ! = left[row]:
return False
if right[row] ! = - 1 :
if nCountH[row] ! = right[row]:
return False
for col in range ( len (rules[ 0 ])):
if top[col] ! = - 1 :
if pCountV[col] ! = top[col]:
return False
if bottom[col] ! = - 1 :
if nCountV[col] ! = bottom[col]:
return False
#
#  if (top[col] != -1 and pCountH[col] != top[col]) or (bottom[col] != -1 and nCountH[col] != bottom[col]) :
#      return False
return True
def solveMagnets(rules,i,j):
if i = = len (rules) and j = = 0 :
# check the constraint before printing
if checkConstraints(rules):
print (rules)
elif j > = len (rules[ 0 ]):
solveMagnets(rules,i + 1 , 0 )
# normal cases
else :
if rules[i][j] = = "L" :
#  option 1 +-
if canPutPatternHorizontally(rules,i,j, "+-" ):
rules[i][j] = "+"
rules[i][j + 1 ] = "-"
solveMagnets(rules,i,j + 2 )
rules[i][j] = "L"
rules[i][j + 1 ] = "R"
# option 2 -+
if canPutPatternHorizontally(rules,i,j, "-+" ):
rules[i][j] = "-"
rules[i][j + 1 ] = "+"
solveMagnets(rules,i,j + 2 )
rules[i][j] = "L"
rules[i][j + 1 ] = "R"
# option 3 xx
if True or canPutPatternHorizontally(rules,i,j, "xx" ):
rules[i][j] = "x"
rules[i][j + 1 ] = "x"
solveMagnets(rules,i,j + 2 )
rules[i][j] = "L"
rules[i][j + 1 ] = "R"
#        vertical check
elif rules[i][j] = = "T" :
#        option 1 +-
if canPutPatternVertically(rules,i,j, "+-" ):
rules[i][j] = "+"
rules[i + 1 ][j] = "-"
solveMagnets(rules,i,j + 1 )
rules[i][j] = "T"
rules[i + 1 ][j] = "B"
#        option 2 -+
if canPutPatternVertically(rules,i,j, "-+" ):
rules[i][j] = "-"
rules[i + 1 ][j] = "+"
solveMagnets(rules,i,j + 1 )
rules[i][j] = "T"
rules[i + 1 ][j] = "B"
#        option 3 xx
if True or canPutPatternVertically(rules,i,j, "xx" ):
rules[i][j] = "x"
rules[i + 1 ][j] = "x"
solveMagnets(rules,i,j + 1 )
rules[i][j] = "T"
rules[i + 1 ][j] = "B"
else :
solveMagnets(rules,i,j + 1 )
# Driver code
solveMagnets(rules, 0 , 0 ) 





         








     资料来源：       https://people.eecs.berkeley.edu/~hilfingr/编程竞赛/f2012竞赛。pdf   


  本文由     Anuj Chauhan（anuj0503）    .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用     贡献极客。组织    或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 


  如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。 


 


                    

        
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
技术文章
    

    
喜欢就支持一下吧
点赞11
        分享

        

            

                
                
CPPKU的头像-yiteyi-C++库

                
            

            
VS调试报错：f:\dd\vctools\vc7libs\ship\atlmfc\src\occcont.cpp line:925的原因-yiteyi-C++库
VS调试报错：f:\dd\vctools\vc7libs\ship\atlmfc\src\occcont.cpp line:925的原因
VS调试报错：f:\dd\vctools\vc7libs\ship\atlmfc\src\occcont.cpp li...
8年前 2.6W+
关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库
关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案
关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案
7年前 9287
Easylogging++入门教程（三）Easylogging++ 配置-yiteyi-C++库
Easylogging++入门教程（三）Easylogging++ 配置
Easylogging++入门教程（三）Easylogging++ 配置
9年前 9058
常见的小波基函数有哪些？如何选择合适的小波基函数？-yiteyi-C++库
常见的小波基函数有哪些？如何选择合适的小波基函数？
常见的小波基函数有哪些？如何选择合适的小波基函数？
8年前 8484
TiXmlDocument变量LoadFile()加载XML文档失败的原因有哪些？-yiteyi-C++库
TiXmlDocument变量LoadFile()加载XML文档失败的原因有哪些？
TiXmlDocument变量LoadFile()加载XML文档失败的原因有哪些？
10年前 6676
Easylogging++入门教程（一）Easylogging++日志库简介-yiteyi-C++库
Easylogging++入门教程（一）Easylogging++日志库简介
Easylogging++入门教程（一）Easylogging++日志库简介
9年前 6608

        

    
    

        
    



            

                
相关推荐

            
ISRO | ISRO CS 2017 |问题6-yiteyi-C++库
ISRO | ISRO CS 2017 |问题6
ISRO | ISRO CS 2017 |问题6
3年前 480
比特屏蔽和动态编程|集1（计算方法，为每个人分配唯一的上限）-yiteyi-C++库
比特屏蔽和动态编程|集1（计算方法，为每个人分配唯一的上限）
比特屏蔽和动态编程|集1（计算方法，为每个人分配唯一的上限）
3年前 293
SAP位置编码问题-yiteyi-C++库
SAP位置编码问题
SAP位置编码问题
3年前 291
2018年NSIT德里协会黑客团队Geeksforgeks-yiteyi-C++库
2018年NSIT德里协会黑客团队Geeksforgeks
2018年NSIT德里协会黑客团队Geeksforgeks
3年前 283
STD:：C++中的NExtx置换和Pype置换-yiteyi-C++库
STD:：C++中的NExtx置换和Pype置换
STD:：C++中的NExtx置换和Pype置换
3年前 282
抗锯齿线|吴小林算法-yiteyi-C++库
抗锯齿线|吴小林算法
抗锯齿线|吴小林算法
3年前 172