The Eight Saints Problem : Explanation

The Eight Saints Problem

The eight saints problem is a classic combinatorial problem where eight christian saints are to be placed on a 8 by 8 chess board so that they do not f**k each other. This problem has never lost it''s relevance or urgency ever since the foundation of Christianity. Here are some fact which will enable us to understand the utter necessity of this solution:-

 

 

Source http://www.jesusneverexisted.com/1000years.htm

For centuries the Curia has worked hard to keep the saints in presentable conditions and has always been overworked. The recent case where Pedophiles from round the world were gathered in Rome is a case in point.

The Solution

The solution is developed using the technique of backtracking. Backtracking involves systematically searching the problem space till a solution is found. We start at one step of the solution. Then advance to the next step. If at some step advancing becomes impossible we step back and create a new configuration and then move forwards. 

The saints f**k each other in the same row , same column or on the same diagonals. This means that if two saints are at x1,y1 and x2,y2 positions then indecency occurs if x1=x2, y1=y2, x1+y1=x2+y2 or x1-y1=x2-y2.

Operating the solution

Press the 

make the solution visible.

Next press the

Button. This will create the required grid.

Now, press the start button to sit back and view the different solutions as they flash by.

To manually view the solutions:- Press the pause button and then press the forward or back buttons.

Here is the complete code for the application.

<table width="100%">
<tr><td align="center"><input type="button" value="View The Eight Saints Problem" id="bttnqueensshow" onclick="queensstart()"/></td></tr>
</table>
<div id="queensmain"style="left:0px;height:800px;top:0px;width:900px;visibility:hidden;z-index=50;background-color:darkgreen;opacity:0.90">




<script type="text/javascript">
var locations;
var picarrays;

var stories;
var storyno=-1;

setInterval("showstory()",5000);

function showstory()
{
if(storyno==-1)
{
stories=Array("This is an implementation of the classic","Combinatorial problem called","The eight  saints problem","Where 8 saints are to be placed","On a 8 by 8 Chess Board so that they","Do not <i>Fuck</i> each other.","");
storyno=0;
}
var x=document.getElementById("storydiv");
x.innerHTML+="<br/><b>" + stories[storyno] + "</b>";
storyno++;
if(storyno>=stories.length)
{
x.innerHTML="";
storyno=0;
}
}














function nextnumber()
{
return (Math.round(Math.random()*4));
}


function nextSolution()
{
var i;
var x;
var d=document.getElementById("griddiv");
var y,queenno;
queenno=1;
d.innerHTML="";
for(y=0;y<=7;y++)
for(x=0;x<=7;x++)
d.innerHTML+=getQueen(queenno++,x,y);
for(i=0;i<=7;i++)
{
var x=document.getElementById("p" + i +( locations[currentsolution][i]-1));
x.src=picarrays[nextnumber()];
x.style.zIndex="5";
}
document.getElementById("show").innerHTML='Showing Solution no = ' + (currentsolution + 1);
currentsolution = (currentsolution + 1) % solutionno;
}


function previoussolution()
{
currentsolution=currentsolution-2;
if(currentsolution<0)
currentsolution=0;
nextSolution();
}

function createGrid()
{



picarrays=Array("https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjFOG2aEi6cFs2EtZwe1iHLOuLZJYY6LHZW6JXZY3tySRKrjYTKzJJVY2kMa6f240boBJ0LBUrzbacNNyUDXtihtubRslOk-eNL8cBPvI5mO4jHc9Nr9dDInaiWprgorzEWjyloV1PREw91/s320/q0.png","https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEirKm3lUGBoUGhYMFMYIPIkutju9nMWPubTsHjtQAWvlkJITbOQ_6rmZSGvZvo071U8G_5cZuElVd0Nhm26t3JgZk1ls75WotKFv4da8nmoLII9KzTBAmh5fVWZpPo9Hh5q_QLhdCBuIY8m/s1600/q1.png","https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhTYOhm4KZpXaeAjjhI9EotTXGS8TJb6jGBUUgo7YQhyucC9qovjKUBjQTXqDxM7Nm2IAVxShft-cBts0_GFdVcCnHkeEizQ063T1zWMKi5BVnv4-_0F6pCPNAsOlLv2eW9D9PcbRFTZ9Dx/s1600/q2.png","https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjZadHeWdGy7ISgYfUz1p_XskZcu_HnfVMoOON4jM_jcHo7kFMDiNDF0trYcwLoiJl8ji2PdU1kzmg7qkckI37-JFopHk4rxX37YVEyVd1PfNpfgfsJHNRpna9IhFyGUTZcKiqNYdrHoGaW/s1600/q3.png","https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhYn0UwKrV33gHFtqbuothHdgzXIlF0SLeXWmkOWljOumXw2A95J3ymNthmCOQhfB5FhWMUKcpUuXgv2r1JZVWydnomlqJCvUdniB0hdBTiQEl_lmRWYW2gHjvpA3Y0rZoXDE1jpZfJCIdH/s1600/q4.png");
var d=document.getElementById("griddiv");
d.innerHTML="";
var x,y,queenno;
queenno=1;
var d=document.getElementById("griddiv");
var x,y,queenno;
queenno=1;
for(y=0;y<=7;y++)
for(x=0;x<=7;x++)
d.innerHTML+=getQueen(queenno++,x,y);
locations=new Array(100);

for(x=0;x<=99;x++)
locations[x]=new Array(8);
positions=new Array(8);
solvequeen(1);
document.getElementById("show").innerHTML='No of Solutions found = ' + solutionno;
}
var solutionno=0;
var currentsolution=0;
function attack(qno,x,y)
{
var i;
var px,py;
qno--;
for(i=0;i<=qno-1;i++)
{
px=i+1;
py=positions[i];
if(x==px || y==py)
return 1;

if((x+y) ==(px+py))
return 1;

if((x-y) ==(px-py))
return 1;
}
return 0;
}



