디지털 지능 생성기 구축
13086 단어 programmingjavascript
책략
고전적인 솔로 게임에서 목표는 숫자로 9x9 격자를 채우는 것이다. 이렇게 하면 줄마다, 열마다, 9개의 3x3 부분 중 하나하나가 1부터 9까지의 모든 숫자를 포함한다.마지막 수수께끼는 부분적으로 완성된 격자(단서를 남긴 격자)로 가장 좋은 상황에서 단일한 해결 방안이 있어야 한다.
수수께끼를 만들려면, 우리는 우선 완전하고 효과적인 격자를 얻어야 한다.첫 번째 생각은 뚜렷하고 간단하다. 무작위 순서로 한 줄의 숫자를 만들어 한 줄에 적용하고 한 줄씩 한쪽으로 옮긴다.어떻게 보이는지 봅시다.
9, 5, 6, 2, 4, 8, 7, 1, 3 등 가능한 숫자를 무작위로 정렬해 봅시다.
메쉬의 첫 번째 행에 적용한 다음 행을 복사하여 특정 양의 정사각형으로 이동합니다.
이 과정을 계속함으로써 우리는 마침내 효과적인 디지털 격자를 얻었다.
우리가 지금 해야 할 일은 이런 단서를 생략하는 것이다.이런 방법은 매우 간단해서 논리를 응용하는 데 너무 많은 작업을 필요로 하지 않는다.그러나 하나의 큰 문제는 솔로 모드가 너무 뚜렷해서 게이머들이 곧 완전히 이해할 수 있을 것이다.
나는 다른 가능한 방법을 찾아서 매우 재미있는 해결 방안을 발견했다. 그것은 빈 디지털 격자에서 디지털 해산기를 운행하는 것이다.이런 방법은 최초의 목적을 더욱 복잡하게 만들었다. 왜냐하면 지금 우리는 생성기와 해산기를 동시에 구축해야 하기 때문이다.
앞에서 말한 바와 같이, 일단 우리가 효과적인 격자가 생기면, 우리는 약간의 숫자를 삭제하고, 일정한 수량의 단서를 생략해야 한다.디지털 게임의 난이도는 단서의 수량과 문제 해결에 필요한 기교의 수량을 포함하여 서로 다른 방식으로 확정할 수 있다.이 생성기의 단순성을 구축하기 위해서 우리는 대량의 단서를 기억하기만 하면 된다.
비밀 번호
수독망격을 표시하기 위해 우리는 다차원수조
grid[a][b]를 사용하는데 그 중에서 a는 한 줄, b-한 열을 나타낸다.우리는 0의 값이 그물 위의 빈 정사각형이라고 생각한다.그래서 우선 우리는 빈 격자를 만들어야 한다.우리는 그룹을 0으로 채우기 위해 하드 인코딩을 하거나 9번씩 플러그인 순환을 실행할 수 있다.
const generateEmptyGrid = () => {
const grid = [];
for (let i = 0; i < 9; i++) {
for (let l = 0; l < 9; l++) {
if (grid[i] === undefined) {
grid[i] = [];
}
grid[i].push(0);
}
}
return grid;
}
[
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0]
]
해산기에 대해, 나는 격자 안에서 실행될 때 모든 정사각형이 고려하는 모든 숫자를 추적하기 위해 역추적 알고리즘을 선택했다.
우리는 해산기가 고려할 무작위 숫자 순서를 얻었다.
const generateNumbersToCheck = () => {
const numbers = [1,2,3,4,5,6,7,8,9];
const numbersRearranged = [];
for (let i = 0; i < 9; i++) {
const randomIndex = Math.floor((Math.random() * numbers.length));
const [randomNumber] = numbers.splice(randomIndex, 1);
numbersRearranged.push(randomNumber);
}
return numbersRearranged;
}
다음에 우리는 회상도를 고려해야 한다.지도의 키는
"col,row"의 형식으로 그물의 위치를 표시할 것이다.나는 먼저 열을 줄 앞에 놓았다. 왜냐하면 이렇게 하면 X축과 Y축을 더욱 대표할 수 있기 때문이다.이 값들은 숫자 그룹으로 특정 시간에 특정 위치에서 검사하는 숫자를 대표할 것이다.// {[key: “col,row”]: number[]}우리는 모든 빈 네모난 블록의 좌표를 얻어 지도를 형성했다.const getEmptySquaresList = (grid) => {
const squaresToFill = [];
for (let i = 0; i < 9; i++) {
for (let l = 0; l < 9; l++) {
if (grid[i][l] === 0) {
let squareCode = `${l},${i}`;
squaresToFill.push(squareCode);
}
}
}
return squaresToFill;
}
const getBacktraceMap = (emptySquaresList) => {
const backtraceMap = {};
const len = emptySquaresList.length;
for (let i = 0; i < len; i++) {
backtraceMap[emptySquaresList[i]] = [];
}
return backtraceMap;
}
const solveSudokuPuzzle = (grid) => {
const numbersToCheck = generateNumbersToCheck();
const emptySquares = getEmptySquaresList(grid);
const backtraceMap = getBacktraceMap(emptySquares);
const pathLength = emptySquares.length;
pointerLoop:
for (let pointer = 0; pointer < pathLength; ) {
// If pointer eventually gets to -1 - puzzle is invalid
if (pointer < 0) {
throw new Error(“Error: The puzzle given is invalid”);
}
const currentSquare = emptySquares[pointer];
// Check if we have tried all of the digits on current square
if (backtraceMap[currentSquare].length === 9) {
// Reset the digits tried on current square list
backtraceMap[currentSquare] = [];
// Move pointer back
pointer--;
// Clear the previously inserted digit on the grid
const [prevCol, prevRow] = emptySquares[pointer].split(',');
insertDigit(grid, 0, prevCol, prevRow);
continue;
}
// Get the position of current square
const [col, row] = currentSquare.split(',')
singleSquareCheck:
for (let numberToGuessIndex = 0; numberToGuessIndex < 9; numberToGuessIndex++) {
const currentNumberToCheck = numbersToCheck[numberToGuessIndex];
// Check if it has not been guessed before
if (backtraceMap[currentSquare].indexOf(currentNumberToCheck) === -1) {
// Check if it can be inserted
const canBeInserted = canNumberBeInserted(grid, currentNumberToCheck, x, y);
// Append as a considered number
backtraceMap[currentSquare].push(currentNumberToCheck);
if (canBeInserted) {
// Apply number and move on
insertDigit(grid, currentNumberToCheck, x, y);
pointer++;
break singleSquareCheck;
}
}
}
}
return grid;
}
pointerLoop 이 모든 빈 칸을 통과하도록 순환을 실행했다.우리는 바늘이 마이너스인지 확인합니다. 이것은 격자가 무효라는 것을 의미하며, 이러한 상황에서 오류를 던집니다.우리는 또한 특정 정사각형의 모든 숫자를 시도했는지 검사했다. 만약 그렇다면, 우리는 바늘을 한 걸음 뒤로 이동하고 이전의 동작을 초기화할 것이다.만약 우리가 준비가 된다면, 우리는 특정한 정사각형 singleSquareCheck 순환에서 가능한 숫자를 검사할 것이다.만약 우리가 삽입할 수 있는 숫자를 찾게 된다면, 우리는 그것을 격자에 적용한 후에 계속할 것이다.만약 우리가 모든 숫자를 시도한다면, 우리는 결국 이전의 검사로 돌아갈 것이다.우리는 그곳에서도 조수를 몇 명 파견했다.
insertDigit 특정 격자 위치에 숫자를 삽입합니다.const insertDigit = (grid, digit, col, row) => {
grid[row][col] = digit;
}
canNumberBeInserted 숫자가 격자의 3x3 부분, 현재 줄과 현재 열에 나타나는지 검사합니다.const canNumberBeInserted = (grid, numberToCheck, col, row) => {
// Check for occurence in 3x3 section)
// getSectionIndexes returns the starting indexes of needed 3x3 section
const [startingCol, startingRow] = getSectionIndexes(col,row);
for (let i = 0; i < 3; i++) {
for (let l = 0; l < 3; l++) {
const colIndexToCheck = startingCol + l;
const rowIndexToCheck = startingRow + i;
if (grid[colIndexToCheck][rowIndexToCheck] === numberToCheck) {
return false;
}
}
}
// Check for the occurence in row
for (let i = 0; i < 9; i++) {
if (grid[row][i] === numberToCheck) {
return false;
}
}
// Check for the occurence in column
for (let i = 0; i < 9; i++) {
if (grid[i][col] === numberToCheck) {
return false;
}
}
return true;
}
전략으로 돌아오다
앞에서 말한 바와 같이 단서의 수량은 선택의 난이도에 달려 있다.
const getNumberOfClues = (difficulty) => {
switch(difficulty) {
case 'evil':
return Math.floor(Math.random() * 2) + 16;
case 'hard':
return Math.floor(Math.random() * 7) + 19;
case 'medium':
return Math.floor(Math.random() * 9) + 27;
case 'easy':
return Math.floor(Math.random() * 9) + 36;
default:
return Math.floor(Math.random() * 27 + 16);
}
}
가장자리를 잡을 가능성이 아주 적은 상황에서 이렇게.우리는 더욱 균일한 분포 힌트를 가진 수수께끼를 얻기 위해 제거 모드를 응용할 수 있다.내가 발견한 방법 중 하나는 무작위 블록을 선택하고 제거하는 것이다. 그것은 맞은편에 있는 다른 블록이다.이렇게:
그러나 우리의 수수께끼에는 매우 뚜렷한 거울 단서 패턴이 있을 것이다.
여기서 우리가 할 수 있는 또 다른 일은 격자를 각 방향으로 0, 1 또는 2/3로 이동하는 것이다.
지금 얘는 튼튼해 보여!
코드로 돌아오기
const leaveClues = (grid, cluesCount) => {
const squaresToClearCount = 81 - cluesCount;
// Have all available square indexes in one array
const allSquareIndexes = [];
for (let i = 0; i < 9; i++) {
for (let l = 0; l < 9; l++) {
allSquareIndexes.push(`${l},${i}`);
}
}
// Get indexes of squares that are going to be cleared
const squaresToClear = [];
for (let counter = 0; i < squaresToClearCount;) {
const [randomSquare] = allSquareIndexes.splice(Math.floor(Math.random() * allSquareIndexes.length), 1);
squaresToClear.push(randomSquare);
counter++;
// We keep track of counter instead of iteration, because we may want to get multiple squares on single iteration
// If we reach the limit here, stop the loop
if (counter === squaresToClearCount) {
break;
}
// If random square is center square, it will not have a counter square
if (randomSquare === '4,4') {
continue;
}
const counterSquare = getCounterSquare(randomSquare);
const indexOfCounterSquare = allSquareIndexes.indexOf(counterSquare);
if (indexOfCounterSquare !== -1) {
allSquareIndexes.splice(indexOfCounterSquare, 1);
squaresToClear.push(counterSquare);
counter++;
}
}
// Clear those digits from the grid
for (let i = 0; i < squaresToClear.length; i++) {
const [col,row] = squaresToClear[i].split(',');
insertDigit(grid, 0, col, row);
}
// Shift the grid
shiftGrid(grid);
return grid;
}
const getCounterSquare = (square) => {
const [col, row] = square.split(',');
const counterRow = 8 - Number(row);
const counterCol = 8 - Number(col);
return `${counterRow},${counterCol}`;
}
const shiftGrid = (grid) => {
const xThirds = Math.floor(Math.random() * 3) + 0;
const yThirds = Math.floor(Math.random() * 3) + 0;
if (xThirds === 0 && yThirds === 0) {
return;
}
// Shift rows
if (yThirds > 0) {
for (let i = 0; i < yThirds * 3; i++) {
const lastRow = grid.pop();
grid.unshift(lastRow);
};
}
// Shift columns
if (xThirds > 0) {
for (let i = 0; i < 9; i++) {
for (let l = 0; l < xThirds * 3; l++) {
const lastRowNumber = grid[i].pop();
grid[i].unshift(lastRowNumber);
}
}
}
}
이렇게!우리는 필요한 난이도의 솔로 게임을 얻을 수 있다.우리는 심지어 코드를 만들어서 필요한 수량의 단서를 가진 수수께끼를 만들 수도 있다.일부 서면 조수는 심지어 게임 자체에 매우 유용할 수도 있다.
만약 네가 이 점을 할 수 있다면, 너의 독서에 감사한다.
Reference
이 문제에 관하여(디지털 지능 생성기 구축), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/lukasgrinys/building-a-sudoku-puzzle-generator-edo텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
