On 08/25/2012 02:51 AM, Chris Cain wrote:
> On Friday, 24 August 2012 at 23:14:02 UTC, maarten van damme wrote:
>> http://en.wikipedia.org/wiki/File:Sudoku_puzzle_hard_for_brute_force.jpg
>
> It occurs to me that one of the main reasons why this particular puzzle
> would be hard for brute force is that the first line is blank and more
> than half of the second line is blank, and it seems like it is designed
> to have as many choices as possible before a set square is encountered.
>
> I bet it could be solved much quicker by a computer by doing it in reverse.
>
> I've got some ideas, maybe I'll write a solution to this myself. :)

FWIW both mine and Maarten's solution require a trivial amount of time
to solve it.

On Saturday, 25 August 2012 at 00:51:23 UTC, Chris Cain wrote:
> On Friday, 24 August 2012 at 23:14:02 UTC, maarten van damme wrote:
>> http://en.wikipedia.org/wiki/File:Sudoku_puzzle_hard_for_brute_force.jpg
>
> It occurs to me that one of the main reasons why this particular puzzle would be hard for brute force is that the first line is blank and more than half of the second line is blank, and it seems like it is designed to have as many choices as possible before a set square is encountered.
>
> I bet it could be solved much quicker by a computer by doing it in reverse.

 Is most likely. What would you do, have multiple threads all solving it until one came with the fastest solution and then fix it back to how it should be? It would work...

 As a test I've taken the puzzle and converted it, normally I gave it up after some 30 seconds but flipped it was 2 seconds.

As the picture puzzle shows:
..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9

Flipped:
....4...9..2.1....5......73.9.........4...1.....5.7.....1.2.........3.85.........

 Strange, flipping it various ways and connecting them comes up with an interesting patterns.

> I've got some ideas, maybe I'll write a solution to this myself. :)

 Adding another level of possibilities removal before going to brute force can definitely do a lot.


On Saturday, 25 August 2012 at 01:00:04 UTC, Timon Gehr wrote:
> FWIW both mine and Maarten's solution require a trivial amount of time to solve it.

 Same for my C version of the solver. But that's not really the topic here :P

The puzzle unflipped is extra hard as the solution to the first row is 987 654 321. Come to think of it, one could add a new function "flip" that mutates the sudoku according to well known rules and maybe something like unflip for when the sudoku was finnished.

New techniques could certainly be added (like single candidate and naked pairs) without too much overhead so they might just pay off, certainly on the impossible puzzle.

Maybe I could also pre-calculate all rows, collumns and squares and store them in int pointer arrays. This way things could become even faster. Would it be possible to do something like that in ctfe?

While trying to use Array!bool I noticed this:
import std.container;

void main(){
	Array!bool test;
	test[0]=false;
}
gives an assertion failure without any information.
Also, why on earth can't I instantiate array!bool with a given length?

On Saturday, 25 August 2012 at 13:33:27 UTC, maarten van damme wrote:
> While trying to use Array!bool I noticed this:
> import std.container;
>
> void main(){
> 	Array!bool test;
> 	test[0]=false;
> }
> gives an assertion failure without any information.
> Also, why on earth can't I instantiate array!bool with a given length?

import std.container, std.stdio;

void main() {
    Array!bool myArr;
    myArr.length = 9; // set length before use
    myArr[0] = true;
    myArr[5] = true;
    writeln("myArr = ", myArr[]); // myArr = [true, false, false, false, false, true, false, false, false]
}

Ok, I'll try with Array!bool instead of bool.

I now renamed a few things, added a few extra checks and generalized bearophiles modifications. Now the only thing keeping it from solving 25 x 25 size sudoku's is the way I input numbers :)

However, I now have a very strange issue. Compiling with dmd -O -release -inline works but compiling with dmd -O -release -inline -noboundscheck gives the following compile time error:

Assertion failure: 'semanticstarted == 2' on line 829 in file 'module.c'

abnormal program termination

Code is at http://dpaste.dzfl.pl/41a01039

I can't test on gdc because compilation of the aur sources failed on my laptop and I'm to lazy to try and determine the source of the error :p

Also, why do you use enum's and not consts ?

maarten van damme:

> Ok, I'll try with Array!bool instead of bool.

There is also a BitVector, but it's heap-allocated, so probably
it's not a good idea. A ucent used as bit vector on a 64 bit
system is maybe the best way to implement that :-) But we don't
have ucents yet.

So maybe you have to implement your own bitvector with an uint[N]
where N is the minimal possible, it's 3 for the 9*9 Sudoku.


> I now renamed a few things, added a few extra checks and generalized
> bearophiles modifications. Now the only thing keeping it from solving
> 25 x 25 size sudoku's is the way I input numbers :)
>
> However, I now have a very strange issue. Compiling with dmd -O
> -release -inline works but compiling with dmd -O -release -inline
> -noboundscheck gives the following compile time error:
>
> Assertion failure: 'semanticstarted == 2' on line 829 in file 'module.c'
>
> abnormal program termination

Congratulations, you have found a compiler bug. I have found
maybe one hundred of those. Please minimize the code and submit
it to Bugzilla :-)


> Code is at http://dpaste.dzfl.pl/41a01039

Replacing side and size with boardSide and boardSize is a good
idea. But the two variables differ only by one char, so there's
space for further improvements.

The code contains:

// But, atention, an ushort is only 16 bits. Change this to uint
to be able to solve 25 x 25 sudoku's (http://dlang.org/type.html)
alias ushort SudokuCell; // contains only values in (0,
everythingPossible)

In D there are smarter ways to do that.
Generally in all your programs try to move as much semantics as
possible from comments to code.

In this case this means using static ifs to choose ushort or uint
(or give a compile-time error) to choose the best SudokuCell
type. There are fancier ways to do it, but this is simple and
seems OK, but I have not tested it:

// SudokuCell contains only values in (0, everythingPossible) (a
RangedValue when available)
static if (boardSide <= short.sizeof * 8) {
     alias ushort SudokuCell;
} else static if (boardSide <= uint.sizeof * 8) {
     alias uint SudokuCell;
} else static if (boardSide <= ulong.sizeof * 8) {
     alias ulong SudokuCell;
} else
     static assert(false, "");


Eventually a SudokuCell is meant to be replaced by a ranged
value, something like:

static if (boardSide <= short.sizeof * 8) {
     alias RangedValue!(ushort, 0, everythingPossible+1)
SudokuCell;
} else static if...

This moves another comment to code, and avoids some potential
run-time bugs in the code, because it forbids you to assign a
value outside that range (in non-release mode) to a Sudoku cell.


> Also, why do you use enum's and not consts ?

If you assign a global value like an int, using const or enum
produces the same binary. But generally enum conveys better that
meaning, because in D enum means that it's known at compile-time,
while const is for run-time constants too. Often while you code
it's better to use the tightest semantics available :-)
You just have to be careful with enum arrays, because they cause
extra allocations.

Bye,
bearophile

struct MaxArray(T, size_t maxLen) {
...
    void opAssign(T[] a) {

I forgot ==>

struct MaxArray(T, size_t maxLen) {
...
    void opAssign(T[] a) pure nothrow {

Bye,
bearophile

And now your backtrack() function too can be nothrow :-)

Bye,
bearophile

Ok, thank you very much with your help :)