Permalink
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
78 lines (58 sloc) 3.67 KB
layout title date excerpt categories
post
Sudoku
2018-03-20 18:08:08 -0500
<p><a href="https://remarkablegames.org/sudoku/" target="_blank">Sudoku</a> has been released!</p> <iframe src="https://remarkablegames.org/sudoku/" frameBorder="0" width="100%" height="500px"></iframe> <p>It's a logic-based, combinatorial number-placement puzzle (see <a href="https://github.com/remarkablegames/sudoku" target="_blank">source</a>).</p> <p>Looking to challenge your brain? Play it <a href="https://remarkablegames.org/sudoku/" target="_blank">here</a>.</p>
sudoku logic number game puzzle preact

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]({% post_url 2018/2018-01-13-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).

<iframe height="1000px" width="100%" src="https://repl.it/@remarkablemark/Sudoku-Solution-Generator?lite=true" scrolling="no" frameborder="no" allowtransparency="true" allowfullscreen="true" sandbox="allow-forms allow-pointer-lock allow-popups allow-same-origin allow-scripts allow-modals"></iframe>

UI

Like [Tile Matcher]({% post_url 2018/2018-01-13-tile-matcher %}), the user interface (UI) is event-driven which meant that I was able to use Preact. The fiddle came quickly after.

<script async src="//jsfiddle.net/remarkablemark/e9abgq6d/embed/result,js,css,html/"></script>

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.

<iframe src="https://remarkablegames.org/sudoku/" frameBorder="0" width="100%" height="500px"></iframe>