## Algorithm to generate sudoku

0 / 237

Overview

Sudoku (数独sūdoku, digit-single) (/sˈdk//-ˈdɒk-//sə-/, originally called Number Place)[1] is a logic-based,[2][3] combinatorial[4] number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called “boxes”, “blocks”, or “regions”) contain all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution. (Source:- Sudoku)

golibrary.co – Sudoku

Our task is to write a program to generate a 9×9 sudoku grid.

Below is the explanation for algorithm to generate sudoku and the logic behind.

Algorithm:

• Initilialize the 9×9 sudoku 2D array (matrix) with all zeroes.
• Have an outer loop which runs until the generated sudoku is solved by the solver algorithm (coming next).
• Have a nested inner loop with index “i”  running for values between 1 to 9.
• Pickup a random cell in the grid to place a number.
• Check if the generated sudoku so far is valid (Read here) and the cell isn’t occupied already, if yes, assign the value of i to the cell. If not, check if other values of i generate a valid sudoku.
• Check if sudoku is solvable. If yes, make a tentative assignment to the selected cell number with the value of i. If not, skip the assignment and backtrack.
• Repeat the previous 3 steps until the algorithm is able to solve the complete sudoku and save this configuration in the matrix but don’t display yet.
• Based on the difficulty level, select the number of cells which will be left blank in the sudoku configuration obtained in step 7 and show the generated board to the user as it’s solveable.

Sudoku solver algorithm:

• Find empty location in the matrix, which can be assigned a value from 1 to 9.
• Loop through values 1 to 9, having index i.
• Assign the value of i to the empty location found in step 1, provided that the sudoku is valid.
• Recursively, try solving sudoku again after step 3. If solving fails, reject the last cell assignment and reset is back to zero. If solving is successful return true.

Javascript code below for the above:

```// algorithm to solve sudoku recursively
function solveSudoku() {
var cell_no = findEmptyLocation(); //find an empty cell location

if (cell_no == -1) //this means all the locations have been assigned values and sudoku is solved
{
return true;
}

for (var num = 1; num <= 9; num++) {
if (chkValid(cell_no, num) == false) //if it looks promising and meets the sudoku row, column and box assignments, make a tentative assignment
{
board[cell_no] = num;

// solve recursively from this position
if (solveSudoku() == true) //this means sudoku solved successfully for this level only, so return true to previous call
return true;
else {
board[cell_no] = 0; // solving failed, try again
}
}
}

return false; //puzzle solving failed, backtrack from this point
}

// this function finds the empty cell location on the board
function findEmptyLocation() {
for (var index = 0; index < 81; index++) {
if (board[index] == 0) //cell free
{
return index;
}
//else loop continues
}

return -1;
}```

Algorithm to check if sudoku is valid:

This has also been explained on our discussion forum (http://forum.golibrary.co), steps below:

A sudoku is said to be valid if

• If all boxes (3×3 grids) contain no duplicates and thus unique numbers between 1-9
• All rows contain no duplicates and thus unique numbers between 1-9
• All columns contain no duplicates and thus unique numbers between 1-9

Checking the same conditions below in the code:

```var isValidSudoku = function(board) {
for (let i = 0; i < 9; i++) {
let row = new Set(), col = new Set(), sqr = new Set();
for (let j = 0; j < 9; j++) {
let rowc = board[i][j];
let colc = board[j][i];
let sqrc = board[Math.floor(i / 3) * 3 + Math.floor(j / 3)][(i % 3) * 3 + j % 3];
if (row.has(rowc) || col.has(colc) || sqr.has(sqrc)) return false;
if (rowc !== ".") row.add(rowc);
if (colc !== ".") col.add(colc);
if (sqrc !== ".") sqr.add(sqrc);
}
}
return true;
};```

Run this code to see the demo:

```<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="viewport" content="width=device-width,height=device-height,initial-scale=1.0"/>
<title>Golibrary.co - Sudoku</title>
<script type="text/javascript">
</script>
<style type="text/css">
.digit {border:0px; width:100%; height: 100%; background-color:transparent; text-align:center; font-weight:bold; color:blue; font-size:25}
.digitLock {border:0px; width:100%; height: 100%; background-color:transparent; text-align:center; font-weight:bold; color:green; font-size:25}
.bcontrol {font-weight:bold; font-size:15}
.bdigit {font-weight:bold; font-size:15}
/* Smartphones (portrait and landscape) ----------- */
@media only screen
and (min-device-width : 320px)
and (max-device-width : 480px) {
/* Styles */
.conHeight {
height:250px;
}
}
/* Smartphones (landscape) ----------- */
@media only screen
and (min-width : 321px) {
/* Styles */
}
/* Smartphones (portrait) ----------- */
@media only screen
and (max-width : 320px) {
/* Styles */
}
/* iPads (portrait and landscape) ----------- */
@media only screen
and (min-device-width : 768px)
and (max-device-width : 1024px) {
/* Styles */
}
/* iPads (landscape) ----------- */
@media only screen
and (min-device-width : 768px)
and (max-device-width : 1024px)
and (orientation : landscape) {
/* Styles */
}
/* iPads (portrait) ----------- */
@media only screen
and (min-device-width : 768px)
and (max-device-width : 1024px)
and (orientation : portrait) {
/* Styles */
}
/* Desktops and laptops ----------- */
@media only screen
and (min-width : 1224px) {
/* Styles */
}
/* Large screens ----------- */
@media only screen
and (min-width : 1824px) {
/* Styles */
}
/* iPhone 4 ----------- */
@media
only screen and (-webkit-min-device-pixel-ratio : 1.5),
only screen and (min-device-pixel-ratio : 1.5) {
/* Styles */
}
</style>
<body>
<?php
?>
<h2 style = "top:150px; left:410px"> SuDoKu</h2>
<div style="border:3px solid red; height:100%;width:300px;padding:5px;"><br><br>
<b>Levels:&nbsp;</b>
<b>Timer:&nbsp;</b><input id="txt" readonly size="10" style="background:gray;line-height:30px;"></input>
</div>
<br><br><br>
<div id="con" class="conHeight" style="background-color:#eeeeee; width:50%; height:410px;">
<table border = "2" width = "100%" height = "100%" cellpadding = "0" cellspacing = "0">
<tr>
<td rowspan = "3" width = "100" align = "left" valign = "top" bgcolor = "#339933">
<table border = "1" height = "410" width = "100" cellpadding = "0" cellspacing = "0"><tr><td>
<h3>&nbsp Controls</h3>
&nbsp &nbsp<input type="button" style = "height: 25px; width: 75px" class="bcontrol" name="bcreate" value="Create" onclick="create()"><br><br>
&nbsp &nbsp<input type="button" style = "height: 25px; width: 75px" class="bcontrol" name="bclear" value="Clear" onclick="resetGame()"><br><br>
&nbsp &nbsp<input type="button" style = "height: 25px; width: 75px" class="bcontrol" id="bpause" name="bpause" value="Pause" onclick="pause()"><br><br>
&nbsp &nbsp<input type="button" style = "height: 25px; width: 75px" class="bcontrol" name="block" value="Lock" onclick="lock()"><br><br>
&nbsp &nbsp<input type="button" style = "height: 25px; width: 75px" class="bcontrol" name="breset" value="Reset" onclick="reset()"><br><br>
&nbsp &nbsp<input type="button" style = "height: 25px; width: 75px" class="bcontrol" name="bhint" value="Hint" onclick="hint();"><br><br>
&nbsp &nbsp<input type="button" style = "height: 25px; width: 75px" class="bcontrol" name="bsolve" value="Solve" onclick="solve();"><br>
</table></tr></td>
</td>
<td rowspan = "3" width = "350" align = "center" valign = "top" bgcolor = "#cc9999">
<table border = "1" height = "410" width = "390" cellpadding = "0" cellspacing = "0">
<tr width = "100%" height = "33%">
<td width = "33%">
<table border = "1" cellpadding = "0" cellspacing = "0" height = "133" width = "130">
<tr>
<td><input class="digit" type="text" id="c0" value=" " size="1" readonly onclick="set(0)"></td>
<td><input class="digit" type="text" id="c1" value=" " size="1" readonly onclick="set(1)"></td>
<td><input class="digit" type="text" id="c2" value=" " size="1" readonly onclick="set(2)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c9" value=" " size="1" readonly onclick="set(9)"></td>
<td><input class="digit" type="text" id="c10" value=" " size="1" readonly onclick="set(10)"></td>
<td><input class="digit" type="text" id="c11" value=" " size="1" readonly onclick="set(11)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c18" value=" " size="1" readonly onclick="set(18)"></td>
<td><input class="digit" type="text" id="c19" value=" " size="1" readonly onclick="set(19)"></td>
<td><input class="digit" type="text" id="c20" value=" " size="1" readonly onclick="set(20)"></td>
</tr>
</table>
</td>
<td width = "33%">
<table border = "1" cellpadding = "0" cellspacing = "0" height = "133" width = "130">
<tr>
<td><input class="digit" type="text" id="c3" value=" " size="1" readonly onclick="set(3)"></td>
<td><input class="digit" type="text" id="c4" value=" " size="1" readonly onclick="set(4)"></td>
<td><input class="digit" type="text" id="c5" value=" " size="1" readonly onclick="set(5)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c12" value=" " size="1" readonly onclick="set(12)"></td>
<td><input class="digit" type="text" id="c13" value=" " size="1" readonly onclick="set(13)"></td>
<td><input class="digit" type="text" id="c14" value=" " size="1" readonly onclick="set(14)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c21" value=" " size="1" readonly onclick="set(21)"></td>
<td><input class="digit" type="text" id="c22" value=" " size="1" readonly onclick="set(22)"></td>
<td><input class="digit" type="text" id="c23" value=" " size="1" readonly onclick="set(23)"></td>
</tr>
</table>
</td>
<td width = "33%">
<table border = "1" cellpadding = "0" cellspacing = "0" height = "133" width = "130">
<tr>
<td><input class="digit" type="text" id="c6" value=" " size="1" readonly onclick="set(6)"></td>
<td><input class="digit" type="text" id="c7" value=" " size="1" readonly onclick="set(7)"></td>
<td><input class="digit" type="text" id="c8" value=" " size="1" readonly onclick="set(8)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c15" value=" " size="1" readonly onclick="set(15)"></td>
<td><input class="digit" type="text" id="c16" value=" " size="1" readonly onclick="set(16)"></td>
<td><input class="digit" type="text" id="c17" value=" " size="1" readonly onclick="set(17)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c24" value=" " size="1" readonly onclick="set(24)"></td>
<td><input class="digit" type="text" id="c25" value=" " size="1" readonly onclick="set(25)"></td>
<td><input class="digit" type="text" id="c26" value=" " size="1" readonly onclick="set(26)"></td>
</tr>
</table>
</td>
</tr>
<tr width = "100%" height = "33%">
<td width = "33%">
<table border = "1" cellpadding = "0" cellspacing = "0" height = "133" width = "130">
<tr>
<td><input class="digit" type="text" id="c27" value=" " size="1" readonly onclick="set(27)"></td>
<td><input class="digit" type="text" id="c28" value=" " size="1" readonly onclick="set(28)"></td>
<td><input class="digit" type="text" id="c29" value=" " size="1" readonly onclick="set(29)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c36" value=" " size="1" readonly onclick="set(36)"></td>
<td><input class="digit" type="text" id="c37" value=" " size="1" readonly onclick="set(37)"></td>
<td><input class="digit" type="text" id="c38" value=" " size="1" readonly onclick="set(38)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c45" value=" " size="1" readonly onclick="set(45)"></td>
<td><input class="digit" type="text" id="c46" value=" " size="1" readonly onclick="set(46)"></td>
<td><input class="digit" type="text" id="c47" value=" " size="1" readonly onclick="set(47)"></td>
</tr>
</table>
</td>
<td width = "33%">
<table border = "1" cellpadding = "0" cellspacing = "0" height = "133" width = "130">
<tr>
<td><input class="digit" type="text" id="c30" value=" " size="1" readonly onclick="set(30)"></td>
<td><input class="digit" type="text" id="c31" value=" " size="1" readonly onclick="set(31)"></td>
<td><input class="digit" type="text" id="c32" value=" " size="1" readonly onclick="set(32)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c39" value=" " size="1" readonly onclick="set(39)"></td>
<td><input class="digit" type="text" id="c40" value=" " size="1" readonly onclick="set(40)"></td>
<td><input class="digit" type="text" id="c41" value=" " size="1" readonly onclick="set(41)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c48" value=" " size="1" readonly onclick="set(48)"></td>
<td><input class="digit" type="text" id="c49" value=" " size="1" readonly onclick="set(49)"></td>
<td><input class="digit" type="text" id="c50" value=" " size="1" readonly onclick="set(50)"></td>
</tr>
</table>
</td>
<td width = "33%">
<table border = "1" cellpadding = "0" cellspacing = "0" height = "133" width = "130">
<tr>
<td><input class="digit" type="text" id="c33" value=" " size="1" readonly onclick="set(33)"></td>
<td><input class="digit" type="text" id="c34" value=" " size="1" readonly onclick="set(34)"></td>
<td><input class="digit" type="text" id="c35" value=" " size="1" readonly onclick="set(35)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c42" value=" " size="1" readonly onclick="set(42)"></td>
<td><input class="digit" type="text" id="c43" value=" " size="1" readonly onclick="set(43)"></td>
<td><input class="digit" type="text" id="c44" value=" " size="1" readonly onclick="set(44)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c51" value=" " size="1" readonly onclick="set(51)"></td>
<td><input class="digit" type="text" id="c52" value=" " size="1" readonly onclick="set(52)"></td>
<td><input class="digit" type="text" id="c53" value=" " size="1" readonly onclick="set(53)"></td>
</tr>
</table>
</td>
</tr>
<tr width = "100%" height = "33%">
<td width = "33%">
<table border = "1" cellpadding = "0" cellspacing = "0" height = "133" width = "130">
<tr>
<td><input class="digit" type="text" id="c54" value=" " size="1" readonly onclick="set(54)"></td>
<td><input class="digit" type="text" id="c55" value=" " size="1" readonly onclick="set(55)"></td>
<td><input class="digit" type="text" id="c56" value=" " size="1" readonly onclick="set(56)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c63" value=" " size="1" readonly onclick="set(63)"></td>
<td><input class="digit" type="text" id="c64" value=" " size="1" readonly onclick="set(64)"></td>
<td><input class="digit" type="text" id="c65" value=" " size="1" readonly onclick="set(65)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c72" value=" " size="1" readonly onclick="set(72)"></td>
<td><input class="digit" type="text" id="c73" value=" " size="1" readonly onclick="set(73)"></td>
<td><input class="digit" type="text" id="c74" value=" " size="1" readonly onclick="set(74)"></td>
</tr>
</table>
</td>
<td width = "33%">
<table border = "1" cellpadding = "0" cellspacing = "0" height = "133" width = "130">
<tr>
<td><input class="digit" type="text" id="c57" value=" " size="1" readonly onclick="set(57)"></td>
<td><input class="digit" type="text" id="c58" value=" " size="1" readonly onclick="set(58)"></td>
<td><input class="digit" type="text" id="c59" value=" " size="1" readonly onclick="set(59)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c66" value=" " size="1" readonly onclick="set(66)"></td>
<td><input class="digit" type="text" id="c67" value=" " size="1" readonly onclick="set(67)"></td>
<td><input class="digit" type="text" id="c68" value=" " size="1" readonly onclick="set(68)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c75" value=" " size="1" readonly onclick="set(75)"></td>
<td><input class="digit" type="text" id="c76" value=" " size="1" readonly onclick="set(76)"></td>
<td><input class="digit" type="text" id="c77" value=" " size="1" readonly onclick="set(77)"></td>
</tr>
</table>
</td>
<td width = "33%">
<table border = "1" cellpadding = "0" cellspacing = "0" height = "133" width = "130">
<tr>
<td><input class="digit" type="text" id="c60" value=" " size="1" readonly onclick="set(60)"></td>
<td><input class="digit" type="text" id="c61" value=" " size="1" readonly onclick="set(61)"></td>
<td><input class="digit" type="text" id="c62" value=" " size="1" readonly onclick="set(62)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c69" value=" " size="1" readonly onclick="set(69)"></td>
<td><input class="digit" type="text" id="c70" value=" " size="1" readonly onclick="set(70)"></td>
<td><input class="digit" type="text" id="c71" value=" " size="1" readonly onclick="set(71)"></td>
</tr>
<tr>
<td><input class="digit" type="text" id="c78" value=" " size="1" readonly onclick="set(78)"></td>
<td><input class="digit" type="text" id="c79" value=" " size="1" readonly onclick="set(79)"></td>
<td><input class="digit" type="text" id="c80" value=" " size="1" readonly onclick="set(80)"></td>
</tr>
</table>
</td>
</tr>
</td></tr></table>
</td>
<td rowspan = "3" width = "100" align = "right" valign = "top" bgcolor = "#339933">
<table border = "1" height = "410" width = "100" cellpadding = "0" cellspacing = "0"><tr><td>
<h3 align = "center">KeyPad</h3>
<input type="button" style = "margin-top: 5px; margin-left:10px; height: 25px; width: 75px" class="bdigit" name="but1" value="1" onclick="setdigit(1)"><br>
<input type="button" style = "margin-top: 5px; margin-left:10px; height: 25px; width: 75px" class="bdigit" name="but2" value="2" onclick="setdigit(2)"><br>
<input type="button" style = "margin-top: 5px; margin-left:10px; height: 25px; width: 75px" class="bdigit" name="but3" value="3" onclick="setdigit(3)"><br>
<input type="button" style = "margin-top: 5px; margin-left:10px; height: 25px; width: 75px" class="bdigit" name="but4" value="4" onclick="setdigit(4)"><br>
<input type="button" style = "margin-top: 5px; margin-left:10px; height: 25px; width: 75px" class="bdigit" name="but5" value="5" onclick="setdigit(5)"><br>
<input type="button" style = "margin-top: 5px; margin-left:10px; height: 25px; width: 75px" class="bdigit" name="but6" value="6" onclick="setdigit(6)"><br>
<input type="button" style = "margin-top: 5px; margin-left:10px; height: 25px; width: 75px" class="bdigit" name="but7" value="7" onclick="setdigit(7)"><br>
<input type="button" style = "margin-top: 5px; margin-left:10px; height: 25px; width: 75px" class="bdigit" name="but8" value="8" onclick="setdigit(8)"><br>
<input type="button" style = "margin-top: 5px; margin-left:10px; height: 25px; width: 75px" class="bdigit" name="but9" value="9" onclick="setdigit(9)"><br>
<input type="button" style = "margin-top: 5px; margin-left:10px; height: 25px; width: 75px" class="bdigit" name="but10" value="_" onclick="setdigit(null)"><br>
</td></tr></table>
</td>
</tr>
</table>
</div>
<br><br>
</body>
</html>```

Subscribe to golibrary.co to read more interesting stuff. If you have any questions or comments, please let us know by commenting on the comment box below or sending us an email to mailto:info@golibrary.co

An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.