the principle is simple, for each empty cell, you must add all the adjacent empty cells.
it is also necessary to collect the number of adjacent mines of each cell
a) list the 8 adjacent cells, except for the cells placed at the edge
this is the prxElm() function in my code
b) count the mines present around a cell -> prxMne()
starting from the first cell
1- we count (a) nearby mines
2- it becomes the first element of a stack of cells to be mapped
3- if its number of nearby mines is zero, repeat this operation for all adjacent cells
the particularity of this algorithm is to use only one stack to accumulate the coordinates to be mapped.
it places the elements with adjacent mines at the top of the stack, and those with none at the end of the stack.
as there can be several cells without adjacent mines, we keep an indexiExp of the last empty cell processed.
of course when you add a cell with mines nearby at the start of the stack, this index is shifted.
the algorithm also take care not to add duplicate the same cell by checking before if this cell is not in the stack.
see .filter(x=>!explor.some(e=>e.p===x.p))
this ends when the exploration index iExp reaches the end of the stack.
here is the whole code, it is not completely finalized, but the essentials are there.
const
MinesCount = 17 // adjusted values to fit this snippet display area
, gridSz = { r:7, c:20 } // grid rows x cols
, gridMx = gridSz.r * gridSz.c
, proxim = [ {v:-1,h:-1}, {v:-1,h:0}, {v:-1,h:+1}, {v:0,h:-1}, {v:0,h:+1}, {v:+1,h:-1}, {v:+1,h:0}, {v:+1,h:+1} ]
, prxElm = (r,c) => proxim.reduce((a,{v,h})=>
{
let rv = r+v, ch = c+h;
if (rv>=0 && ch>=0 && rv<gridSz.r && ch<gridSz.c) a.push({p:((rv * gridSz.c) + ch), r:rv, c:ch} )
return a
},[])
, GenNbX = (nb,vMax) => [null].reduce(arr=>
{
while (arr.length < nb)
{
let numGen = Math.floor(Math.random() * vMax)
if (!arr.includes(numGen)) arr.push(numGen);
}
return arr //.sort((a,b)=>a-b)
},[])
, minesP = GenNbX( MinesCount, gridMx )
, prxMne = (r,c) => prxElm(r,c).reduce((a,{p})=>minesP.includes(p)?++a:a,0) // count mines arroub=nd
, td2rcp = td =>
{
let r = td.closest('tr').rowIndex -1 // -1 for thead count of rows
, c = td.cellIndex
, p = (r * gridSz.c) +c
return {r,c,p}
}
, p2rc = p =>({r: Math.floor(p / gridSz.c), c: (p % gridSz.c)})
, { timE, cFlags, minesArea } = drawTable('mines-area', gridSz, MinesCount )
;
const chrono = (function( timeElm )
{
const
one_Sec = 1000
, one_Min = one_Sec * 60
, twoDgts = t => (t<10) ? `0${t}` : t.toString(10)
, chronos =
{ timZero : null
, timDisp : timeElm
, timIntv : null
, running : false
}
, obj =
{ start()
{
if (chronos.running) return
chronos.timDisp.textContent="00:00"
chronos.running = true
chronos.timZero = new Date().getTime()
chronos.timIntv = setInterval(() =>
{
let tim = (new Date().getTime()) - chronos.timZero
chronos.timDisp.textContent = `${Math.floor(tim/one_Min)}:${twoDgts(Math.floor((tim % one_Min)/one_Sec))}`
}
, 250);
}
, stop()
{
if (!chronos.running) return
chronos.running = false
clearInterval( chronos.timIntv )
}
}
return obj
}(timE))
function drawTable(tName, gSz, mines )
{
let table = document.getElementById(tName)
// table.innerHTML = '' // eraze table
let tHead = table.createTHead()
, tBody = table.createTBody()
, xRow = tHead.insertRow()
, timE = xRow.insertCell()
, cFlags = xRow.insertCell()
;
timE.setAttribute('colspan', gSz.c -4)
timE.className="time"
timE.textContent="0:00"
cFlags.setAttribute('colspan', 4)
cFlags.className="flag"
cFlags.textContent=" 0/" + mines
for (let r=gSz.r;r--;)
{
xRow = tBody.insertRow()
for(let c = gSz.c;c--;) xRow.insertCell()
}
return { timE, cFlags, minesArea: tBody }
}
minesArea.onclick = ({target}) =>
{
if (!target.matches('td')) return
if (target.hasAttribute('class')) return // already done
chrono.start()
let {r,c,p} = td2rcp(target)
if (minesP.includes(p)) // you are dead!
{
chrono.stop()
minesArea.className="Boom"
minesP.forEach(p=> // show mines
{
let {r,c} = p2rc(p)
let td = minesArea.rows[r].cells[c]
if (!td.hasAttribute('class')) td.className="mineOff"
})
minesArea.rows[r].cells[c].className="mineBoom" // this one is for you
minesArea.querySelectorAll('td:not([class]), td.flag') // jusr disable click
.forEach(td=>td.classList.add('off')) // and cursor
}
else
{
let explor = [ {p, r, c, m:prxMne(r,c) } ]
, iExp = 0
;
while (iExp < explor.length && explor[iExp].m === 0) // Open mine-free area
{
prxElm(explor[iExp].r,explor[iExp].c) // look around
.filter(x=>!explor.some(e=>e.p===x.p)) // if not already in
.forEach(x=>
{
M = prxMne(x.r,x.c)
if (M>0 ) { explor.unshift( { p:x.p, r:x.r, c:x.c, m:M} ); iExp++ }
else explor.push( { p:x.p, r:x.r, c:x.c, m:M} ) // mine-free space
})
iExp++
}
explor.forEach(({r,c,m})=>minesArea.rows[r].cells[c].className="m"+m )
}
if (checkEnd()) // some kind of victory!?
{
chrono.stop()
minesArea.querySelectorAll('td.flag').forEach(td=>td.classList.add('off'))
minesArea.className="win"
}
}
minesArea.oncontextmenu = e => // Yes, there is a right click for flag mines
{
if (!e.target.matches('td')) return
e.preventDefault()
let {r,c,p} = td2rcp( e.target)
, cell_rc = minesArea.rows[r].cells[c]
;
if (!cell_rc.hasAttribute('class')) cell_rc.className="flag"
else if (cell_rc.className === 'flag') cell_rc.removeAttribute('class')
let nbFlags = minesArea.querySelectorAll('td.flag').length
cFlags.textContent = ` ${nbFlags} / ${MinesCount}`
}
function checkEnd()
{ // what about us ?
let count = 0
, reject = 0
, tdNotSeen = minesArea.querySelectorAll('td:not([class])')
, flagPos = minesArea.querySelectorAll('td.flag')
;
cFlags.textContent = ` ${flagPos.length} / ${MinesCount}`
if (tdNotSeen.length > MinesCount ) return false
flagPos.forEach(td=>
{
let {r,c,p} = td2rcp(td)
if (minesP.includes(p)) count++ // correct place
else reject++
})
tdNotSeen.forEach(td=>
{
let {r,c,p} = td2rcp(td)
if (minesP.includes(p)) count++
else reject++ // no mines there
})
if (count != MinesCount || reject != 0 ) return false
tdNotSeen.forEach(td=>
{
let {r,c,p} = td2rcp(td)
minesArea.rows[r].cells[c].className="mineOff"
})
cFlags.textContent = ` ${MinesCount} / ${MinesCount}`
return true
}body { background-color: #383947; } /* dark mode ? ;-) */
table {
border-collapse : collapse;
margin : 1em auto;
--szRC : 18px;
font-family : Arial, Helvetica, sans-serif;
}
table td {
border : 1px solid #1a1a1a80;
text-align : center;
}
table thead {
font-size : .8em;
background-color : #c3c5db;
}
table tbody {
background-color : #a39999;
cursor : cell;
}
table tbody td {
width : var(--szRC);
height : var(--szRC);
overflow : hidden;
}
.m0, .m1, .m2, .m3, .m4, .m5, .m6, .m7, .m8 { background-color: whitesmoke; font-size: 12px; font-weight: bold; cursor: default; }
.m1::after { content: '1'; color: #0000ff; }
.m2::after { content: '2'; color: #008000; }
.m3::after { content: '3'; color: #ff0000; }
.m4::after { content: '4'; color: #000080; }
.m5::after { content: '5'; color: #800000; }
.m6::after { content: '6'; color: #008080; }
.m7::after { content: '7'; color: #000000; }
.m8::after { content: '8'; color: #808080; }
.off { cursor: default; }
.Boom { background-color: yellow; cursor: default; }
.mineOff { cursor: default; padding: 0; }
.flag { background-color: lightgray; padding: 0; }
.mineBoom { color: crimson; padding: 0; }
.mineOff::after,
.mineBoom::after { content: '\2738'; }
.flag::before { content: '\2691'; color: crimson; }
.time::before { content: 'Time elapsed : '; color: darkblue; }
.win td { border-color: gold;}<table id="mines-area"></table>I don’t think a recursive method is suitable for this kind of problem.
It requires having a complex strategy for exploring empty spaces.
For example, spiraling around the starting point.
But this strategy comes up against the problem of the island hindering this progress, and which requires, once crossed, to carry out a new spiral advance to recover the points hidden during the previous spiral, but having to avoid the points already explored during the previous spiral.
You can also move forward by sectors from an initial point, but you will still encounter the same problem of the islet and its backtracking, which also multiply here with each roughness on the explored shores.
This requires complex calculations that are difficult to master and debug, not to mention the fact that recursive methods intensively use call stacks which it adds up for each new branch.
(Without neglecting the risk of going crazy, by striving to develop its recursive algorithms.)
The larger the grid and the more its recursive lists will conflict with each other, and more the computationnal time will be affected.
Of course there are already winning heuristics on this type of strategy, they are of a very high level, and we are here just on a minesweeper game where hundreds of lines of code have nothing to do.
My method only uses a single stack, its algorithm is easy to understand and requires a few lines of code.
What more ?