5
$\begingroup$

A standard 9x9 Sudoku uses the digits 1 to 9.

You are only allowed two distinct primes to represent 1 to 9.

Find out the minimum number of characters (digits + signs) needed to construct a Sudoku puzzle with a unique solution.

Allowed signs are plus, minus, division, multiplication, factorial, and exponentiation.

$\endgroup$
3
$\begingroup$

The minimal Sudoku contains 17 digits: 2 each of seven of the nine digits, 3 of another digit, and none of the last one. (By symmetry, it doesn't matter which two digits are selected to appear 3 and 0 times in the Sudoku.)

If we select our two primes as

2 and 3, then we can represent the digits as $$3-2,2,3,2+2,2+3,3!,?,2\wedge3,3\times3.$$ (We omit 7 because we only need to represent all but one of the digits for the minimal Sudoku.)

So we choose the minimal Sudoku with

seventeen digits filled, two each of $1,2,4,5,6,8,9$ and three of $3$.

How many symbols do we need to use then?

Each of $1,4,5,8,9$ requires three symbols, $2$ and $3$ require only one, and $6$ requires two. So the total is $$5(2\times3)+(2\times1)+(2\times2)+(3\times1)=30+2+4+3=39.$$

$\endgroup$
  • $\begingroup$ Excellent !!!........ $\endgroup$ – Uvc May 27 at 17:09
2
$\begingroup$

I got it down to

37 symbols

Using all the same methods as @RandAlThor, but choosing a

17 clue sudoku with a slightly more off-balance clue distribution (1,3,4,2,1,2,0,2,2):

enter image description here

For double checking purposes, here's the sudoku as solved by https://sudokusolver.net/

enter image description here

For further improvement, it's very likely that some digit(s), particularly those that occur twice, can be replaced by adding both a 2 and a 3, giving a sudoku that has more clues but fewer symbols. Since I cannot figure out a non-boring way to do the search for those, I'll leave it to someone else.

EDIT @Oray helpfully pointed out in the comments that factorials were allowed, and OP says we can cheat with the exponentiation symbol too so here's a version with

29 symbols:

enter image description here

$\endgroup$
  • $\begingroup$ Very elegant...!!! $\endgroup$ – Uvc May 27 at 19:01
  • $\begingroup$ 3! instad of 3+3 makes it 35 :) $\endgroup$ – Oray May 27 at 19:22
  • $\begingroup$ @Oray Oh, right, we were allowed to use that. Oops :-) $\endgroup$ – Bass May 27 at 19:46
  • $\begingroup$ We can cheat a little bit..use the power notation and omitting “^” carrot symbol..8 can be written with 2 characters..bringing it down further to 33..just a tad less than double the minimum of 17. $\endgroup$ – Uvc May 27 at 19:47
  • $\begingroup$ Given these new tricks, the latest version is probably pretty close to a hard minimum: the only 3-symbol clues occur only once each, so they cannot be replaced with anything, and replacing 2-symbol clues seems unlikely to bring the number of symbols down very much. $\endgroup$ – Bass May 27 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.