Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

Hi again,

I confess I have difficulties to diggest your code.

>From your experience to reach this success, would you have some hints for
SQLite team that would allow the code to become more easy to read and stay
performant ?

Example :
- a non-performant implementation of 'this' required 'that' complex
workaround,
- a non-availabe syntax for 'this' required 'that' other  complex syntax to
workaround,
- ...

Regards,
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[E.Pasma]

Op 16 mrt 2014, om 16:45 heeft big stone het volgende geschreven:


Hi Edzard,

I just reproduced your test.

Indeed :
- you probably blew-up everything running SQL sudoku on this planet :
  . 'hardest1' in under 2 seconds on my machine,
  . 'eastermonster1' in 43ms.
- with Norvig's method and available SQLite syntax.

Each of these feats is jaw-dropping.


Regards,
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users


Thanks a lot,

just some nuance, (being Python adept myself) here is a summary of my  
timings. From left to right:  the time in seconds for Norvig's Python  
script and my SQL script in two versions, without and with ordering  
the digits by most used.


sudoku  python  sql sql+zsort

easy1   .067.068.069

sqlite1 .082.095.197

hard1   445.900..085

hola1   .058.075.084

eastermonster1  .259.762.079

hardest1.2822.066   3.990

As the difference is in milliseonds I changed the Python script to  
include the printing of the output in the timing. Below is this version


## Solve Every Sudoku Puzzle

## See http://norvig.com/sudoku.html

## Throughout this program we have:
##   r is a row,e.g. 'A'
##   c is a column, e.g. '3'
##   s is a square, e.g. 'A3'
##   d is a digit,  e.g. '9'
##   u is a unit,   e.g. ['A1','B1','C1','D1','E1','F1','G1','H1','I1']
##   grid is a grid,e.g. 81 non-blank chars, e.g. starting with '. 
18...7...
##   values is a dict of possible values, e.g. {'A1':'12349',  
'A2':'8', ...}


def cross(A, B):
"Cross product of elements in A and elements in B."
return [a+b for a in A for b in B]

digits   = '123456789'
rows = 'ABCDEFGHI'
cols = digits
squares  = cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
[cross(r, cols) for r in rows] +
[cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in  
('123','456','789')])

units = dict((s, [u for u in unitlist if s in u])
 for s in squares)
peers = dict((s, set(sum(units[s],[]))-set([s]))
 for s in squares)

 Unit Tests 

def test():
"A set of tests that must pass."
assert len(squares) == 81
assert len(unitlist) == 27
assert all(len(units[s]) == 3 for s in squares)
assert all(len(peers[s]) == 20 for s in squares)
assert units['C2'] == [['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2',  
'H2', 'I2'],
   ['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7',  
'C8', 'C9'],
   ['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1',  
'C2', 'C3']]
assert peers['C2'] == set(['A2', 'B2', 'D2', 'E2', 'F2', 'G2',  
'H2', 'I2',
   'C1', 'C3', 'C4', 'C5', 'C6', 'C7',  
'C8', 'C9',

   'A1', 'A3', 'B1', 'B3'])
print 'All tests pass.'

 Parse a Grid 

def parse_grid(grid):
"""Convert grid to a dict of possible values, {square: digits}, or
return False if a contradiction is detected."""
## To start, every square can be any digit; then assign values  
from the grid.

values = dict((s, digits) for s in squares)
for s,d in grid_values(grid).items():
if d in digits and not assign(values, s, d):
return False ## (Fail if we can't assign d to square s.)
return values

def grid_values(grid):
"Convert grid into a dict of {square: char} with '0' or '.' for  
empties."

chars = [c for c in grid if c in digits or c in '0.']
assert len(chars) == 81
return dict(zip(squares, chars))

 Constraint Propagation 

def assign(values, s, d):
"""Eliminate all the other values (except d) from values[s] and  
propagate.
Return values, except return False if a contradiction is  
detected."""

other_values = values[s].replace(d, '')
if all(eliminate(values, s, d2) for d2 in other_values):
return values
else:
return False

def eliminate(values, s, d):
"""Eliminate d from values[s]; propagate when values or places <=  
2.
Return values, except return False if a contradiction is  
detected."""

if d not in values[s]:
return values ## Already eliminated
values[s] = values[s].replace(d,'')
## (1) If a square s is reduced to one value d2, then eliminate  
d2 from the peers.

if len(values[s]) == 0:
return False ## Contradiction: removed last value
elif len(values[s]) == 1:
d2 = values[s]
if not all(eliminate(values, s2, d2) for s2 in peers[s]):
return False
## (2) If a unit u is reduced to only one place for a value d,  
then put it there.

for u in units[s]:
dplaces = [s for s in u if d in values[s]]
if len(dplaces) == 0:
return False ## Contradiction: no place for this value
elif 

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

Hi Edzard,

I just reproduced your test.

Indeed :
- you probably blew-up everything running SQL sudoku on this planet :
   . 'hardest1' in under 2 seconds on my machine,
   . 'eastermonster1' in 43ms.
- with Norvig's method and available SQLite syntax.

Each of these feats is jaw-dropping.


Regards,
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[E.Pasma]

Hello

The SQLite version is 3.8.4 by now and this is stil about the sudoku  
solving. I studied Norvigs algorithm (Python) http://norvig.com/sudoku.html 
 . It is possible to achieve this method in SQL.


A very important difference between Norvigs programme and the SQLite  
example is however that Norvig only reporst the first solution  
(assuming the sudoku has just one solution). Changing my SQLIte code  
by adding LIMIT 1 immediately makes it much more competitive.
 To achieve Norvigs algorithm I need to choose the cell with least  
remaining choices. The Python program maintains a list of remaining  
choices for each cell. In my SQL, using bitmaps, the number of choices  
is expressed as:


