Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#26 2017-04-19 09:16:39

Leren
Member
Registered: 2017-04-19
Posts: 3

Re: Sort of like Sudoku

An exhaustive search has revealed that the total number of solutions for the first puzzle (post 1) without any additional constraints is 19,879 and for the second puzzle (post 4) is 140,884.

Leren

Offline

#27 2017-04-19 11:09:33

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Sort of like Sudoku

Hi, Leren (Dutch for 'learn'), and welcome to the forum! smile

Well, that's interesting information! I'd suspected that there would be many more solutions to the OP's puzzle (post #1) than the few that I'd found with the Excel Solver add-in I referred to in other posts, but not as many as that!!!

How did you arrive at that total, and what program did you use?


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#28 2017-04-19 18:51:40

Leren
Member
Registered: 2017-04-19
Posts: 3

Re: Sort of like Sudoku

You might have trouble believing this but I just looped through every possible value of all 40 blank cells subject to the given constraints. Now if there were no constraints that sounds like 7^ 40 steps, and even allowing that my

computer runs at about 140,000,000 steps/second, that would take something like 10^18 years. However the constraints reduce this dramatically, so that the whole process only took 470 seconds !

I just use visual basic in Excel, so lower level languages like C++ would no doubt be even faster. The trick is to pick your blank cell loops so that you can use a 30ish cell sum constraint as soon as possible.

I first came across this type of puzzle in a Sudoku forum that I am in, where someone could not solve one of these problems with the first and last rows being completely specified (in addition to the nine 30ish cells).

Well I just love a programming challenge and I looped through the 28 unspecified cells, and found the unique solution in less than perceptible time.

To find other similar puzzles I just did a google search and eventually found this thread, which naturally suggested the 40 blank cell problem which obviously would have multiple solutions.

Offline

#29 2018-04-21 11:22:40

EliTorres25
Member
Registered: 2017-11-03
Posts: 4

Re: Sort of like Sudoku

That's a great idea. The fact he different squares share number columns ads a significant amount of difficulty to those squares.

Offline

#30 2021-08-23 11:14:09

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Sort of like Sudoku

phrontister (post #14) wrote:

The standard Excel Solver was missing a constraint functionality I needed that the advanced one has.

EDIT: I had a tiny sniff of success with the standard Excel Solver by scaling the grid down from 7x7 to 5x5. The solver doesn't allow (as far as I could tell) crossing of the 'AllDifferent' constraint (eg, a row crossing a column - because one of them is then treated as not containing all variables, which it must contain), and so I cooked up some workarounds (linear and nonlinear).
Only one 'worked': ie,
- a nonlinear one, with the 'GRG Nonlinear' solving method;
- for one particular scenario only, in which I helped it get started by providing the answers to 4 cells, leaving the other 17 for the solver to find...which it did! smile
- it failed on all other assignments. sad

I gave the standard Excel Solver a tweak or 2 and had another go at the 7x7 puzzle from patchy1's first post (without post #24's constraints)...and this time it worked. up

The Solver stops computing at the first solution it finds, but, as mentioned in earlier posts, this puzzle has many solutions (both with post #24's constraints and without).
3e93bZK.jpg

Last edited by phrontister (2021-08-23 12:14:14)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#31 2022-01-22 05:03:50

Hicies87
Member
From: Portsmouth
Registered: 2022-01-22
Posts: 15

Re: Sort of like Sudoku

I love Sudoku and Japanese crossword puzzles. And this task seems to me more difficult.

Offline

Board footer

Powered by FluxBB