Eu fiz uma espécie de jogo de quebra-cabeça em que o objetivo é se livrar de todos os azulejos brancos. Você pode tentar no final da pergunta.
Cada vez, o tabuleiro é gerado aleatoriamente com ladrilhos brancos em lugares aleatórios em uma grade 5 * 5. Você pode clicar em qualquer ladrilho nessa grade e ele alternará a cor e todos os ladrilhos que estiverem tocando nas laterais. Meu dilema é o fato de não saber se isso irá gerar um quadro impossível. Qual é a melhor maneira de verificar coisas assim?
function newgame() {
moves = 0;
document.getElementById("moves").innerHTML = "Moves: "+moves;
for (var i = 0; i < 25; i++) {
if (Math.random() >= 0.5) {
$(document.getElementsByClassName('block')[i]).toggleClass("b1 b2")
}
}
}
newgame();
function toggle(a,b) {
moves += 1;
document.getElementById("moves").innerHTML = "Moves: "+moves;
$(document.getElementsByClassName('block')[a+(b*5)]).toggleClass("b1 b2");
if (a<4) {$(document.getElementsByClassName('block')[(a+1)+(b*5)]).toggleClass("b1 b2")}
if (a>0) {$(document.getElementsByClassName('block')[(a-1)+(b*5)]).toggleClass("b1 b2")}
if (b<4) {$(document.getElementsByClassName('block')[a+((b+1)*5)]).toggleClass("b1 b2")}
if (b>0) {$(document.getElementsByClassName('block')[a+((b-1)*5)]).toggleClass("b1 b2")}
}body {
background-color: #000000;
}
.game {
float: left;
background-color: #000000;
width: 300px;
height: 300px;
overflow: hidden;
overflow-x: hidden;
user-select: none;
display: inline-block;
}
.container {
border-color: #ffffff;
border-width: 5px;
border-style: solid;
border-radius: 5px;
width: 600px;
height: 300px;
text-align: center;
}
.side {
float: left;
background-color: #000000;
width: 300px;
height: 300px;
overflow: hidden;
overflow-x: hidden;
user-select: none;
display: inline-block;
}
.block {
transition: background-color 0.2s;
float: left;
}
.b1:hover {
background-color: #444444;
cursor: pointer;
}
.b2:hover {
background-color: #bbbbbb;
cursor: pointer;
}
.row {
width: 300px;
overflow: auto;
overflow-x: hidden;
}
.b1 {
display: inline-block;
height: 50px;
width: 50px;
background-color: #000000;
border-color: #000000;
border-width: 5px;
border-style: solid;
}
.b2 {
display: inline-block;
height: 50px;
width: 50px;
background-color: #ffffff;
border-color: #000000;
border-width: 5px;
border-style: solid;
}
.title {
width: 200px;
height: 50px;
color: #ffffff;
font-size: 55px;
font-weight: bold;
font-family: Arial;
display: table-cell;
vertical-align: middle;
}
.button {
cursor: pointer;
width: 200px;
height: 50px;
background-color: #000000;
border-color: #ffffff;
border-style: solid;
border-width: 5px;
color: #ffffff;
font-size: 25px;
font-weight: bold;
font-family: Arial;
display: table-cell;
vertical-align: middle;
border-radius: 5px;
transition: background-color 0.3s, color 0.3s;
}
.button:hover {
background-color: #ffffff;
color: #000000;
}
.sidetable {
padding: 30px 0px;
height: 200px;
}
#moves {
width: 200px;
height: 50px;
color: #aaaaaa;
font-size: 30px;
font-weight: bold;
font-family: Arial;
display: table-cell;
vertical-align: middle;
}<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<center>
<div class="container">
<div class="game"><div class="row"><div onclick="toggle(0,0);" class="block b1"></div><div onclick="toggle(1,0);" class="block b1"></div><div onclick="toggle(2,0);" class="block b1"></div><div onclick="toggle(3,0);" class="block b1"></div><div onclick="toggle(4,0);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,1);" class="block b1"></div><div onclick="toggle(1,1);" class="block b1"></div><div onclick="toggle(2,1);" class="block b1"></div><div onclick="toggle(3,1);" class="block b1"></div><div onclick="toggle(4,1);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,2);" class="block b1"></div><div onclick="toggle(1,2);" class="block b1"></div><div onclick="toggle(2,2);" class="block b1"></div><div onclick="toggle(3,2);" class="block b1"></div><div onclick="toggle(4,2);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,3);" class="block b1"></div><div onclick="toggle(1,3);" class="block b1"></div><div onclick="toggle(2,3);" class="block b1"></div><div onclick="toggle(3,3);" class="block b1"></div><div onclick="toggle(4,3);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,4);" class="block b1"></div><div onclick="toggle(1,4);" class="block b1"></div><div onclick="toggle(2,4);" class="block b1"></div><div onclick="toggle(3,4);" class="block b1"></div><div onclick="toggle(4,4);" class="block b1"></div></div></div>
<div class="side">
<center class="sidetable">
<div class="title">Tiles</div>
<br>
<div class="button" onclick="newgame()">New Game</div>
<br><br>
<div id="moves">Moves: 0</div>
</center>
</div>
</div>
</center>
game-design
logic
puzzle
playtesting
Qwerty
fonte
fonte
Respostas:
Este é o tipo de jogo em que o mesmo movimento realizado duas vezes reverte o tabuleiro para o estado anterior. Portanto, para garantir que um tabuleiro seja solucionável, gere-o jogando ao contrário. Comece com um quadro (em branco) resolvido e inicie programaticamente "clicando" aleatoriamente um certo número de vezes ou até que o quadro tenha o número desejado de quadrados brancos. Uma solução é simplesmente executar os mesmos movimentos na ordem inversa. Outras soluções mais curtas podem existir, mas você tem a garantia de ter pelo menos uma.
Outra solução muito mais complexa é definir um algoritmo de solução que passe por todos os estados de jogo possíveis a partir da sua posição inicial, para tentar encontrar a solução. Isso levaria muito mais tempo para implementar e executar, mas permitiria que as placas fossem verdadeiramente geradas aleatoriamente. Não vou entrar em detalhes dessa solução, porque não é uma idéia tão boa.
fonte
Embora as respostas acima sejam inteligentes (e provavelmente como eu faria de qualquer maneira), esse jogo em particular é muito conhecido. Chama-se Lights Out e foi matematicamente resolvido. Existe uma solução se e somente se duas somas de vários elementos (fornecidas na página da wikipedia) adicionarem a zero mod 2 (ou seja, um número par). Em geral, um pouco de álgebra linear deve fornecer condições de solução semelhantes para jogos em qualquer tabuleiro.
fonte
Faça o contrário ao gerar seu quebra-cabeça.
Em vez de selecionar os ladrilhos aleatoriamente e transformá-los de branco em preto, comece com uma lousa em branco e selecione os ladrilhos, mas em vez de transformar esse ladrilho em preto, faça como se o usuário o selecionasse, resultando na inversão de todos os outros ladrilhos em torno dele.
Dessa forma, você terá a garantia de ter pelo menos uma solução: o usuário precisará desfazer o que o jogador "AI" fez para criar o nível.
fonte
Ed e Alexandre têm o direito disso.
Mas se você não quer saber se cada solução é possível, existem maneiras.
Há um número finito de quebra-cabeças possíveis
Clicar duas vezes no mesmo quadrado produz o mesmo resultado que não clicar nele, independentemente de quantos cliques foram feitos entre eles. Isso significa que toda solução pode ser descrita, atribuindo a cada quadrado um valor binário de 'clicado' ou 'não clicado'. Da mesma forma, cada quebra-cabeça pode ser descrito atribuindo a cada quadrado um valor binário de 'alternado' ou 'não alternado'. Isso significa que existem 2 ^ 25 quebra-cabeças possíveis e 2 ^ 25 soluções possíveis. Se você pode provar que cada solução resolve um quebra-cabeça único, deve haver uma solução para cada quebra-cabeça. Da mesma forma, se você encontrar duas soluções que resolvem o mesmo quebra-cabeça, não poderá haver uma solução para cada quebra-cabeça.
Além disso, 2 ^ 25 é 33.554.432. Isso é bastante, mas não é um número incontrolável. Um bom algoritmo e um computador decente provavelmente poderiam ter uma força bruta em algumas horas, especialmente quando você considera que metade dos quebra-cabeças é inversa da outra metade.
fonte
Resposta generalizada:
fonte
Outros já mencionaram maneiras de descobrir se o quebra-cabeça gerado aleatoriamente é solucionável. a pergunta que você também deve estar perguntando é se você realmente deseja quebra-cabeças gerados aleatoriamente.
Todos os quebra-cabeças gerados aleatoriamente têm a mesma falha principal: a dificuldade deles é praticamente imprevisível. Os possíveis quebra-cabeças que você pode encontrar podem variar de já resolvidos, a triviais (a solução é óbvia) a difíceis (a solução não é óbvia) a impossíveis (o quebra-cabeça não é solucionável). Como a dificuldade é imprevisível, cria uma experiência insatisfatória para o jogador, especialmente se ele fizer vários quebra-cabeças seguidos. É altamente improvável que eles obtenham uma curva de dificuldade suave, o que pode deixá-los entediados ou frustrados, dependendo dos quebra-cabeças que recebem.
Outro problema da geração aleatória é que o tempo que leva para inicializar o quebra-cabeça é imprevisível. De um modo geral, você terá um quebra-cabeça solucionável (quase) imediatamente, mas com um pouco de azar, seus quebra-cabeças gerados aleatoriamente podem acabar em uma série de quebra-cabeças não resolvíveis.
Uma maneira de resolver ambos é disponibilizar vetores predefinidos de todos os quebra-cabeças solucionáveis, organizados em grupos de dificuldade e, em seguida, selecionar um quebra-cabeça aleatório dos quebra-cabeças solucionáveis com base na dificuldade. Dessa forma, você estará certo de que todo quebra-cabeça é solucionável, que a dificuldade é previsível e que a geração será feita em tempo constante.
fonte