Back Tracking is a brute force approach that follows DFS

Opposing, “Branch and Bound” is another brute force approach that follows BFS

Here is an example: There are two boys (B1, B2) and one girl (G1) and three chairs

Let’s list all the possible combinations:

%%{init: {'theme':'darkmode'}}%%
graph LR
%% Colors %%
classDef purple fill:#8e7cc3,stroke:#000,stroke-width:2px,color:#fff
classDef blue fill:#2374f7,stroke:#000,stroke-width:2px,color:#fff
classDef pink fill:#eb3dd6,stroke:#000,stroke-width:2px,color:#fff
classDef orange fill:#fc822b,stroke:#000,stroke-width:2px,color:#fff
classDef red fill:#f44336,stroke:#000,stroke-width:2px,color:#fff
classDef green fill:#16b522,stroke:#000,stroke-width:2px,color:#fff
	B0(.) --1--> temp1(B1):::blue --2--> temp3(B2):::orange --3--> temp4(G1):::red
  temp1(B1):::blue --4--> temp6(G1):::red --5--> temp7(B2):::orange 
	B0(.) --6--> temp8(B2) --7--> temp9(B1):::blue --8--> temp10(G1):::red
  temp8(B2):::orange --9--> temp11(G1):::red--10--> temp12(B1):::blue
  B0(.) --11--> tem1(G1):::red --12--> tem3(B1):::blue --13--> tem4(B2):::orange 
  tem1(G1) --14--> tem6(B2):::orange--15--> tep7(B1):::blue

%%{init: {'theme':'darkmode'}}%%
graph LR
%% Colors %%
classDef purple fill:#8e7cc3,stroke:#000,stroke-width:2px,color:#fff
classDef blue fill:#2374f7,stroke:#000,stroke-width:2px,color:#fff
classDef pink fill:#eb3dd6,stroke:#000,stroke-width:2px,color:#fff
classDef orange fill:#fc822b,stroke:#000,stroke-width:2px,color:#fff
classDef red fill:#f44336,stroke:#000,stroke-width:2px,color:#fff
classDef green fill:#16b522,stroke:#000,stroke-width:2px,color:#fff
	B0(.) --1--> temp1(B1):::blue --4--> temp3(B2):::orange --10--> temp4(G1):::red 
  temp1(B1):::blue --5--> temp6(G1):::red --11--> temp7(B2):::orange 
	B0(.) --2--> temp8(B2) --6--> temp9(B1):::blue --12--> temp10(G1):::red 
  temp8(B2):::orange --7--> temp11(G1):::red--13--> temp12(B1):::blue
  B0(.) --3--> tem1(G1):::red --8--> tem3(B1):::blue --14--> tem4(B2):::orange 
  tem1(G1):::red --9--> tem6(B2):::orange--15--> tep7(B1):::blue

There are six final combinations, where the index on each edge indicates the order of traversal

Now let’s add a constraint, the girl shouldn’t sit in the middle of the boys:

%%{init: {'theme':'darkmode'}}%%

graph LR
	%% Colors %%
	classDef red fill:#e63946,stroke:#000,stroke-width:2px,color:#fff
	B0(.) --1--> temp1(B1) --2--> temp3(B2) --3--> temp4(G1) 
  temp1(B1) --4--> temp6(G1):::red
	B0(.) --5--> temp8(B2) --6--> temp9(B1) --7--> temp10(G1) 
  temp8(B2) --8--> temp11(G1):::red
  B0(.) --9--> tem1(G1) --10--> tem3(B1) --11--> tem4(B2) 
  tem1(G1) --12--> tem6(B2)--13--> tep7(B1)

%%{init: {'theme':'darkmode'}}%%

graph LR
	%% Colors %%
	classDef red fill:#e63946,stroke:#000,stroke-width:2px,color:#fff
	B0(.) --1--> temp1(B1) --4--> temp3(B2) --10--> temp4(G1) 
  temp1(B1) --5--> temp6(G1):::red
	B0(.) --2--> temp8(B2) --6--> temp9(B1) --11--> temp10(G1) 
  temp8(B2) --7--> temp11(G1):::red
  B0(.) --3--> tem1(G1) --8--> tem3(B1) --12--> tem4(B2) 
  tem1(G1) --9--> tem6(B2)--13--> tep7(B1)

leet code (couldn’t solve):

• https://leetcode.com/problems/word-search/