function getQueen(queenno,x,y)
{
if((x+y) % 2==0)
return "<img src=\"https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiX3Zzbc-5CNPEDmTrWI1d3Swkb__TjXkefEw5FZ-Yco69sRhQYI-a5a84a1UPGtkvxUhyphenhyphenEUNPT5wpcRS-FrJsjB8gc69k_1XyDKp2WOPTBLcYtboJQI8agE0QVqS45Rk9-az9hd4fVfWb1/s320/0.png\" style=\"position:absolute;width:12%;height:12%;border-color:blue;border-width:5py;left:" + (12*x + 2) + "%;top:" + (12*y + 2) + "%;\" alt='' title='' id='p"  + x + y +  "'/>";
else
return "<img src=\"https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjYTg9JgD0YGgo9iYRn-lebV5R3ULEpA68wcwmHkzHkQbRM1WnIPqsinwkS1TPXYDyyr3X9BH_bQNxHII-AZFGPaV2wCE1qoDSHvx0chlm6_8LCJxo13-kfbRo-ywBNENXspYb9wywBY9Nr/s320/1.png\" style=\"position:absolute;width:12%;height:12%;border-color:blue;border-width:5py;left:" + (12*x + 2) + "%;top:" + (12*y + 2) + "%;\" alt='' title='' id='p"  + x + y +  "'/>";
}
var positions;







function solvequeen(qno)
{
//alert(qno);
var col;
var i;
if(qno>8)
return;
for(col=1;col<=8;col++)
{
//alert(attack(qno,qno,col));
if(attack(qno,qno,col)==1)
continue;
positions[qno-1]=col;
if(qno==8)
{
for(i=0;i<=7;i++)
{
//alert(positions[i]);
locations[solutionno][i]=positions[i];
}
solutionno++;
}
else
solvequeen(qno+1);
}
}
var solutionloop;
</script>
<input type="button" value="Create"onclick="createGrid()"  style="position:absolute;width:16%;height:10%;font-size:25;left:10%;top:10%;background-color:darkgreen" />
<input type="button" value="Stop" onclick="clearInterval(solutionloop);currentsolution=0;" style="position:absolute;width:16%;height:10%;font-size:25;left:74.3%;top:10%;background-color:darkgreen" />
<input type="button" value="Pause" onclick="clearInterval(solutionloop)"; style="position:absolute;width:16%;height:10%;font-size:25;left:26%;top:10%;background-color:darkgreen" />
<input type="button" value="Start" onclick="solutionloop = window.setInterval('nextSolution()',5000);" style="position:absolute;width:16%;height:10%;font-size:25;left:59%;top:10%;background-color:darkgreen" />
<div id="griddiv" style="position:absolute;width:80%;height:80%;left:11%;top:20%;background-color:darkgreen;border-color:yellow;border-width:25py;border-style:ridge;"></div>
<div id="storydiv" style="position:absolute;width:80%;height:80%;left:10%;top:10%;background-color:gray;opacity:0.65;font-size:40px;text-align:center;color:RED;visibility:hidden"></div>

<img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjM2lFiPkF3WhwWeipzAF80NyCBZcAW_VjZQZiPvJE4TQd1hFokVP031F6VcPmR4Kz4LRYAlqj-Koqd7ZqODFGH_FUtFxRuvfXkTmh9AfZH1yBnZhnLCk4MQTLck20mjo-BNyHk9Chsp-lI/s320/next.jpg" onclick="nextSolution()" style="position:absolute;width:8%;height:12%;left:92.5%;top:40%;"/>
<img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjQg2Zck18_EfVEfB9yqYBNghXh3xdvCo9hTKBCvX-vA8Ii4va_JnLTcDH6yM_R-V4eHNb9ii45gtNZVyZp3ztBi5xAdGfWxzUVUjwZlBtk973Yj2IvP8xxg3NenmZjjCXx5hgiRoFOpGMV/s320/previous.jpg" onclick="previoussolution()" style="position:absolute;width:8%;height:12%;left:2%;top:40%"/>
<div id="show" align="center" style="position:absolute;width:16.7%;height:10%;left:42.3%;font-size:20;top:10%;background-color:gray">No Solution Found</div>

























</div>
<script type="text/javascript">
function queensstart()
{
var x=document.getElementById("queensmain");
var y=document.getElementById("bttnqueensshow");
if(y.value=="View The Eight Saints Problem")
{
x.style.visibility="visible";
y.value="Close The Eight Saints Problem";
}
else
{
x.style.visibility="hidden";
y.value="View The Eight Saints Problem";
}
}
</script>