(w10 or w11) +
(w20 or w21) +
(w30 or w31) +
(w40 or w41) +
(w50 or w51) +
(w60 or w61) +
(w70 or w71) +
(w80 or w81) +
(w90 or w91)

The complete programme is below. In my tests it needs 0.2 seconds for  
the SQLite example from http://www.sqlite.org/lang_with.html#sudoku


A novelty (comapred to Norvigs algorithm) is the ordering in which  
candidate digist are generated. I pick the digit that occurs most as  
first. That is intuitivelythe the way that I solve sudoku's by hand.  
This extra ordering (by zfixed desc) makes the time for the SQLIte  
example sudoku worse. But ..


the ;hard1' example from Norvigs code is solved in a fraction of a  
second. (by the way this example is ambigu).


Also your (Bigstone's) eastermonster  
('1 
... 
2.9.4 
...5...6...7...5.9.3...7...85..4.7.6...3...9.8...2.1')  
is solved within a second.


Finally here is the code (but it is not suited for educational purpose)

Regards, Edzard

create temporary table i ( --
i integer primary key, -- sudoku cell (1..81)
name char, -- A1..H8
word0, -- only bit i is set, i = 1..54
word1, -- only bit i-54 is set, i = 55..81
peers0, peers1) -- bitmap of neighbour cells
;
insert into i
select  i,
char(65+y)||(x+1) as name,
case when iword=0 then 1

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

Don't say postgresql is slower :
- I remember now I did then implement the "norvig postgresql",
- and it manages a 20% win over your solution with today postgresql 9.3.2.3.

Anyway, it's indeed a "less inefficient" run for now between SQL motors.

It remains to be seen if improving SQLite in sudoku solving will improve it
for other existing (or not yet imagined) workloads.

** the "norvig" PostgresSQL code **

-- implementing several "logical" algorithms in SQL to solve a sudoku
--
--   Norvig algorithm from Peter Norvig, http://norvig.com/sudoku.html
--
--   Brut Force algorithm from Anton Scheffer,
http://technology.amis.nl/2009/10/13/oracle-rdbms-11gr2-solving-a-sudoku-using-recursive-subquery-factoring/

--   translated per Marcin Mank,
http://archives.postgresql.org/pgsql-general/2009-11/msg00150.php
--
-- Norvig Algorithm =
--   . from given Sudoku problem, generate an array with each cell of the
sudoku being a string with all remaining possibilites
--   . define as "neighbors" of a cell, all cells which must not have the
same piece as this cells, (there are 20 neighbors to each cell)
--   . then analyse the cell (the string) have the less remaining
solutions, but more than 1,
--.. for a given sudoku position, "play" only on the first cell you
found with the less possibilities, and try each of them,
--   ... replace in this cell the string by the possible piece you
want to try,
--   ... remove the piece you played from the neighbors cells own
possibilities (as it's no more a possibility for them)
--... when removing a possibility to a neighbor, if it leave
him only on possibility, "play" it immediately,
--   ... if you remove all the solutions from a neighbor, than
you're not on the sudoku solution path, stop this track.
--
-- Brut force Algorithm =
--. try all possible piece in all empty position of the sudoku problem,
from top left to bottom right of the sudoku board cells,
--. stop a track each time you can't fill the next position
-- 
-- Speed result :
--. brute force loose on the easy and complex sudo, wins on the medium
--. "Brut" and  "Norvig" algorithms seem to stay mono-thread, giving-up
the competitive advantage of SQL
-- ==

-- Array usage in SQL (
http://www.postgresql.org/docs/9.2/static/functions-array.html)
-- array length (on a dimension) :array_length(anyarray, dimension_integer)
-- array to rowset : select unnest(ARRAY[1,2])
-- rowset to array : ARRAY(SELECT * FROM test)
-- array to string : select array_to_string(ARRAY[1, 2, 3, NULL, 5], ',',
'*')
-- string to array : select string_to_array('xx~^~yy~^~zz', '~^~', 'yy')



CREATE OR REPLACE function  format_string_sudoku(board  text [])
-- displays a sudoku "board" in 9x9 form with delimiters (so 13 line
records)
RETURNS setof text
LANGUAGE SQL
AS $$
with recursive  formatted_string(ss , ind )

as (select '' , 81 FROM generate_series(1,1) lp
union all
   select (case when length($1[ind])=1 then $1[ind] else '_' end) || (case
  when ind % 81=0 then '|='
  when ind % 27=0 then '||---||'
  when ind % 9=0 then '||'
  when ind % 3=0 then '|' else '' end)
  || ss , ind-1 from formatted_string where ind>0 )

select unnest(string_to_array( '=|' || ss, ''))
from formatted_string where ind=0
$$;

CREATE OR REPLACE function neighbors(cell integer)
-- gives back the rowset of neighbors of the given "cell" of any sudoku
board
RETURNS SETOF integer
LANGUAGE SQL
AS $$
with list_of(neighbors) as (select   unnest(ARRAY[
  mod( $1 - 1, 9 ) - 8 + lp * 9 ,
  ( ($1 - 1 ) / 9 ) * 9 + lp  ,
   mod( ( ( $1 - 1 ) / 3 ), 3 ) * 3 + ( ( $1 - 1 ) / 27 ) * 27 + lp + (
( lp - 1 ) / 3 ) * 6]) FROM generate_series(1,9) lp
  )
select  distinct * from list_of where
neighbors<>$1
$$;


CREATE OR REPLACE function truly_possibles(board text, cell integer)
-- gives the table of possible pieces to put in given "cell"  of the
current  sudoku "board"
-- including the one already in place, if it exists
RETURNS SETOF text
LANGUAGE SQL
AS $$

select z from   (SELECT gs::text AS z FROM generate_series(1,9) gs) z
  WHERE  substr( $1,  $2  ,1)=' '  and  NOT EXISTS ( SELECT NULL
   FROM neighbors($2) lp
   WHERE   z = substr( $1,   lp  , 1 )
 )
  union select  substr( $1,  $2 ,1 ) z where  substr( $1,  $2 ,1 )<>'
'
$$;

create or replace function create_sudoku_board(initial   text) returns
setof text[]
-- create a sudoku board from the given "s" (string form) sudoku problem
language sqlas
$$

with recursive

-- handle several string presentations of the sudoku board problem to solve
cleaned_starter(starter) as (select
regexp_replace(regexp_replace(initial,'\n|\=|\-|\|', '' ,'g' ),'\.','
','g'  )),

-- recursively generate the board from the bottom right cell to the top
left of the sudoku board
board_generator( t  , board , next_cell 

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[E.Pasma]

Op 9 feb 2014, om 20:50 heeft big stone het volgende geschreven:


Hi,

You're right,' recommands' is not in the code, but was not run anymore
either.
The "x" table cte definition should be removed, as the final  
request  use

only "q".

Anyway, after all this algorithmic surgery, Postgresql was slower  
with the

'optimization' algorithm than with the brute force.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users


Postgresql is out of competition then:
http://www.sqlite.org/lang_with.html#sudoku runs about 10% slower  
there (after s/instr/strpos/).
Bigstone's https://www.mail-archive.com/sqlite-users@sqlite.org/msg81630.html 
 takes three times longer in Psql.


(psql version 8.4.19)

___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

Hi,

You're right,' recommands' is not in the code, but was not run anymore
either.
The "x" table cte definition should be removed, as the final request  use
only "q".

Anyway, after all this algorithmic surgery, Postgresql was slower with the
'optimization' algorithm than with the brute force.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[E.Pasma]

Op 9 feb 2014, om 13:19 heeft big stone het volgende geschreven:


Congratulations, *E.Pasma* !

You indeed won the "brute force sudoku speed" competition for sqlite  
3.8.3

by a factor of  x2.5 on my PC !

D. Richard Hipp is still tuning the CTE implementation, so  
competition may

be less slow with 3.8.4.

To get clother to python speed (http://norvig.com/sudoku.html), we  
would

need to implement :
- an efficient Peter Norvig's method,
- or an efficient Dancing Links method.

==> See below link for "slower than brute force" dancing links
implementation in pgSQL.

http://www.postgresql.org/message-id/caj-6ajqpxxex8ftljksngksvbjrn0h3hydw9xpsvu837gsn...@mail.gmail.com

regards,



I see that there is much competition. The version at http://norvig.com/sudoku.html 
 solves our example in 0.04 seconds. At least that is what it  
reports. A timer within Python made it 0.1 seconds. Still that is at  
least 10 times faster than my SQLite version. On my machine I have the  
following timings now:


http://www.sqlite.org/lang_with.html#sudoku - 13 seconds
Bigstone's https://www.mail-archive.com/sqlite-users@sqlite.org/msg81630.html 
 - 4 sceonds

My bitmapped version - 1.5 seconds
Peter Norvig's http://norvig.com/sudoku.html - 0.1 second

By the way I could not run your postgresql version. Psql reports that  
function recommands does not exist.



___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

Congratulations, *E.Pasma* !

You indeed won the "brute force sudoku speed" competition for sqlite 3.8.3
by a factor of  x2.5 on my PC !

D. Richard Hipp is still tuning the CTE implementation, so competition may
be less slow with 3.8.4.

To get clother to python speed (http://norvig.com/sudoku.html), we would
need to implement :
- an efficient Peter Norvig's method,
- or an efficient Dancing Links method.

==> See below link for "slower than brute force" dancing links
implementation in pgSQL.

http://www.postgresql.org/message-id/caj-6ajqpxxex8ftljksngksvbjrn0h3hydw9xpsvu837gsn...@mail.gmail.com

regards,
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[E.Pasma]

Op 6 feb 2014, om 16:46 heeft Simon Slavin het volgende geschreven:



On 6 Feb 2014, at 7:15am, big stone  wrote:

If we wish to have SQLite + Python combination to become "reference  
choice"

in education, I would think that priority list should be :


Just to remind you that you're posting to the SQLite list.  Most of  
those are things that would be done by the Python maintainers, not  
the SQLite maintainers.


Simon.


I find the subject of Sudoku solving still interesting and have an  
other quey here. This derives from Bigstone's 1st solution, defining a  
neighbourhood relation between sudoku cells. New is that I tried  
bitmaps instead of a characterstring to represent the sudoku. Below is  
the result. Conclusions

- bitmaps are hard to debug as they can not be easily viewed
- but the solution is much fater (four times)
- the recursion tends to go breath first by default which is not  
optimal for speed.
- using a seperate (temporary) table for a non-trivial sub-queriy,  
instead of a CTE. is worth when used at several places.


create temporary table ind (
ind integer primary key, -- sudoku cell (1..81)
word0, -- bitmap of ind, bits 1..54
word1, -- bitmap of ind, bits 55..81
neighbours0, neighbours1) -- bitmap of neighbour cells
;
/*
initializing the neighbour bitmaps was the
most tricky part: one must probably turn the
soduku upside down and view it through a mirror
to see the x,y coordinates as used here.
*/
insert into ind
select  ind,
case when iword=0 then 10 then word0 else 0 end,
w1 | case when z>0 then word1 else 0 end,
w10 | case when z=1 then word0 else 0 end,
w11 | case when z=1 then word1 else 0 end,
w20 | case when z=2 then word0 else 0 end,
w21 | case when z=2 then word1 else 0 end,
w30 | case when z=3 then word0 else 0 end,
w31 | case when z=3 then word1 else 0 end,
w40 | case when z=4 then word0 else 0 end,
w41 | case when z=4 then word1 else 0 end,
w50 | case when z=5 then word0 else 0 end,
w51 | case when z=5 then word1 else 0 end,
w60 | case when z=6 then word0 else 0 end,
w61 | case when z=6 then word1 else 0 end,
w70 | case when z=7 then word0 else 0 end,
w71 | case when z=7 then word1 else 0 end,
w80 | case when z=8 then word0 else 0 end,
w81 | case when z=8 then word1 else 0 end,
w90 | case when z=9 then word0 else 0 end,
w91 | case when z=9 then word1 else 0 end
frominput
joinind
on  ind.ind = input.ind
)
,
sudoku as (
select  1 as ind,
w0, w1,
w10, w11,
w20, w21,
w30, w31,
w40, w41,
w50, w51,
w60, w61,
w70, w71,
w80, w81,
w90, w91
frominput
where   ind>81
union all
select  sudoku.ind+1,
w0 | word0,
w1 | word1,
w10 | case when z=1 then word0 else 0 end,
w11 | case when z=1 then word1 else 0 end,
w20 | case when z=2 then word0 else 0 end,
w21 | case when z=2 then word1 else 0 end,
w30 | case when z=3 then word0 else 0 end,
w31 | case when z=3 then word1 else 0 end,
w40 | case when z=4 then word0 else 0 end,
w41 | case when z=4 then word1 else 0 end,
w50 | case when z=5 then word0 else 0 end,
w51 | case when z=5 then word1 else 0 

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[Roger Binns]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

On 05/02/14 23:15, big stone wrote:
> APSW looks indeed great for specialised installations.

The intention behind APSW is a Python wrapper for SQLite3.  It does
everything the SQLite way where applicable.  It advances with SQLite
meaning new versions of APSW do not support older releases of SQLite.

The one shipped with Python (sqlite3 aka pysqlite) tries to comply with
DBAPI and hence tries to be indistinguishable from the wrappers for the
other databases (postgres, mysql etc).  This includes faking functionality
that SQLite doesn't actually have.  It also supports very old versions of
SQLite - I believe it will work correctly with 3.0.0!

> If we wish to have SQLite + Python combination

You'll find the python sqlite community at
https://groups.google.com/forum/#!forum/python-sqlite

Roger
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.14 (GNU/Linux)

iEYEARECAAYFAlLz5AYACgkQmOOfHg372QRi7gCeNhVPXQ2W7BGA1k2bU9q7vcNq
KL0Anjw2vcScfVG6pIUHJFFaB8SFFgNk
=CYrk
-END PGP SIGNATURE-
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[Simon Slavin]

On 6 Feb 2014, at 7:15am, big stone  wrote:

> If we wish to have SQLite + Python combination to become "reference choice"
> in education, I would think that priority list should be :

Just to remind you that you're posting to the SQLite list.  Most of those are 
things that would be done by the Python maintainers, not the SQLite maintainers.

Simon.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

Hello,

APSW looks indeed great for specialised installations.

If we wish to have SQLite + Python combination to become "reference choice"
in education, I would think that priority list should be :

- fixing true problems among those listed in "http://bugs.python.org/; with
search the keyword "SQLite" :
  (example : http://bugs.python.org/issue9303 : "Migrate sqlite3 module to
_v2 API to enhance performance")

- supporting a little more "SQL standard" features at each maintenance
release of SQLite,

- having an evolution in current Python.org Policy not to change of SQLite
version between 3.x.0beta1 and 3.x.9,
(it was no problem as long as SQLite was not evolving to support more
SQL standard)
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[E.Pasma]

Op 1 feb 2014, om 08:29 heeft big stone het volgende geschreven:


Maybe Chrismas will be in february this year  :

http://bugs.python.org/issue20465

Whatever will be the answer from the python team, THANKS a lot Mr  
Hipp, Mr

Kennedy, and Mr Mistachkin for making it possible !
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Hello, just in case this great development may not yet be included in  
Python, you can of cause install your own as a Python site package.  
Being an APSW adept myself, I like to forward the announcement below.

Best regards, E. Pasma.


Begin doorgestuurd bericht:


Van: Roger Binns 
Datum: 5 februari 2014 22:04:04 GMT+01:00
Aan: python-sql...@googlegroups.com
Onderwerp: [python-sqlite] APSW 3.8.3-r1 released
Antwoord aan: python-sql...@googlegroups.com

APSW 3.8.3-r1 is now available. The home page is at
https://github.com/rogerbinns/apsw which includes full documentation,
source and binary distributions for Windows (Python 2.3 onwards  
including

Python 3).

APSW is a wrapper around SQLite that provides all SQLite API  
functionality

in Python. It is not DBAPI compliant as it provides SQLite semantics.
pysqlite provides DBAPI semantics. You can see the two approaches
contrasted at http://rogerbinns.github.io/apsw/pysqlite.html

Changelist is below and a clickable version at
http://rogerbinns.github.io/apsw/changes.html

APSW is now hosted at Github - https://github.com/rogerbinns/apsw

Added SQLITE_RECURSIVE, SQLITE_READONLY_DBMOVED,
SQLITE_FCNTL_COMMIT_PHASETWO, SQLITE_FCNTL_HAS_MOVED and  
SQLITE_FCNTL_SYNC

constants.

Roger



___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

Maybe Chrismas will be in february this year  :

http://bugs.python.org/issue20465

Whatever will be the answer from the python team, THANKS a lot Mr Hipp, Mr
Kennedy, and Mr Mistachkin for making it possible !
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[Joseph R. Justice]

On Sat, Jan 18, 2014 at 3:38 PM, big stone  wrote:

And :
> - python3.4 is still in beta also, not a released product.
> - sadly  first RC  candidate 1 is  February 9, 2014, 2 days earlier.
>
> Sqlite was so close now, *so close* to achieve this goal ...
>

Maybe you could get the Python devs to push back the RC deadline, assuming
they feel it's important to get 3.8.3 into Python 3.4, or see if Dr. Hipp
is willing to push the SQLite release up (assuming nothing goes wrong), or
get them both to meet in the middle.

Or, if it's expected that there will be no changes to SQLite between when
it's tagged as a release candidate and when it's officially released (which
can only be known close to that date), perhaps the Python devs will be
willing to incorporate the SQLite release candidate into the Python release
candidate, under the condition that the SQLite code not functionally change
from release candidate to official release status.

Or, perhaps a change can be made for a prospective 3.4.1, or if developer
and end user demand is sufficient, perhaps the Python devs will agree to
accommodate that.

You can try, anyway.



Joseph
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[Keith Medcalf]

soduko1.sql and soduko2.sql are the two originals.  soduko3.sql removes the 
digits view to an actual table (from soduko2.sql) and soduko3.sql puts digits 
back in as a CTE but is a select from the wholenumber module rather than 
generating the digits recursively.

So, the fastest one uses digits pregenerated as a table with both text and 
integer columns used in the appropriate places dictated by the format 
requirement in order to avoid conversions.  All run one after the other on a 
3Ghz core, single threaded, solving the same problem.

The main determinants are whether or not the digits is a CTE thus regenerated 
each time needed, and whether the digits table contains both text and integer 
values so that conversions can be avoided.  The former (CTE regeneration) may 
be able to be fixed in the optimizer.  The latter (conversions) is pretty much 
expected and why we have datatypes.

>timethis sqlite < soduko1.sql

TimeThis :  Command Line :  sqlite
TimeThis :Start Time :  Sun Jan 19 11:43:39 2014

812753649943682175675491283154237896369845721287169534521974368438526917796318452

TimeThis :  Command Line :  sqlite
TimeThis :Start Time :  Sun Jan 19 11:43:39 2014
TimeThis :  End Time :  Sun Jan 19 11:45:27 2014
TimeThis :  Elapsed Time :  00:01:47.919


>timethis sqlite < soduko2.sql

TimeThis :  Command Line :  sqlite
TimeThis :Start Time :  Sun Jan 19 11:46:39 2014

812753649943682175675491283154237896369845721287169534521974368438526917796318452

TimeThis :  Command Line :  sqlite
TimeThis :Start Time :  Sun Jan 19 11:46:39 2014
TimeThis :  End Time :  Sun Jan 19 11:50:42 2014
TimeThis :  Elapsed Time :  00:04:02.752


>timethis sqlite < soduko3.sql

TimeThis :  Command Line :  sqlite
TimeThis :Start Time :  Sun Jan 19 11:50:50 2014

812753649943682175675491283154237896369845721287169534521974368438526917796318452

TimeThis :  Command Line :  sqlite
TimeThis :Start Time :  Sun Jan 19 11:50:50 2014
TimeThis :  End Time :  Sun Jan 19 11:52:10 2014
TimeThis :  Elapsed Time :  00:01:19.912


>timethis sqlite < soduko4.sql

TimeThis :  Command Line :  sqlite
TimeThis :Start Time :  Sun Jan 19 11:52:17 2014

812753649943682175675491283154237896369845721287169534521974368438526917796318452

TimeThis :  Command Line :  sqlite
TimeThis :Start Time :  Sun Jan 19 11:52:17 2014
TimeThis :  End Time :  Sun Jan 19 11:54:14 2014
TimeThis :  Elapsed Time :  00:01:56.807

soduko1 uses:


drop table if exists gen9;
create table gen9(z);
insert into gen9 values ('1'),('2'),('3'),('4'),('5'),('6'),('7'),('8'),('9');
drop table if exists initial;
create table initial (s, ind);

insert into initial
select  sud, instr( sud, ' ')
  from  (SELECT
--- '53  76  195986 8   6   34  8 3  17   2   6 6   
 28419  58  79'
'8  36  7  9 2   5   7   457 1   3   1
68  85   1  94  '
 as sud) as q;

soduko2:

WITH RECURSIVE input(sud) AS (
   VALUES(
'8..36..7..9.2...5...7...457.1...3...168..85...1..94..'
--- 
'53..76..195986.8...6...34..8.3..17...2...6.628419..58..79'
   )
),

/* A table filled with digits 1..9, inclusive. */
digits(z, lp) AS (
   VALUES('1', 1)
   UNION ALL SELECT
   CAST(lp+1 AS TEXT), lp+1 FROM digits WHERE lp<9
),

soduko3:

create table digits(lp integer primary key, z text);
create virtual table w using wholenumber;
insert into digits (lp, z) select value, cast(value as text) from w where value 
between 1 and 9;

WITH RECURSIVE input(sud) AS (
   VALUES(
'8..36..7..9.2...5...7...457.1...3...168..85...1..94..'
--- 
'53..76..195986.8...6...34..8.3..17...2...6.628419..58..79'
   )
),

and soduko4:

create virtual table w using wholenumber;
WITH RECURSIVE input(sud) AS (
   VALUES(
'8..36..7..9.2...5...7...457.1...3...168..85...1..94..'
--- 
'53..76..195986.8...6...34..8.3..17...2...6.628419..58..79'
   )
),

/* A table filled with digits 1..9, inclusive. */
digits(z, lp) AS (
select cast(value as text), value from w where value between 1 and 9
--   VALUES('1', 1)
--   UNION ALL SELECT
--   CAST(lp+1 AS TEXT), lp+1 FROM digits WHERE lp<9
),



>-Original Message-
>From: sqlite-users-boun...@sqlite.org [mailto:sqlite-users-
>boun...@sqlite.org] On Behalf Of big stone
>Sent: Sunday, 19 January, 2014 04:54
>To: sqlite-users@sqlite.org
>Subject: Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk
>
>Hi Keith,
>
>Indeed just removing the CTE creation of the DIGITS makes Dan's version
>up
>to speed.
>
>Would the "wholenumber" external SQLite module help :
>- to make SQLite code cleaner ? (like "generate_series" of Postgresql, or
>"dual" of Oracle)
>- still provide the same speed-up ?
>
>
>Portfolio of 

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

Hi Keith,

Indeed just removing the CTE creation of the DIGITS makes Dan's version up
to speed.

Would the "wholenumber" external SQLite module help :
- to make SQLite code cleaner ? (like "generate_series" of Postgresql, or
"dual" of Oracle)
- still provide the same speed-up ?


Portfolio of typical Sudokus
-- easy   (0 sec)
'53..76..195986.8...6...34..8.3..17...2...6.628419..58..79'
-- medium (2 sec)
'17.9..3..2...8..96..553..9...1..8...264...3..1..4..7..7...3..'
-- hard   (200 s)
'8..36..7..9.2...5...7...457.1...3...168..85...1..94..'

WITH RECURSIVE input(sud) AS (
   VALUES(
'53..76..195986.8...6...34..8.3..17...2...6.628419..58..79'
   )
),

/* A table filled with digits 1..9, inclusive. */
digits(z, lp) AS (
VALUES('1', 1),('2', 2) ,('3', 3),('4', 4),('5', 5),('6', 6),('7',
7),('8', 8),('9', 9)
),

/* The tricky bit. */
x(s, ind) AS (
   SELECT sud, instr(sud, '.') FROM input
   UNION ALL
   SELECT
   substr(s, 1, ind-1) || z || substr(s, ind+1),
   instr( substr(s, 1, ind-1) || z || substr(s, ind+1), '.' )
   FROM x, digits AS z
   WHERE ind>0
   AND NOT EXISTS (
 SELECT 1 FROM digits AS lp
 WHERE z.z = substr(s, ((ind-1)/9)*9 + lp, 1)
 OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)
 OR z.z = substr(s, (((ind-1)/3) % 3) * 3
   + ((ind-1)/27) * 27 + lp
   + ((lp-1) / 3) * 6
   , 1)
   )
)

SELECT s FROM x WHERE ind=0;
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[Keith Medcalf]

>>- my badly written sql takes  about 3'40", (on my windows pc)
>>- your neater version takes  about 7'20",(on my windows pc)
>>==> Do you see the same ratio ? I don't catch why yours is slower.
>
>One uses tables for the join constants and the other (slower one)
>dynamically regenerates the constant table each time it is needed by re-
>running the recursive CTE which dynamically generates the constants.
>
>Or at least that is what it looks like when you request SQLite to EXPLAIN
>itself ...
>
>Though I could be mistaken ...

If you remove 'digits' from being a CTE to being a table, both execute "almost" 
the same speed.

The remaining differential is that in the first case, the digits table only 
contains text, and the text is repetitively converted to an integer for use in 
the correlated subquery in the recursive CTE.  This adds about 15-20% overhead 
compared to carrying both the text and integer version of the digit in the 
digits table and using the field with the appropriate field type in the 
appropriate place.  Several million conversions of text to integer add up to a 
significant number of cycles.




___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[Keith Medcalf]

>- my badly written sql takes  about 3'40", (on my windows pc)
>- your neater version takes  about 7'20",(on my windows pc)
>==> Do you see the same ratio ? I don't catch why yours is slower.

One uses tables for the join constants and the other (slower one) dynamically 
regenerates the constant table each time it is needed by re-running the 
recursive CTE which dynamically generates the constants.

Or at least that is what it looks like when you request SQLite to EXPLAIN 
itself ...

Though I could be mistaken ...




___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

And :
- python3.4 is still in beta also, not a released product.
- sadly  first RC  candidate 1 is  February 9, 2014, 2 days earlier.

Sqlite was so close now, *so close* to achieve this goal ...


very sad.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[Richard Hipp]

On Sat, Jan 18, 2014 at 2:34 PM, Simon Slavin  wrote:

>
> I'm sorry, I withdraw that.  I just remembered that SQLite 3.8.3 is still
> in beta.  It would be a bad idea to include a beta library in a released
> product.  So whether it gets included or not depends on comparing the
> release schedules of the two products.
>


Tentative release date for SQLite 3.8.3 is 2014-02-11.


-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[Simon Slavin]

On 18 Jan 2014, at 7:30pm, Simon Slavin  wrote:

> On 18 Jan 2014, at 7:27pm, big stone  wrote:
> 
>> I'm still making desesperate prayers to have this SQLite3.8.3 in Python3.4.
>> 
>> Python3.4 beta2 is using in SQLite3.8.1
> 
> Talk to the Python folks on the Python dev list as soon as possible:

I'm sorry, I withdraw that.  I just remembered that SQLite 3.8.3 is still in 
beta.  It would be a bad idea to include a beta library in a released product.  
So whether it gets included or not depends on comparing the release schedules 
of the two products.

Simon.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[Simon Slavin]

On 18 Jan 2014, at 7:27pm, big stone  wrote:

> I'm still making desesperate prayers to have this SQLite3.8.3 in Python3.4.
> 
> Python3.4 beta2 is using in SQLite3.8.1

Talk to the Python folks on the Python dev list as soon as possible:



If they're still in beta they might do it.  If not, then it'll have to wait for 
3.5.

Simon.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

I'm still making desesperate prayers to have this SQLite3.8.3 in Python3.4.

Python3.4 beta2 is using in SQLite3.8.1

"SQL CTE motor inside !" could be a big incentive for Python2.X users to
switch to Python 3.4.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

Recursive CTE are really fun to :
- describe algorithms in sql,
- measure sql motor speed.

For the hardest sudoku at hand that I have:
 
'8..36..7..9.2...5...7...457.1...3...168..85...1..94..'

- my badly written sql takes  about 3'40", (on my windows pc)
- your neater version takes  about 7'20",(on my windows pc)
==> Do you see the same ratio ? I don't catch why yours is slower.

Anyway, SQLite speed is in  the same ballpark as postgresql (9.2.1).
==> Awesome  !

Apparently, the RECURSIVE CTE design stucks all algorithms execution in a
mono-process mode.
==> If someone as a solution to make this sudoku algorithm parallelized  on
SQL, I would be VERY interested to read his trick.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[Dan Kennedy]

Let me try again. Some spaces were missing from the input
in the parent post:


/* The input suduko. */
WITH RECURSIVE input(sud) AS (
  VALUES(
'53..76..195986.8...6...34..8.3..17...2...6.628419..58..79'
  )
),

/* A table filled with digits 1..9, inclusive. */
digits(z, lp) AS (
  VALUES('1', 1)
  UNION ALL SELECT
  CAST(lp+1 AS TEXT), lp+1 FROM digits WHERE lp<9
),

/* The tricky bit. */
x(s, ind) AS (
  SELECT sud, instr(sud, '.') FROM input
  UNION ALL
  SELECT
  substr(s, 1, ind-1) || z || substr(s, ind+1),
  instr( substr(s, 1, ind-1) || z || substr(s, ind+1), '.' )
  FROM x, digits AS z
  WHERE ind>0
  AND NOT EXISTS (
SELECT 1 FROM digits AS lp
WHERE z.z = substr(s, ((ind-1)/9)*9 + lp, 1)
OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)
OR z.z = substr(s, (((ind-1)/3) % 3) * 3
  + ((ind-1)/27) * 27 + lp
  + ((lp-1) / 3) * 6
  , 1)
  )
)

SELECT s FROM x WHERE ind=0;


___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[Rob Willett]

I have to say thats it been a long time since I sat back and was amazed by what 
people can do.

My knowledge of SQL is limited, whilst I recognise it is a functional language, 
I had no idea you could solve Sudoku in it.

I take my hat off to the real experts. The downside of this is I now really, 
really understand how little I know the language :)

Rob.

On 18 Jan 2014, at 17:50, Dan Kennedy  wrote:

> 
> Beaten by minutes!
> 
> 
> /* The input suduko. */
> WITH RECURSIVE input(sud) AS (
>  VALUES(
>'53  76  195986 8   6   34  8 3  17   2   6 6 28419  5
> 8  79'
>  )
> ),
> 
> /* A table filled with digits 1..9, inclusive. */
> digits(z, lp) AS (
>  VALUES('1', 1)
>  UNION ALL SELECT
>  CAST(lp+1 AS TEXT), lp+1 FROM digits WHERE lp<9
> ),
> 
> /* The tricky bit. */
> x(s, ind) AS (
>  SELECT sud, instr(sud, ' ') FROM input
>  UNION ALL
>  SELECT
>substr(s, 1, ind-1) || z || substr(s, ind+1),
>instr( substr(s, 1, ind-1) || z || substr(s, ind+1), ' ' )
>  FROM x, digits AS z
>  WHERE ind>0
>  AND NOT EXISTS (
>SELECT 1 FROM digits AS lp
>  WHERE z.z = substr(s, ((ind-1)/9)*9 + lp, 1)
> OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)
> OR z.z = substr(s, (((ind-1)/3) % 3) * 3
>  + ((ind-1)/27) * 27 + lp
>  + ((lp-1) / 3) * 6
>, 1)
>  )
> )
> 
> SELECT s FROM x WHERE ind=0;
> 
> 
> 
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[Dan Kennedy]

Beaten by minutes!


/* The input suduko. */
WITH RECURSIVE input(sud) AS (
  VALUES(
'53  76  195986 8   6   34  8 3  17   2   6 6 28
419  58  79'

  )
),

/* A table filled with digits 1..9, inclusive. */
digits(z, lp) AS (
  VALUES('1', 1)
  UNION ALL SELECT
  CAST(lp+1 AS TEXT), lp+1 FROM digits WHERE lp<9
),

/* The tricky bit. */
x(s, ind) AS (
  SELECT sud, instr(sud, ' ') FROM input
  UNION ALL
  SELECT
substr(s, 1, ind-1) || z || substr(s, ind+1),
instr( substr(s, 1, ind-1) || z || substr(s, ind+1), ' ' )
  FROM x, digits AS z
  WHERE ind>0
  AND NOT EXISTS (
SELECT 1 FROM digits AS lp
  WHERE z.z = substr(s, ((ind-1)/9)*9 + lp, 1)
 OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)
 OR z.z = substr(s, (((ind-1)/3) % 3) * 3
  + ((ind-1)/27) * 27 + lp
  + ((lp-1) / 3) * 6
, 1)
  )
)

SELECT s FROM x WHERE ind=0;



___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

sudoku !

drop table if exists gen9;
create table gen9(z);
insert into gen9 values
('1'),('2'),('3'),('4'),('5'),('6'),('7'),('8'),('9');

drop table if exists initial;
create table initial ( s, ind) ;
insert into initial select  sud, instr( sud, ' ')   from
 (SELECT '53  76  195986 8   6   34  8 3  17   2   6 628
419  58  79' as sud) as q ;
 WITH  RECURSIVE x(  s, ind ) AS
 (SELECT  s, ind  from initial
  UNION ALL
  SELECT  substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 ) as s
   ,
instr(substr('',1,
ind)
   || substr( s, ind + 1 ), ' ' ) as ind
  FROM  x inner join  gen9 as z
  WHERE ind >0
  AND NOT EXISTS ( SELECT NULL
   FROM gen9 as lp
   WHERE
   z.z = substr( s, ( (ind - 1 ) / 9 ) * 9 +lp.z, 1 )
--line search
   OR
z.z = substr( s, (ind -(9*(( ind - 1)/ 9 ))) - 9 + lp.z
* 9, 1 ) --columns search
   OR
   z.z = substr( s, (( ind - 1 ) / 3 - 3*(( ( ind - 1 ) / 3
)/ 3) ) * 3 --square column
  + ( ( ind - 1 ) / 27 ) * 27  --
square line
  + lp.z + ( ( lp.z - 1 ) / 3 ) * 6 --
position in square
   , 1 )
 )
  )
select s from x where ind= 0 ;
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[Petite Abeille]

On Jan 17, 2014, at 11:26 PM, big stone  wrote:

> Has anyone a clue ?

No. But this is what Charlie the Unicorn has to say on the subject:

"Oh God you guys. This better be pretty important. Is the meadow on fire?"

___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

I think this should work, but  with current almagation avalaible for
download sqlite-amalgamation-201401171527, I get nothing.
Has anyone a clue ?

drop table if exists gen9;
drop table if exists genx;
drop table if exists initial;
create table gen9(z);
insert into gen9   values
('1'),('2'),('3'),('4'),('5'),('6'),('7'),('8'),('9');
create table initial (s, ind) ;
insert into initial select  sud, instr( sud, ' ')   from
 (SELECT '53  76  195986 8   6   34  8 3  17   2   6 628
419  58  79' as sud) as q ;
 WITH  RECURSIVE x( s, ind ) AS
 (SELECT *  from initial
  UNION ALL
  SELECT substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 ) as s
   ,
instr(substr('xx',1,
ind)
   || substr( s, ind + 1 ), ' ' ) as ind
  FROM x ,   gen9 as z
  WHERE ind > 0
  AND NOT EXISTS ( SELECT NULL
   FROM gen9 as lp
   WHERE z.z = substr( s, ( (ind - 1 ) / 9 ) * 9 +lp.z, 1 )
   OR
z.z = substr( s, (ind -(9*( ind - 1)/ 9 )) - 8 + lp.z *
9, 1 )
   OR
   z.z = substr( s, (( ind - 1 ) / 3 - ( ( ind - 1 ) / 3 )/
3 ) * 3
  + ( ( ind - 1 ) / 27 ) * 27 + lp.z
  + ( ( lp.z - 1 ) / 3 ) * 6
   , 1 )

 ))

SELECT s FROM x
--even without the test below, I can't read back the initial record of the
recursive CTE
--WHERE ind = 0;
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

hello again,

I get the message of error "OperationalError: circular reference: x"
from the recursive CTE below.

Is it a syntax error or a bug ?

  

drop table if exists gen9;
drop table if exists genx;
create table gen9(z);
insert into gen9   values
('1'),('2'),('3'),('4'),('5'),('6'),('7'),('8'),('9');
WITH  RECURSIVE x( s, ind ) AS
 (SELECT sud, instr( sud, ' ') as w  from
(SELECT '53  76  195986 8   6   34  8 3  17   2   6 628
419  58  79'  AS sud
 UNION ALL
  SELECT substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
   ,
instr(substr('xx',1,
ind)
   || substr( s, ind + 1 ), ' ' ) as sud
  FROM x ,   gen9 as z
  WHERE ind > 0
  AND NOT EXISTS ( SELECT NULL
   FROM gen9 as lp
   WHERE z.z = substr( s, ( (ind - 1 ) / 9 ) * 9 +lp.z, 1 )
   ORz.z = substr( s, ind -(( ind - 1)/ 9 ) - 8 + lp.z
* 9, 1 )
   ORz.z = substr( s, (( ind - 1 ) / 3 - ( ( ind - 1 )
/ 3 )/ 3 ) * 3
  + ( ( ind - 1 ) / 27 ) * 27 + lp.z
  + ( ( lp.z - 1 ) / 3 ) * 6
   , 1 )
 )))

SELECT s FROM x WHERE ind = 0;
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] Solving the Sudoku with SQlite 3.8.3 trunk

[big stone]

Hello,

I'm trying to do the SQLite version of the sudoku solver that exist here in
POSTGRESQL
(here : http://wiki.postgresql.org/wiki/Sudoku_puzzle)

I'm at this stage below  currently.
could  anyone help me ? I have a syntax error , and a bit confuse where it
can be (not sure about the modulo translation also)



drop table if exists gen9;
drop table if exists genx;
create table genx(x);
insert into genx values
('xx');
create table gen9(z);
insert into gen9   values (1),(2),(3),(4),(5),(6),(7),(8),(9);
WITH  RECURSIVE x( s, ind ) AS
 (SELECT sud, instr( sud, ' ')   from
(SELECT '53  76  195986 8   6   34  8 3  17   2   6 628
419  58  79'  AS sud
 UNION ALL
  SELECT substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
   ,
instr(substr('xx',1,
ind)
   || substr( s, ind + 1 ), ' ' )
  FROM x
 ,   gen9 as z
  WHERE ind > 0
  AND NOT EXISTS ( SELECT NULL
   FROM gen9 as lp
   WHERE z.z = substr( s, ( (ind - 1 ) / 9 ) * 9 + lp, 1 )
   ORz.z = substr( s, ind -( ind - 1/ 9 ) - 8 + lp * 9,
1 )
   ORz.z = substr( s, (( ind - 1 ) / 3 - ( ( ind - 1 )
/ 3 )/ 3 ) * 3
  + ( ( ind - 1 ) / 27 ) * 27 + lp
  + ( ( lp - 1 ) / 3 ) * 6
   , 1 )
 )
)
SELECT s
FROM x
WHERE ind = 0;
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users