@remarkablemark/

# Sudoku Solution Generator

## Generates the solution to a random Sudoku puzzle.

main.js
```1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
```
```// Sudoku uses numbers 1-9
const SIZE = 9;

/**
* Generates an array with values.
*
* @param  {Number}   len
* @param  {Function} [callback]
* @return {Array}
*/
const generateArray = (len, callback = () => {}) =>
Array.apply(null, { length: len }).map(callback);

// [1, 2, 3, 4, 5, 6, 7, 8, 9]
const NUMBERS = generateArray(SIZE, (_, index) => index + 1);

/**
* Shuffles an array.
*
* @param  {Array}   array
* @param  {Boolean} [shouldMutate=false]
* @return {Array}
*/
const shuffleArray = (array = [], shouldMutate = false) => {
const arr = shouldMutate ? array : array.slice();
for (let i = arr.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
return arr;
};

/**
* Generates row.
*
* @return {Array}
*/
const generateRow = () => shuffleArray(NUMBERS);

/**
* Given output, checks if row is usable.
*
* @param  {Number}  index
* @param  {Array}   row
* @param  {Array}   output
* @return {Boolean}
*/
const isRowUsable = (index, row = [], output = []) => {
let rowIndex = output.length - 1;
for (; rowIndex > -1; rowIndex--) {
let columnIndex = output[rowIndex].length - 1;
for (; columnIndex > -1; columnIndex--) {
// check if row value exists in output column
const rowValue = row[columnIndex];
if (rowValue === output[rowIndex][columnIndex]) return false;

let rowStart = 6;
if (index < 3) {
rowStart = 0;
} else if (index < 6) {
rowStart = 3;
}

let columnStart = 6;
if (columnIndex < 3) {
columnStart = 0;
} else if (columnIndex < 6) {
columnStart = 3;
}

let section = [];
for (i = 0; i < 3; i++) {
if (output[rowStart + i] instanceof Array) {
section = section.concat(
output[rowStart + i].slice(columnStart, columnStart + 3)
);
}
}

// check if row value exists in output 3x3 section
if (section.indexOf(rowValue) !== -1) return false;
}
}
return true;
};

/**
* Generates a solution to a Sudoku puzzle.
*
* @return {Array}
*/
const generateSolution = () => {
// seed 1st row
const output = [generateRow()];

// generate rows 2 to 8
let loopCount = 0;
for (let index = 1; index < 8; index++) {
while (true) {
const row = generateRow();
if (isRowUsable(index, row, output)) {
output[index] = row;
loopCount = 0;
break;
}
loopCount++;
// break and try again if stuck in infinite loop
if (loopCount > 2e5) return generateSolution();
}
}

// invert the output
const columnValues = output.reduce((result, row, rowIndex) => {
row.forEach((columnValue, columnIndex) => {
result[columnIndex] = result[columnIndex] || [];
result[columnIndex][rowIndex] = columnValue;
});
return result;
}, []);

// get 9th row
const lastRow = [];
for (let number = SIZE; number > 0; number--) {
for (let i = columnValues.length - 1; i > -1; i--) {
if (columnValues[i].indexOf(number) === -1) {
lastRow[i] = number;
break;
}
}
}
output.push(lastRow);

return output;
};

console.log(generateSolution());
```
Native Browser JavaScript