Sudoku

Mar 20, 2018HomeEdit


Sudoku is out!

Here’s a description of Sudoku from Wikipedia:

Sudoku (a.k.a. Number Place) is a logic-based, combinatorial number placement puzzle. The objective is to fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 subgrids that compose the grid contains all of the digits from 1 to 9.

Algorithm

Generating a Sudoku puzzle/solution turned out to be harder than expected. Like Tile Matcher, the shape of the puzzle/solution is a multi-dimensional array.

// 9x9 grid
[
  [1, 2, 3, 4, 5, 6, 7, 8, 9],
  [4, 5, 6, 7, 8, 9, 1, 2, 3],
  [7, 8, 9, 1, 2, 3, 4, 5, 6],
  [2, 3, 4, 5, 6, 7, 8, 9, 1],
  [5, 6, 7, 8, 9, 1, 2, 3, 4],
  [8, 9, 1, 2, 3, 4, 5, 6, 7],
  [6, 7, 8, 9, 1, 2, 3, 4, 5],
  [9, 1, 2, 3, 4, 5, 6, 7, 8],
  [3, 4, 5, 6, 7, 8, 9, 1, 2]
]

I saw that many other algorithms backtracked by solving the puzzle. The algorithm I hacked together in repl.it, on the other hand, attempted to generate each row randomly and checked if the solution was valid.

My algorithm wasn’t perfect because sometimes an infinite loop would occur (see line 110). Moreover, it could generate puzzles that aren’t unique (has more than 1 solution).

UI

Like Tile Matcher, the user interface (UI) is event-driven which meant that I was able to use Preact. The fiddle came quickly after.

I built the grid using semantic HTML5 elements like table and inputs. Consequently, I got tabbing navigation for free. I then implemented arrow key navigation to make it even more accessible for keyboard users.

<table>
  <tbody>
    <!-- rows -->
    <tr>
      <!-- columns -->
      <td>
        <input value="1" />
      </td>
      ...
    </tr>
    ...
  </tbody>
</table>

Acknowledgements

I want to give a shoutout to tdlm for his contributions. He helped fix several bugs and made a feature request.

Game

You can play the game here and check out the source code here. I’d love to hear your feedback and ideas.